Past exam of the numerical linear algebra course of the University of Oxford / 2025 / 1 / a

The orthonormal columns give $A^{T}A=I_n$. Thus $P=A{A}^T$ is the orthogonal projection onto the column space of $A$, andThe two terms are orthogonal, so the Pythagorean identity givesOnly the first term depends on $x$. Consequently the linear least-squares problem has the unique answer

For every vector $z\in {\mathbb{R}}^n$, splitting the rows givesBoth summands are nonnegative. Taking the supremum over unit vectors in the definition of the spectral norm proves

Put $B=A_1^T{A}_1$. It is a symmetric matrix and a positive semidefinite matrix, while $A_2^T{A}_2=I_n-B$ is also a positive semidefinite matrix. By the spectral theorem, choose an orthogonal matrix $V=[v_1,\dots ,v_n]$ such thatThe bounds follow directly from $z^{T}Bz=\Vert A_{1}z{\Vert }_2^2\in [0,\Vert z{\Vert }_2^2]$. Define the diagonal matricesThe columns of $A_{1}V$ are mutually orthogonal, since $(A_1{v}_i{)}^T(A_1{v}_j)={\lambda }_j{\delta }_{ij}$. For each ${\lambda }_j>0$, set $u_{1j}=A_1{v}_j/\sqrt{{\lambda }_j}$. These columns are orthonormal. At a zero ${\lambda }_j$, one has $A_1{v}_j=0$; choose $u_{1j}$ by completing the already prescribed columns to an orthonormal set of $n$ columns in ${\mathbb{R}}^k$. Such a completion exists because $k\ge n$. This gives $A_{1}V=U_1{\Sigma }_1$, including the zero columns.

Likewise, the Gram matrix of $A_{2}V$ is $\mathrm{diag}(1-{\lambda }_j)$. Normalize its nonzero columns and complete at its zero columns in ${\mathbb{R}}^{m-k}$, using $m-k\ge n$. The resulting $U_2$ has orthonormal columns and $A_{2}V=U_2{\Sigma }_2$. Combining the identities givesThis is a form of the cosine-sine decomposition. Completing the zero columns is essential: neither block was assumed to have full column rank.

Using the orthonormal columns of $U_1,U_2$ in the factorization givesMultiplying by the orthogonal matrices $V^T$ and $V$ gives