Past exam of the mathematics course of the University of Cambridge / 2001 / ib / Paper 2 / 14E (Numerical Analysis)

For a real symmetric positive-definite matrix, the Cholesky decomposition is $B=R^{T}R$, where $R$ is upper triangular with positive diagonal; equivalently $B=L{L}^T$ with $L=R^T$ lower triangular.

Existence can be proved by induction. Write $B=\left(\begin{array}{cc}b& v^T\\ v& C\end{array}\right)$, where $b>0$. For a nonzero vector $z$, evaluate the quadratic form at $(-v^{T}z/b,z{)}^T$ to obtain $z^T(C-v{v}^T/b)z>0$. The Schur complement is therefore positive definite. By induction it has factor $R_0^T{R}_0$, andhas $R^{T}R=B$. The one-dimensional starting case is the positive square root.

For uniqueness, if $R_1^T{R}_1=R_2^T{R}_2=B$, then $U=R_2{R}_1^{-1}$ is upper triangular and satisfies $U^{T}U=I$. Since $U^{-1}$ is upper triangular and equals $U^T$, which is lower triangular, $U$ is diagonal. Orthogonality makes its diagonal entries $\pm 1$, and positivity of the diagonals of $R_1,R_2$ forces $+1$. Hence $U=I$ and $\boxed{R_1=R_2}$.

Full column rank makes $B=A^{T}A$ positive definite: for nonzero $v$, $v^{T}Bv=\Vert Av{\Vert }^2>0$. Let $B=R^{T}R$ be its unique upper-triangular Cholesky decomposition with positive diagonal. Defining $Q=A{R}^{-1}$ givesThus the skinny QR decomposition exists. If $A=\tilde{Q}\tilde{R}$ is another such decomposition, orthonormality gives $A^{T}A={\tilde{R}}^T\tilde{R}$. Cholesky uniqueness forces $\tilde{R}=R$, and then $\tilde{Q}=A{R}^{-1}=Q$. Therefore the skinny factorization with positive diagonal is unique. This is the thin QR factorization from Cholesky decomposition; no inverse of the rectangular $Q$ is assumed.