Past exam of the mathematics course of the University of Cambridge / 2013 / ib / Paper 1 / 18C / Solution

For a full-column-rank matrix, a thin QR decomposition has $A=Q_{1}R$, where $Q_1^T{Q}_1=I_n$ and $R$ is nonsingular upper triangular. Extend $Q_1$ to an orthogonal matrix $Q=(Q_1,Q_2)$. Orthogonality givesThus the unique least-squares solution satisfies $R{x}^{\ast }=Q_1^{T}b$, with residual norm $\Vert Q_2^{T}b\Vert$. In a rank-deficient problem $R$ is singular and uniqueness needs separate treatment.

A Givens rotation is the identity except for the rows/columns $p,q$, whose block is $\left(\begin{array}{cc}c& s\\ -s& c\end{array}\right)$ with $c^2+s^2=1$. Its transpose times itself has that block equal to the identity, so it is orthogonal. Choose $c=4/5,s=3/5$ in rows two and three. ThenBack substitution in the first three rows givesThe fourth row of the rotated residual is the unavoidable value $-2$, while the other three rows vanish. Thus this rotation also directly exhibits the least-squares optimality.