Past exam of the year 1 of the computer science course of the University of Oxford / 2018 / Digital systems, linear algebra, introduction to formal proof / 6 / a

For independent columns $a_1,\dots ,a_k$ in a real inner product space, the Gram-Schmidt process recursively formsEach $u_j$ subtracts the orthogonal projections onto earlier normalized vectors. Their independence ensures $u_j\ne 0$. The resulting $q_i$ are orthonormal and preserve the span of every initial column set. Putting $Q=(q_1\cdots q_k)$ and $r_{ij}=⟨q_i,a_j⟩$ for $i\le j$, with zeros below the diagonal, gives a QR decomposition $A=QR$ with $Q^{T}Q=I$. Dependent input columns require omitting a zero residual or treating rank deficiency separately.

The first column has norm two, giving $q_1=(1,-1,1,-1{)}^T/2$. Its inner products with the second and third columns are both one. Subtracting $q_1$ from the second column leaves $(3,3,3,3{)}^T/2$, of norm three, so $q_2=(1,1,1,1{)}^T/2$. The inner product of $q_2$ with the third column is one. Subtracting $q_1+q_2$ from that column leaves $(1,1,-1,-1{)}^T$, of norm two. Thus the Gram-Schmidt process givesThe columns of $Q$ have unit norm and pairwise zero inner products, so $Q^{T}Q=I_3$. Direct multiplication verifies $QR=A$.