Past exam of the numerical linear algebra and approximation course of the University of Oxford / 2008 / 1

A real square orthogonal matrix $Q$ satisfies $\boxed{Q^{T}Q=Q{Q}^T=I}$. Equivalently its columns form an orthonormal basis. In particular it preserves the Euclidean norm, since $\Vert Qx{\Vert }_2^2=x^T{Q}^{T}Qx=\Vert x{\Vert }_2^2$.

A Householder matrix has the formIt reflects in the hyperplane perpendicular to $v$. Put $P=v{v}^T/(v^{T}v)$, an orthogonal projector satisfying $P^T=P$ and $P^2=P$. Then $H^{T}H=(I-2P{)}^2=I-4P+4P^2=I$, proving that every Householder matrix is orthogonal.

If $x\ne 0$, choose $\alpha =-\mathrm{sgn}(x_1)\Vert x{\Vert }_2$, with $\mathrm{sgn}(0)=1$ for this choice, and put $v=x-\alpha e_1$. This nonzero vector satisfiesThus the Householder matrix $H=I-2v{v}^T/(v^{T}v)$ gives $Hx=x-v=\alpha e_1$. Symmetry gives $\boxed{x^{T}H=\alpha e_1^T}$. If $x=0$, any Householder matrix works with $\alpha =0$.

For an LQ decomposition, process rows $j=1,\dots ,\min (m,n)$. At step $j$, postmultiply by an orthogonal block matrix $H_j=\mathrm{diag}(I_{j-1},{\hat{H}}_j)$ that zeros entries to the right of the diagonal in the current row. If its row tail is already suitable, use the identity. Earlier processed rows have zero entries throughout this trailing block, so their zeros are preserved. Consequently $L=A{H}_1\cdots H_r$ has $l_{ij}=0$ for $i<j$. Setting $\boxed{Q=H_r^T\cdots H_1^T}$ gives $\boxed{A=LQ}$. The argument handles both rectangular shapes; $L$ is lower trapezoidal when it is not square.

The singular value decomposition $A=U\Sigma V^T$ givesTherefore $\boxed{{\sigma }_i(A)=\sqrt{{\lambda }_i(A^{T}A)}}$, counting multiplicities. These are the nonnegative square roots: zero singular values must be included if $A$ is singular. Strict positivity requires full rank, which the question does not assume.

Write the lower bidiagonal matrix entries as $B_{ii}=d_i$ and $B_{i+1,i}=e_i$. Its columns $i$ and $j$ have disjoint supports if $|i-j|>1$, so $T=B^{T}B$ has no entries outside the three central diagonals. More explicitly,This proves both symmetry and the tridiagonal matrix structure.

A generic lower triangular matrix has a dense first column. The first left Householder transformation in its QR decomposition mixes those rows, usually creating entries throughout the rows to the right. Subsequent eliminations impose upper triangularity but no further systematic zeros; thus $R$ is generically a full upper triangular matrix.

For Householder bidiagonalization use two-sided operations instead. At stage $j$, a right Householder transformation acting on columns $j,\dots ,n$ clears the current row $j$ beyond its diagonal. Then a left Householder transformation acting on rows $j+1,\dots ,n$ clears column $j$ below its first subdiagonal. The left operation leaves row $j$ unchanged; both operations preserve the already completed lower-bidiagonal rows and columns. Continue for $j=1,\dots ,n-1$, omitting a final unnecessary left operation. The result isIt follows that $B^{T}B=Q^T{A}^{T}AQ$. Hence the two symmetric matrices are orthogonally similar and have the same eigenvalues. By part (c), compute the eigenvalues of the symmetric tridiagonal matrix $B^{T}B$ and take their nonnegative square roots to obtain all singular values of $A$.