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

A real singular value decomposition has the form $A=U\Sigma V^T$, where $U\in {\mathbb{R}}^{m\times m}$ and $V\in {\mathbb{R}}^{n\times n}$ are orthogonal matrices, and $\Sigma$ is a rectangular diagonal matrix with entries ${\sigma }_1\ge \cdots \ge {\sigma }_{\min (m,n)}\ge 0$. These entries are the singular values. Their squares are the eigenvalues of $A^{T}A$, omitting the additional zero eigenvalues when $n>m$. The positive singular values number exactly the matrix rank.

Use the singular value decomposition and the orthogonal invariance of the Euclidean norm. Put $z=V^{T}x$ and $c=U^{T}b$. Since precisely ${\sigma }_1,\dots ,{\sigma }_r$ are positive,The second sum is independent of $x$ and cannot be removed. The first sum vanishes exactly when $z_j=c_j/{\sigma }_j$ for $1\le j\le r$, while $z_{r+1},\dots ,z_n$ are arbitrary. Thus every least-squares solution isThe unavoidable linear-system residual is the component of $b$ orthogonal to the column space of $A$:The minimum-norm least-squares solution sets all ${\alpha }_j=0$ and equals $A^{+}b$, where $A^{+}$ is the Moore-Penrose inverse. The squared minimum, rather than the minimum itself, is the second sum in the first display.

Let $u_j$ and $v_j$ be the columns of the orthogonal matrices $U$ and $V$ in the singular value decomposition. Multiplying by the rectangular diagonal matrix retains its $r$ nonzero diagonal entries:The families $(u_j)$ and $(v_j)$ are orthonormal, hence in particular orthogonal. Each summand is a rank-one outer product, and the remaining terms vanish because their singular values are zero.

For the matrix's Euclidean operator norm, orthogonal invariance of the Euclidean norm givesTaking $x=v_1$ gives equality, so $\Vert A{\Vert }_2={\sigma }_1$. For the Frobenius norm, the trace identity and the singular value decomposition giveConsequentlyHere the Euclidean matrix norm means the operator norm induced by the vector Euclidean norm, rather than the entrywise Euclidean length, which is the Frobenius norm.

The two columns are orthogonal, with lengths one and two; equivalently $A^{T}A=\mathrm{diag}(1,4)$. Ordering the singular values decreasingly requires swapping the right coordinate directions. One full singular value decomposition isBoth $U$ and $V$ are orthogonal matrices, and direct matrix multiplication gives $U\Sigma V^T=A$. Hence