Orthogonal Decomposition of A Matrix I'm trying to follow/understand a research paper that I have, and well, it's been a while since I've done this kind of math. At this point I have an nxn matrix H and from that construct an (n-1)xn matrix H' = $[\textbf{h}_1-\textbf{h}_n$, ..., $\textbf{h}_{1-n}-\textbf{h}_n]^T$. Now "using orthogonal decomposition" I'm to obtain H'=$\textbf{QU}$, where $\textbf{Q}$ is an (n-1)x(n-1) orthogonal matrix and $\textbf{U}$, which is an (n-1)xn upper diagonal matrix.
I guess I'm hoping someone can better explain orthogonal decomposition and help me write the elements of $\textbf{Q}$ and $\textbf{U}$ in terms of the elements of H'.
 A: Look up QR decomposition. QR decomposition decomposes the matrix as a product of an orthonormal matrix and an upper triangular matrix. i.e. $QQ^T = Q^TQ = I$ and $R$ is upper triangular. QR decomposition is nothing but Gram-Schmidt orthogonalization process. It is relatively easy to code up QR based on Gram Schmidt orthogonalization process. Wikipedia does a nearly complete job of explaining both QR and Gram-Schmidt. The main idea behind QR/Gram Schmidt is to construct an orthonormal basis for the column space/range of $A$ using the columns of the matrix $A$. The idea is relatively simple.

*

*Take the first column of $A$ and make it into a unit vector by dividing out by the norm


*Take the second column of $A$ and remove the component along the first column of $A$ and make it into a unit vector by dividing out by the norm


*In general, take the $k^{th}$ column of $A$ and remove the components from the previous $k-1$ columns of $A$ (i.e. remove the subspace spanned by the first $k-1$ columns of $A$) and make it into a unit vector by dividing out by the norm
This orthonormal set of vectors give you the $Q$ matrix and the (rotation) operations you perform on the vectors of the $Q$ matrix go into the $R$ (rotation) matrix.
However, the QR algorithm using Gram-Schmidt orthogonalization process can become unstable. Hence couple of other algorithms based on Givens Rotation, Householder reflection are used in practise since they tend to be more stable than Gram-Schmidt algorithm.
There is a one to one correspondence between the algorithm based on Givens Rotation and the algorithm based on Householder reflection. (Just like the correspondence between solving a system by Gauss Elimination and LU). So technically the stability of the algorithm based on Givens rotation is same as the stability of the algorithm based on Householder reflection.
