Past exam of the mathematics course of the University of Cambridge / 2006 / ib / Paper 3 / 19D / a / Solution

A full QR decomposition of a real $m$ by $n$ matrix with $m\ge n$ writeswhere $Q$ is an orthogonal $m$ by $m$ matrix and $R$ is upper triangular $n$ by $n$. In the full-column-rank case $R$ is invertible. Equivalently the reduced factorization is $A=Q_{1}R$ with $Q_1^T{Q}_1=I_n$. Householder transformations can construct the full factorization.

Let $Q^{T}b=\left(\genfrac{}{}{0ex}{}{c_1}{c_2}\right)$ with $c_1\in {\mathbb{R}}^n$. Since orthogonal transformations preserve the Euclidean norm,Therefore the linear least-squares problem has the full-rank solutionBack substitution solves this triangular system without forming $A^{T}A$. If the matrix is rank deficient, use a rank-revealing pivoted factorization and minimize over its independent columns; the minimizer need not be unique. The original PDF minimizes over $x\in {\mathbb{R}}^n$; the converted TeX's minimization over $b$ is a transcription error.