Linear Algebra: Gram-Schmidt $A=QR$ factorisation and diagonal components of $R$

Question

With the $A=QR$ factorisation ($Q$ is a matrix with orthonormal columns $q_1$ to $q_n$, $A$ is a matrix with independent columns $a_1$ to $a_n$. $Q$ is created from the columns of $A$ with Gram-Schmidt), how would I prove that $r_{jj}=\rVert A_j \lVert$, where $A_j$ is a column vector produced by Gram-Schmidt before it is divided by its length to produce $q_j$ of length 1?

Answer 1

Generally matrix multiplication $A=BC$ can be read as $a_1=Bc_1,a_2=Bc_2,\dots,a_n=Bc_n$, where $a_i$ are the columns of $A$ and $c_i$ are the columns of $C$. So in the case of $A=QR$ you have $a_i=Qr_i$.

Now what happens when you multiply out $Qr_i$? Only the first $i$ entries of $r_i$ are nonzero*. That means $a_i=\sum_{j=1}^i q_j r_{ji}$, thus $|r_{ii}|=\left \| a_i - \sum_{j=1}^{i-1} q_j r_{ji} \right \|$. This right hand side is what you called $\| A_i \|$, where $A_i$ is $a_i$ minus the projections of $a_i$ onto the $q_j$ with $j<i$.

Now to get the signs straight, you have to decide that the diagonal of $R$ consists of nonnegative numbers. This is not automatic from the assumption that $Q$ is orthogonal and $R$ is upper triangular, since you can always replace $q_j$ by $-q_j$ and then replace all of the $r_{ji}$ by $-r_{ji}$.

* It is possible that not even all $i$ of those are nonzero, but those are the ones that have any chance to be nonzero.