Past exam of the mathematics course of the University of Cambridge / 2016 / ib / Paper 2 / 19D / b / Solution

A QR decomposition of an $m\times n$ matrix, $m\ge n$, is $A=QR$, where $Q$ is an $m\times m$ orthogonal matrix and $R$ is $m\times n$ and upper trapezoidal: $R_{ij}=0$ for $i>j$. In particular its bottom $m-n$ rows vanish.

Successive left Givens rotations annihilate the entries below the diagonal, column by column. When working on column $j$, rotate rows $j$ and $i>j$; their earlier columns are already zero, so the earlier eliminations persist. If $G_k\cdots G_{1}A=R$, thenA product of orthogonal matrices is orthogonal. The construction remains valid for a rank-deficient matrix, although uniqueness is not asserted. This is QR decomposition by Givens rotations.