Print this page and work through it on paper. Revealed answers are never printed, so you can check one question and still print a clean sheet.

1. 1.Computation · 6 min

   Find the singular values of each matrix exactly. In each case say which Gram matrix you diagonalised and why that one, and give one independent arithmetic check on your answer (a trace identity or a determinant identity).

   1. (a)$A=\left(\begin{array}{cc}1& 1\\ -1& 1\end{array}\right)$. What does $A$ do to the unit circle?
   2. (b)$B=\left(\begin{array}{cc}1& 2\\ 0& 1\end{array}\right)$. Compare the singular values with the eigenvalues of $B$ and comment.
   3. (c)$C=\left(\begin{array}{cc}1& 2\\ 2& 4\\ 2& 4\end{array}\right)$. Explain, before computing anything, how many singular values must be zero.
   Show the solution to question 1

   (a) Diagonalise $A^{T}A$. Both Gram matrices are $2\times 2$, so either will do; take $A^{T}A$:

   $$A^{T}A=\left(\begin{array}{cc}1& -1\\ 1& 1\end{array}\right)\left(\begin{array}{cc}1& 1\\ -1& 1\end{array}\right)=\left(\begin{array}{cc}2& 0\\ 0& 2\end{array}\right).$$

   Both eigenvalues are $2$, so ${\sigma }_1={\sigma }_2=\sqrt{2}$. Every direction is stretched by the same factor: indeed $\frac{1}{\sqrt{2}}A$ is the rotation matrix through $-45^{\circ }$, so $A$ is $\sqrt{2}$ times a rotation and sends the unit circle to a circle of radius $\sqrt{2}$. Check: ${\sigma }_1{\sigma }_2=2=|\det A|=|1\cdot 1-1\cdot (-1)|$. ✓

   (b) A shear. $B^{T}B=\left(\begin{array}{cc}1& 0\\ 2& 1\end{array}\right)\left(\begin{array}{cc}1& 2\\ 0& 1\end{array}\right)=\left(\begin{array}{cc}1& 2\\ 2& 5\end{array}\right)$, with trace $6$ and determinant $1$, so the characteristic polynomial is ${\lambda }^2-6\lambda +1$ and

   $$\lambda =3\pm 2\sqrt{2}=(\sqrt{2}\pm 1{)}^2.$$

   Hence ${\sigma }_1=\sqrt{2}+1$ and ${\sigma }_2=\sqrt{2}-1$. Two checks: ${\sigma }_1{\sigma }_2=2-1=1=|\det B|$ ✓, and ${\sigma }_1^2+{\sigma }_2^2=(3+2\sqrt{2})+(3-2\sqrt{2})=6=1^2+2^2+0^2+1^2=\mathrm{tr}(B^{T}B)$ ✓.

   Note that both eigenvalues of $B$ are $1$, while its singular values are about $2.41$ and $0.41$. Singular values are the absolute eigenvalues only for symmetric matrices, and a shear is the standard counterexample.

   (c) Rank one, so only one singular value is nonzero. $C$ is $3\times 2$, so $C^{T}C$ is $2\times 2$ and is the smaller Gram matrix:

   $$C^{T}C=\left(\begin{array}{ccc}1& 2& 2\\ 2& 4& 4\end{array}\right)\left(\begin{array}{cc}1& 2\\ 2& 4\\ 2& 4\end{array}\right)=\left(\begin{array}{cc}9& 18\\ 18& 36\end{array}\right).$$

   Its determinant is $324-324=0$ and its trace is $45$, so the eigenvalues are $45$ and $0$: ${\sigma }_1=\sqrt{45}=3\sqrt{5}$, ${\sigma }_2=0$. This had to happen: the second column of $C$ is twice the first, so $\mathrm{rank}C=1$ and exactly one singular value is nonzero. Check: ${\sigma }_1^2=45=1+4+4+16+4+16$, the sum of the squares of all six entries. ✓

2. 2.Sketch · 7 min

   Let $A=\left(\begin{array}{cc}2& 1\\ -2& 1\end{array}\right)$. A sketch with no singular values written beside it earns nothing here: every feature you draw must be justified by a computation.

   1. (a)Find the singular values and the right singular vectors of $A$. Explain why, for this particular matrix, the images of ${\mathbf{e}}_1$ and ${\mathbf{e}}_2$ are the semi-axes of the image ellipse, and find the unit vectors ${\mathbf{u}}_1,{\mathbf{u}}_2$ along those axes.
   2. (b)On one pair of axes sketch the unit circle and its image under $A$. Mark ${\mathbf{e}}_1$ and ${\mathbf{e}}_2$ on the circle and their images on the ellipse, draw both axes of the ellipse, and state whether $A$ preserves or reverses orientation and how you know.
   3. (c)Verify that the image of $\mathbf{w}=\frac{1}{\sqrt{2}}(1,1)$ lies on your ellipse by writing $A\mathbf{w}$ in the frame $\{{\mathbf{u}}_1,{\mathbf{u}}_2\}$ and checking the ellipse equation, and check the area of the ellipse against $|\det A|$.
   Show the solution to question 2

   (a) Singular values and right singular vectors.

   $$A^{T}A=\left(\begin{array}{cc}2& -2\\ 1& 1\end{array}\right)\left(\begin{array}{cc}2& 1\\ -2& 1\end{array}\right)=\left(\begin{array}{cc}8& 0\\ 0& 2\end{array}\right).$$

   The Gram matrix is already diagonal, so its unit eigenvectors are ${\mathbf{v}}_1={\mathbf{e}}_1$ (eigenvalue $8$) and ${\mathbf{v}}_2={\mathbf{e}}_2$ (eigenvalue $2$), and ${\sigma }_1=2\sqrt{2}$, ${\sigma }_2=\sqrt{2}$. By the ellipsoid theorem the semi-axes of the image ellipse are $A{\mathbf{v}}_i$, and here those are the images of the standard basis vectors: $A{\mathbf{e}}_1=(2,-2)$, of length $2\sqrt{2}={\sigma }_1$ ✓, and $A{\mathbf{e}}_2=(1,1)$, of length $\sqrt{2}={\sigma }_2$ ✓. The axis directions are ${\mathbf{u}}_1=A{\mathbf{v}}_1/{\sigma }_1=\frac{1}{\sqrt{2}}(1,-1)$ and ${\mathbf{u}}_2=A{\mathbf{v}}_2/{\sigma }_2=\frac{1}{\sqrt{2}}(1,1)$, which are perpendicular, as they must be.

   (b) The sketch. On one set of axes draw the unit circle and, on it, the points ${\mathbf{e}}_1=(1,0)$ and ${\mathbf{e}}_2=(0,1)$. The image is an ellipse centred at the origin, tilted $45^{\circ }$: its long axis runs along the line $y=-x$ and ends at $\pm (2,-2)$, its short axis runs along $y=x$ and ends at $\pm (1,1)$. Mark $(2,-2)$ as the image of ${\mathbf{e}}_1$ and $(1,1)$ as the image of ${\mathbf{e}}_2$, and draw both axes of the ellipse as dashed lines through the origin. The ellipse should enclose the circle without touching it: the smallest stretch is ${\sigma }_2=\sqrt{2}>1$, so every point of the circle is pushed outward. Finally, since $\det A=2+2=4>0$, orientation is preserved: travelling counterclockwise from ${\mathbf{e}}_1$ to ${\mathbf{e}}_2$ on the circle corresponds to travelling counterclockwise from $(2,-2)$ (at angle $-45^{\circ }$) to $(1,1)$ (at angle $45^{\circ }$) on the ellipse.

   (c) Two checks. For $\mathbf{w}=\frac{1}{\sqrt{2}}(1,1)$, $A\mathbf{w}=\frac{1}{\sqrt{2}}(3,-1)$. Its coordinates in the frame $\{{\mathbf{u}}_1,{\mathbf{u}}_2\}$ are

   $$y_1=A\mathbf{w}\cdot {\mathbf{u}}_1=\frac{1}{2}(3\cdot 1+(-1)(-1))=2,y_2=A\mathbf{w}\cdot {\mathbf{u}}_2=\frac{1}{2}(3-1)=1,$$

   and $\frac{y_1^2}{{\sigma }_1^2}+\frac{y_2^2}{{\sigma }_2^2}=\frac{4}{8}+\frac{1}{2}=1$, so $A\mathbf{w}$ lies on the ellipse ✓ (plot it at roughly $(2.1,-0.7)$). Area: $\pi {\sigma }_1{\sigma }_2=\pi \cdot 2\sqrt{2}\cdot \sqrt{2}=4\pi$, and the unit disc's area $\pi$ scaled by $|\det A|=4$ is also $4\pi$ ✓.

3. 3.Computation · 10 min

   Let $A=\left(\begin{array}{cc}2& 1\\ 1& 2\\ 1& 1\end{array}\right)$. Compute a full SVD $A=U\Sigma V^T$ by hand. State the size of each factor before you start.

   1. (a)Find the singular values and an orthonormal set of right singular vectors, and write down $V$.
   2. (b)Find ${\mathbf{u}}_1$ and ${\mathbf{u}}_2$ from the right singular vectors, then find the remaining column of $U$. Explain why that last column cannot come from the same formula as the first two, and check it is orthogonal to both.
   3. (c)Write down $U$, $\Sigma$ and $V$ with their correct shapes, verify two entries of $U\Sigma V^T$ against $A$, and write $A$ in outer product form.
   Show the solution to question 3

   Sizes. $A$ is $3\times 2$, so $U$ is $3\times 3$, $\Sigma$ is $3\times 2$ and $V$ is $2\times 2$.

   (a) Singular values and $V$. The smaller Gram matrix is $A^{T}A$ ($2\times 2$):

   $$A^{T}A=\left(\begin{array}{ccc}2& 1& 1\\ 1& 2& 1\end{array}\right)\left(\begin{array}{cc}2& 1\\ 1& 2\\ 1& 1\end{array}\right)=\left(\begin{array}{cc}6& 5\\ 5& 6\end{array}\right).$$

   Trace $12$, determinant $36-25=11$, so ${\lambda }^2-12\lambda +11=(\lambda -11)(\lambda -1)$: ${\lambda }_1=11$, ${\lambda }_2=1$, and ${\sigma }_1=\sqrt{11}$, ${\sigma }_2=1$. Both are nonzero, so $r=2$: full column rank.

   For $\lambda =11$, $A^{T}A-11I=\left(\begin{array}{cc}-5& 5\\ 5& -5\end{array}\right)$ forces $x=y$, so ${\mathbf{v}}_1=\frac{1}{\sqrt{2}}(1,1)$. For $\lambda =1$, $\left(\begin{array}{cc}5& 5\\ 5& 5\end{array}\right)$ forces $x=-y$, so ${\mathbf{v}}_2=\frac{1}{\sqrt{2}}(1,-1)$. Thus $V=\frac{1}{\sqrt{2}}\left(\begin{array}{cc}1& 1\\ 1& -1\end{array}\right)$. Check: ${\sigma }_1^2+{\sigma }_2^2=12=4+1+1+4+1+1$, the sum of squared entries of $A$. ✓

   (b) Left singular vectors from the formula, then one from the null space.

   $${\mathbf{u}}_1=\frac{A{\mathbf{v}}_1}{{\sigma }_1}=\frac{1}{\sqrt{11}}\cdot \frac{1}{\sqrt{2}}\left(\begin{array}{c}3\\ 3\\ 2\end{array}\right)=\frac{1}{\sqrt{22}}\left(\begin{array}{c}3\\ 3\\ 2\end{array}\right),{\mathbf{u}}_2=\frac{A{\mathbf{v}}_2}{{\sigma }_2}=\frac{1}{\sqrt{2}}\left(\begin{array}{c}1\\ -1\\ 0\end{array}\right).$$

   (Norm check on ${\mathbf{u}}_1$: $9+9+4=22$ ✓.) The formula ${\mathbf{u}}_i=A{\mathbf{v}}_i/{\sigma }_i$ produces only $r=2$ vectors, and there is no ${\mathbf{v}}_3$ at all, since $V$ is $2\times 2$; the third column of $U$ carries no information about $A$ beyond being orthogonal to the first two, which is exactly the statement that it spans $\mathrm{Null}{A}^T$. Solve $A^T\mathbf{u}=0$:

   $$2x+y+z=0,x+2y+z=0.$$

   Subtracting gives $x=y$, and then $3x+z=0$, so $z=-3x$: ${\mathbf{u}}_3=\frac{1}{\sqrt{11}}(1,1,-3)$. Orthogonality check: ${\mathbf{u}}_1\cdot {\mathbf{u}}_3\propto 3+3-6=0$ ✓ and ${\mathbf{u}}_2\cdot {\mathbf{u}}_3\propto 1-1+0=0$ ✓.

   (c) Assemble, check, reduce. $\Sigma$ has the shape of $A$, a $2\times 2$ diagonal block with a zero row beneath:

   $$U=\left(\begin{array}{ccc}3/\sqrt{22}& 1/\sqrt{2}& 1/\sqrt{11}\\ 3/\sqrt{22}& -1/\sqrt{2}& 1/\sqrt{11}\\ 2/\sqrt{22}& 0& -3/\sqrt{11}\end{array}\right),\Sigma =\left(\begin{array}{cc}\sqrt{11}& 0\\ 0& 1\\ 0& 0\end{array}\right),V=\frac{1}{\sqrt{2}}\left(\begin{array}{cc}1& 1\\ 1& -1\end{array}\right).$$

   Entry $(1,1)$ of $U\Sigma V^T$ is ${\sum }_i{\sigma }_i{u}_{1i}{v}_{1i}=\sqrt{11}\cdot \frac{3}{\sqrt{22}}\cdot \frac{1}{\sqrt{2}}+1\cdot \frac{1}{\sqrt{2}}\cdot \frac{1}{\sqrt{2}}=\frac{3}{2}+\frac{1}{2}=2=A_{11}$ ✓. Entry $(3,2)$ is $\sqrt{11}\cdot \frac{2}{\sqrt{22}}\cdot \frac{1}{\sqrt{2}}+1\cdot 0\cdot (-\frac{1}{\sqrt{2}})=1=A_{32}$ ✓.

   The reduced SVD drops ${\mathbf{u}}_3$ and the zero row of $\Sigma$; in outer product form,

   $$A=\sqrt{11}{\mathbf{u}}_1{\mathbf{v}}_1^T+1\cdot {\mathbf{u}}_2{\mathbf{v}}_2^T=\frac{1}{2}\left(\begin{array}{cc}3& 3\\ 3& 3\\ 2& 2\end{array}\right)+\frac{1}{2}\left(\begin{array}{cc}1& -1\\ -1& 1\\ 0& 0\end{array}\right)=\left(\begin{array}{cc}2& 1\\ 1& 2\\ 1& 1\end{array}\right)=A.✓$$

4. 4.Computation · 7 min

   A $3\times 4$ matrix is given in outer product form,

   $$A=3{\mathbf{u}}_1{\mathbf{v}}_1^T+{\mathbf{u}}_2{\mathbf{v}}_2^T,{\mathbf{u}}_1=\frac{1}{3}\left(\begin{array}{c}1\\ 2\\ 2\end{array}\right),{\mathbf{u}}_2=\frac{1}{3}\left(\begin{array}{c}2\\ 1\\ -2\end{array}\right),{\mathbf{v}}_1=\frac{1}{2}\left(\begin{array}{c}1\\ 1\\ 1\\ 1\end{array}\right),{\mathbf{v}}_2=\frac{1}{2}\left(\begin{array}{c}1\\ -1\\ 1\\ -1\end{array}\right).$$

   Do not multiply out the entries of $A$ at any point; everything asked can be read off the factorisation.

   1. (a)State $\mathrm{rank}A$ and the dimension of each of the four fundamental subspaces, and write down orthonormal bases for $\mathrm{Col}A$ and $\mathrm{Row}A$. Say what you checked to be sure the given expression is a legitimate SVD.
   2. (b)Find orthonormal bases for $\mathrm{Null}{A}^T$ and $\mathrm{Null}A$.
   3. (c)Compute $A\mathbf{x}$ for $\mathbf{x}=(1,1,1,1)$ and for $\mathbf{x}=(1,0,-1,0)$. Then decide whether $A\mathbf{y}=\mathbf{b}$ is solvable for $\mathbf{b}=(0,0,3)$ and for $\mathbf{b}=(3,6,6)$, giving a solution when one exists.
   Show the solution to question 4

   (a) Dimensions and the two easy bases. First confirm this really is an SVD in outer product form: ${\mathbf{u}}_1\cdot {\mathbf{u}}_2=\frac{1}{9}(2+2-4)=0$, ${\mathbf{v}}_1\cdot {\mathbf{v}}_2=\frac{1}{4}(1-1+1-1)=0$, and all four vectors have unit length ($\frac{1}{9}(1+4+4)=1$, $\frac{1}{9}(4+1+4)=1$, $\frac{1}{4}\cdot 4=1$). The weights $3>1>0$ are decreasing, so ${\sigma }_1=3$, ${\sigma }_2=1$ and $\mathrm{rank}A=2$.

   By the four-subspaces theorem: $\mathrm{Col}A=\mathrm{span}\{{\mathbf{u}}_1,{\mathbf{u}}_2\}\subseteq {\mathbb{R}}^3$ has dimension $2$; $\mathrm{Null}{A}^T$ has dimension $m-r=1$; $\mathrm{Row}A=\mathrm{span}\{{\mathbf{v}}_1,{\mathbf{v}}_2\}\subseteq {\mathbb{R}}^4$ has dimension $2$; $\mathrm{Null}A$ has dimension $n-r=2$. The listed $\mathbf{u}$'s and $\mathbf{v}$'s are already orthonormal bases of the column and row spaces.

   (b) The two null spaces. $\mathrm{Null}{A}^T$ is the orthogonal complement of $\mathrm{Col}A$ in ${\mathbb{R}}^3$, so it is spanned by any vector perpendicular to ${\mathbf{u}}_1$ and ${\mathbf{u}}_2$; the cross product $(1,2,2)\times (2,1,-2)=(-4-2,4+2,1-4)=(-6,6,-3)$ works, and normalising gives

   $${\mathbf{u}}_3=\frac{1}{3}(2,-2,1).$$

   Check: ${\mathbf{u}}_1\cdot {\mathbf{u}}_3=\frac{1}{9}(2-4+2)=0$ ✓, ${\mathbf{u}}_2\cdot {\mathbf{u}}_3=\frac{1}{9}(4-2-2)=0$ ✓.

   $\mathrm{Null}A$ is the orthogonal complement of $\mathrm{Row}A$ in ${\mathbb{R}}^4$: $\mathbf{x}\perp {\mathbf{v}}_1,{\mathbf{v}}_2$ means $x_1+x_2+x_3+x_4=0$ and $x_1-x_2+x_3-x_4=0$. Adding and subtracting, $x_1+x_3=0$ and $x_2+x_4=0$, so

   $${\mathbf{v}}_3=\frac{1}{\sqrt{2}}(1,0,-1,0),{\mathbf{v}}_4=\frac{1}{\sqrt{2}}(0,1,0,-1),$$

   which are orthogonal to each other and to ${\mathbf{v}}_1,{\mathbf{v}}_2$ ✓. (Any orthonormal basis of this plane is acceptable — it is the repeated singular value $0$ leaving the choice free.)

   (c) Using the factorisation directly. $\mathbf{x}=(1,1,1,1)=2{\mathbf{v}}_1$, and ${\mathbf{v}}_1\perp {\mathbf{v}}_2$, so

   $$A\mathbf{x}=2(3{\mathbf{u}}_1({\mathbf{v}}_1^T{\mathbf{v}}_1)+{\mathbf{u}}_2({\mathbf{v}}_2^T{\mathbf{v}}_1))=6{\mathbf{u}}_1=(2,4,4).$$

   $\mathbf{x}=(1,0,-1,0)=\sqrt{2}{\mathbf{v}}_3$ lies in $\mathrm{Null}A$, so $A\mathbf{x}=0$: both ${\mathbf{v}}_1^T\mathbf{x}$ and ${\mathbf{v}}_2^T\mathbf{x}$ vanish.

   $A\mathbf{y}=\mathbf{b}$ is solvable exactly when $\mathbf{b}\in \mathrm{Col}A$, i.e. when $\mathbf{b}\perp \mathrm{Null}{A}^T$, because $\mathrm{Col}A=(\mathrm{Null}{A}^T{)}^{\perp }$. For $\mathbf{b}=(0,0,3)$: $\mathbf{b}\cdot {\mathbf{u}}_3=3\cdot \frac{1}{3}=1\ne 0$, so no solution exists. For $\mathbf{b}=(3,6,6)=9{\mathbf{u}}_1$: it lies in $\mathrm{Col}A$, and since $A{\mathbf{v}}_1=3{\mathbf{u}}_1$, the vector $\mathbf{y}=3{\mathbf{v}}_1=\frac{3}{2}(1,1,1,1)$ is a solution. It is not the only one — add anything in $\mathrm{Null}A$ — but it is the one of smallest norm, being the one in $\mathrm{Row}A$.

5. 5.Proof · 9 min

   Let $A$ be a real $m\times n$ matrix of rank $r$ with singular values ${\sigma }_1\ge \cdots \ge {\sigma }_r>0$. You may quote $\Vert A{\Vert }_2={\sigma }_1$, $\Vert A{\Vert }_F^2={\sigma }_1^2+\cdots +{\sigma }_r^2$, and the definition of the spectral norm as a maximum of $\Vert A\mathbf{x}\Vert /\Vert \mathbf{x}\Vert$.

   1. (a)Prove that $\Vert A{\Vert }_2\le \Vert A{\Vert }_F\le \sqrt{r}\Vert A{\Vert }_2$, and determine exactly which matrices make each inequality an equality.
   2. (b)Prove from the definition that $\Vert AB{\Vert }_2\le \Vert A{\Vert }_2\Vert B{\Vert }_2$ whenever the product is defined, and give a $2\times 2$ example in which the inequality is strict.
   3. (c)Prove that an $n\times n$ matrix is orthogonal if and only if all $n$ of its singular values equal $1$. Deduce $\Vert Q{\Vert }_2$ and $\Vert Q{\Vert }_F$ for an orthogonal $Q$, and give an example showing that $\Vert A{\Vert }_2=1$ alone does not make $A$ orthogonal.
   Show the solution to question 5

   (a) The sandwich. Every ${\sigma }_i^2$ is positive, so

   $$\Vert A{\Vert }_2^2={\sigma }_1^2\le {\sigma }_1^2+{\sigma }_2^2+\cdots +{\sigma }_r^2=\Vert A{\Vert }_F^2,$$

   and since ${\sigma }_i\le {\sigma }_1$ for each $i$,

   $$\Vert A{\Vert }_F^2=\sum _{i=1}^r{\sigma }_i^2\le r{\sigma }_1^2=r\Vert A{\Vert }_2^2.$$

   Taking square roots gives $\Vert A{\Vert }_2\le \Vert A{\Vert }_F\le \sqrt{r}\Vert A{\Vert }_2$. The left inequality is an equality exactly when ${\sigma }_2^2+\cdots +{\sigma }_r^2=0$, i.e. when $r\le 1$: rank-one matrices and the zero matrix. The right inequality is an equality exactly when ${\sigma }_i={\sigma }_1$ for every $i\le r$: all nonzero singular values equal. Orthogonal matrices, and more generally scalar multiples of matrices with orthonormal columns, are the examples. $■$

   (b) Submultiplicativity. The definition of $\Vert A{\Vert }_2$ as a maximum gives $\Vert A\mathbf{y}\Vert \le \Vert A{\Vert }_2\Vert \mathbf{y}\Vert$ for every $\mathbf{y}$ (trivially when $\mathbf{y}=0$). Apply it twice: for any $\mathbf{x}\ne 0$,

   $$\Vert AB\mathbf{x}\Vert =\Vert A(B\mathbf{x})\Vert \le \Vert A{\Vert }_2\Vert B\mathbf{x}\Vert \le \Vert A{\Vert }_2\Vert B{\Vert }_2\Vert \mathbf{x}\Vert .$$

   Divide by $\Vert \mathbf{x}\Vert$ and take the maximum over $\mathbf{x}$: $\Vert AB{\Vert }_2\le \Vert A{\Vert }_2\Vert B{\Vert }_2$. $■$

   Strictness: $A=\mathrm{diag}(1,0)$ and $B=\mathrm{diag}(0,1)$ each have spectral norm $1$, but $AB=0$ has norm $0<1\cdot 1$. The direction $B$ stretches most is the direction $A$ kills.

   (c) Orthogonal matrices are exactly the matrices with all singular values $1$. If $Q$ is orthogonal then $Q^{T}Q=I_n$, whose eigenvalues are all $1$, so every singular value of $Q$ is $\sqrt{1}=1$. Conversely, if $A$ is $n\times n$ with all $n$ singular values equal to $1$, then $r=n$ and $\Sigma =I_n$, so the SVD reads $A=U{I}_n{V}^T=U{V}^T$, a product of orthogonal matrices and hence orthogonal ($(U{V}^T{)}^T(U{V}^T)=V{U}^{T}U{V}^T=V{V}^T=I$). $■$

   Consequently $\Vert Q{\Vert }_2=1$ and $\Vert Q{\Vert }_F=\sqrt{1+\cdots +1}=\sqrt{n}$, which is the right-hand equality case of (a) with $r=n$. The converse of the first claim fails: $A=\mathrm{diag}(1,0)$ has $\Vert A{\Vert }_2={\sigma }_1=1$ but is singular. The spectral norm reports only the largest stretch and is silent about the others; orthogonality is a statement about all of them.

6. 6.Computation · 9 min

   Condition numbers throughout are in the $2$-norm, $\kappa (A)={\sigma }_1/{\sigma }_n$. Give every value exactly.

   1. (a)Find $\kappa (B)$ for the shear $B=\left(\begin{array}{cc}1& 2\\ 0& 1\end{array}\right)$, and use the rule of thumb to say how many decimal digits solving $B\mathbf{x}=\mathbf{b}$ can lose. Cross-check your value against $\Vert B{\Vert }_2\Vert B^{-1}{\Vert }_2$.
   2. (b)Let $A$ be invertible. Prove that $\kappa (A^{T}A)=\kappa (A{)}^2$ and $\kappa (A^{-1})=\kappa (A)$, and state the practical consequence of the first identity for solving least-squares problems through the normal equations.
   3. (c)Compute $\kappa (E)$ and $\kappa (D)$ for $E=\left(\begin{array}{cc}1& 0.999\\ 0.999& 1\end{array}\right)$ and $D=1000I_2$, compare each with its determinant, and explain what the comparison shows. Then exhibit a $\mathbf{b}$ and a $\delta \mathbf{b}$ for which the error amplification bound for $E$ is attained exactly, showing the ratio.
   Show the solution to question 6

   (a) The shear. $B^{T}B=\left(\begin{array}{cc}1& 2\\ 2& 5\end{array}\right)$ has eigenvalues $3\pm 2\sqrt{2}=(\sqrt{2}\pm 1{)}^2$, so ${\sigma }_1=\sqrt{2}+1$ and ${\sigma }_2=\sqrt{2}-1$ and

   $$\kappa (B)=\frac{\sqrt{2}+1}{\sqrt{2}-1}=\frac{(\sqrt{2}+1{)}^2}{(\sqrt{2}-1)(\sqrt{2}+1)}=(\sqrt{2}+1{)}^2=3+2\sqrt{2}\approx \mathrm{5.83.}$$

   The rule of thumb says a condition number near $10^k$ costs about $k$ digits; ${\log }_{10}5.83\approx 0.77$, so solving $B\mathbf{x}=\mathbf{b}$ loses less than one decimal digit. Cross-check: $\Vert B^{-1}{\Vert }_2=1/{\sigma }_2=\sqrt{2}+1$, and indeed $B^{-1}=\left(\begin{array}{cc}1& -2\\ 0& 1\end{array}\right)$ is another shear with the same Gram eigenvalues, so $\Vert B{\Vert }_2\Vert B^{-1}{\Vert }_2=(\sqrt{2}+1{)}^2$ ✓.

   (b) Squaring and inverting. From $A=U\Sigma V^T$, $A^{T}A=V{\Sigma }^T\Sigma V^T=V{\Sigma }_n^2{V}^T$, which is an orthogonal diagonalisation of a symmetric positive definite matrix; its eigenvalues ${\sigma }_i^2$ are positive, and for a symmetric positive definite matrix the eigenvalues are the singular values (the orthogonal diagonalisation is itself an SVD). Hence

   $$\kappa (A^{T}A)=\frac{{\sigma }_1^2}{{\sigma }_n^2}=\kappa (A{)}^2.$$

   Likewise $A^{-1}=V{\Sigma }^{-1}{U}^T$ is an SVD of $A^{-1}$ up to reordering, with singular values $1/{\sigma }_n\ge \cdots \ge 1/{\sigma }_1$, so $\kappa (A^{-1})=\frac{1/{\sigma }_n}{1/{\sigma }_1}=\kappa (A)$. Practical consequence: forming the normal equations $A^{T}A\mathbf{x}=A^T\mathbf{b}$ to solve a least-squares problem squares the condition number, so a matrix that loses $4$ digits loses $8$ once squared. This is why least-squares software works with $A$ directly (via QR or the SVD) rather than with $A^{T}A$.

   (c) Determinant versus conditioning, and attainment. $E$ is symmetric with eigenvalues $1\pm 0.999$, namely $1.999$ and $0.001$, both positive, so those are its singular values and

   $$\kappa (E)=\frac{1.999}{0.001}=1999,\det E=1-0.999^2=\mathrm{0.001999.}$$

   $D=1000I$ has both singular values $1000$, so $\kappa (D)=1$ while $\det D=10^6$. The larger determinant belongs to the perfectly conditioned matrix and the tiny determinant to the badly conditioned one, but that is a coincidence of scale, not a rule: $\frac{1}{1000}I$ has determinant $10^{-6}$ and is also perfectly conditioned. The determinant is the product of the singular values and confuses overall size with the spread between directions; the condition number is a ratio and sees only the spread. Solving $E\mathbf{x}=\mathbf{b}$ can lose about ${\log }_{10}1999\approx 3.3$ digits.

   Attainment: the eigenvectors of $E$ are $\frac{1}{\sqrt{2}}(1,1)$ for $1.999$ and $\frac{1}{\sqrt{2}}(1,-1)$ for $0.001$, and for a symmetric positive definite matrix these serve as both left and right singular vectors. Take $\mathbf{b}=(1,1)$, so $\mathbf{x}=E^{-1}\mathbf{b}=\frac{1}{1.999}(1,1)$, and perturb along the weak direction, $\delta \mathbf{b}=(t,-t)$, so $\delta \mathbf{x}=E^{-1}\delta \mathbf{b}=\frac{1}{0.001}(t,-t)=1000(t,-t)$. Then

   $$\frac{\Vert \delta \mathbf{x}\Vert }{\Vert \mathbf{x}\Vert }=\frac{1000t\sqrt{2}}{\sqrt{2}/1.999}=1999t,\frac{\Vert \delta \mathbf{b}\Vert }{\Vert \mathbf{b}\Vert }=\frac{t\sqrt{2}}{\sqrt{2}}=t,$$

   so the ratio is exactly $1999=\kappa (E)$ ✓. With $t=0.001$, a $0.1\%$ error in $\mathbf{b}$ becomes a $199.9\%$ error in $\mathbf{x}$: the computed solution is worse than useless.

7. 7.Computation · 8 min

   The matrix $A=\left(\begin{array}{cc}2& 1\\ 1& 2\\ 1& 1\end{array}\right)$ has singular values ${\sigma }_1=\sqrt{11}$, ${\sigma }_2=1$, with ${\mathbf{u}}_1=\frac{1}{\sqrt{22}}(3,3,2)$, ${\mathbf{v}}_1=\frac{1}{\sqrt{2}}(1,1)$, ${\mathbf{u}}_2=\frac{1}{\sqrt{2}}(1,-1,0)$ and ${\mathbf{v}}_2=\frac{1}{\sqrt{2}}(1,-1)$. (You may take these as given, or check them.)

   1. (a)Write down the best rank-one approximation $A_1$, verify directly that it has rank one, compute $A-A_1$, and find $\Vert A-A_1{\Vert }_2$ and $\Vert A-A_1{\Vert }_F$ both from the singular values and directly from the entries.
   2. (b)A student proposes instead $B=\left(\begin{array}{cc}2& 1\\ 0& 0\\ 0& 0\end{array}\right)$, arguing that keeping the largest row is a rank-one approximation. Compute $\Vert A-B{\Vert }_F$ and a lower bound for $\Vert A-B{\Vert }_2$, compare with (a), and name the theorem that guarantees the outcome.
   3. (c)A $40\times 30$ matrix has singular values $8,6,3,2,1$ and all others zero. Find the smallest $k$ for which $A_k$ retains at least $90\%$ of $\Vert A{\Vert }_F^2$, give $\Vert A-A_k\Vert$ in both norms for that $k$, and compare the storage of $A_k$ with that of the full matrix.
   Show the solution to question 7

   (a) The truncation.

   $$A_1={\sigma }_1{\mathbf{u}}_1{\mathbf{v}}_1^T=\sqrt{11}\cdot \frac{1}{\sqrt{22}}\left(\begin{array}{c}3\\ 3\\ 2\end{array}\right)\cdot \frac{1}{\sqrt{2}}\left(\begin{array}{cc}1& 1\end{array}\right)=\frac{\sqrt{11}}{\sqrt{44}}\left(\begin{array}{cc}3& 3\\ 3& 3\\ 2& 2\end{array}\right)=\frac{1}{2}\left(\begin{array}{cc}3& 3\\ 3& 3\\ 2& 2\end{array}\right),$$

   since $\sqrt{44}=2\sqrt{11}$. Its rank is one (every column is a multiple of $(3,3,2)$). The error is

   $$A-A_1=\left(\begin{array}{cc}1/2& -1/2\\ -1/2& 1/2\\ 0& 0\end{array}\right)={\sigma }_2{\mathbf{u}}_2{\mathbf{v}}_2^T,$$

   as the truncation lemma promises. Hence $\Vert A-A_1{\Vert }_2={\sigma }_2=1$ and $\Vert A-A_1{\Vert }_F=\sqrt{{\sigma }_2^2}=1$. Direct check of the Frobenius value from the entries: $4\cdot \frac{1}{4}=1$, so $\Vert A-A_1{\Vert }_F=1$ ✓. The two norms agree because the error matrix has rank one.

   (b) Deleting rows is not the same as truncating. $B$ has rank one, so it is a legitimate competitor. The error is

   $$A-B=\left(\begin{array}{cc}0& 0\\ 1& 2\\ 1& 1\end{array}\right),\Vert A-B{\Vert }_F=\sqrt{0+0+1+4+1+1}=\sqrt{7}\approx 2.65>1.$$

   For the spectral norm a lower bound suffices: $\Vert A-B{\Vert }_2\ge \Vert (A-B){\mathbf{e}}_2\Vert =\Vert (0,2,1)\Vert =\sqrt{5}>1$. So $B$ is worse than $A_1$ in both norms. The Eckart–Young theorem says this was inevitable: no matrix of rank at most $1$ can come closer to $A$ than ${\sigma }_2=1$ in either norm. The best rank-$k$ approximation zeroes the small singular values, which touches every entry of $A$; zeroing entries, rows or columns is a different and inferior operation.

   (c) Choosing $k$ from an energy target. Squares: $64,36,9,4,1$, total $\Vert A{\Vert }_F^2=114$. Cumulative fractions:

   $$\frac{64}{114}\approx 0.561,\frac{100}{114}\approx 0.877,\frac{109}{114}\approx \mathrm{0.956.}$$

   The first to reach $0.90$ is at $k=3$, and $k=2$ falls short at $87.7\%$, so $k=3$ is the smallest. The errors are $\Vert A-A_3{\Vert }_2={\sigma }_4=2$ and $\Vert A-A_3{\Vert }_F=\sqrt{{\sigma }_4^2+{\sigma }_5^2}=\sqrt{4+1}=\sqrt{5}$. Check: $109+5=114$ ✓, the Pythagorean split of the Frobenius norm.

   Storage: the rank-$3$ truncation needs $k(m+n+1)=3(40+30+1)=213$ numbers against $40\cdot 30=1200$ for the matrix itself, a ratio of $1200/213\approx 5.6$, so about $18\%$ of the original.

8. 8.Proof · 10 min

   Throughout, $A$ is $m\times n$ of rank $r$ and ${\sigma }_j(A)$ denotes its $j$-th singular value, with the convention ${\sigma }_j(A)=0$ for $j>r$. Quote the Eckart–Young theorem in the form

   $${\sigma }_{k+1}(A)=\min \{\Vert A-B{\Vert }_2:\mathrm{rank}B\le k\},0\le k<\min (m,n),$$

   together with the truncation lemma $\Vert A-A_k{\Vert }_2={\sigma }_{k+1}$. (The edge cases $k=0$ and $k\ge r$ are immediate and you should say why.)

   1. (a)Let $E$ be any $m\times n$ matrix. Prove that ${\sigma }_{k+1}(A+E)\le {\sigma }_{k+1}(A)+\Vert E{\Vert }_2$, and deduce that $|{\sigma }_j(A+E)-{\sigma }_j(A)|\le \Vert E{\Vert }_2$ for every $j$. Explain in a sentence why this inequality is what makes numerical rank a meaningful quantity.
   2. (b)Prove that $\Vert A{\Vert }_F^2=\Vert A_k{\Vert }_F^2+\Vert A-A_k{\Vert }_F^2$ for every $1\le k\le r$, and describe the geometric content of the identity.
   3. (c)Let $A$ be $n\times n$ and invertible. Prove that the spectral-norm distance from $A$ to the nearest singular matrix is exactly ${\sigma }_n$, exhibit a singular matrix at that distance, and deduce that $\kappa (A)=\Vert A{\Vert }_2/\mathrm{dist}(A,\text{singular})$. What is the distance for the shear $\left(\begin{array}{cc}1& 2\\ 0& 1\end{array}\right)$?
   Show the solution to question 8

   Edge cases first. For $k=0$ the only matrix of rank $0$ is $B=0$ and $\Vert A{\Vert }_2={\sigma }_1$, so the formula holds. For $k\ge r$ the choice $B=A$ is allowed and gives distance $0={\sigma }_{k+1}$. For $1\le k<r$ it is the theorem as stated.

   (a) Singular values move by at most the size of the perturbation. Since $A_k$ has rank at most $k$, it is an admissible $B$ for the matrix $A+E$, so

   $${\sigma }_{k+1}(A+E)\le \Vert (A+E)-A_k{\Vert }_2\le \Vert A-A_k{\Vert }_2+\Vert E{\Vert }_2={\sigma }_{k+1}(A)+\Vert E{\Vert }_2,$$

   using the triangle inequality for the spectral norm (which holds because $\Vert (X+Y)\mathbf{x}\Vert \le \Vert X\mathbf{x}\Vert +\Vert Y\mathbf{x}\Vert$ for every $\mathbf{x}$) and then the truncation lemma. Now exchange roles: $A=(A+E)+(-E)$ and $\Vert -E{\Vert }_2=\Vert E{\Vert }_2$, so the same argument gives ${\sigma }_{k+1}(A)\le {\sigma }_{k+1}(A+E)+\Vert E{\Vert }_2$. Together, with $j=k+1$,

   $$|{\sigma }_j(A+E)-{\sigma }_j(A)|\le \Vert E{\Vert }_2\text{for every }j.■$$

   This is what makes numerical rank meaningful: if the data carry noise of size $\Vert E{\Vert }_2$, every singular value of the measured matrix lies within $\Vert E{\Vert }_2$ of the corresponding singular value of the true matrix, so a singular value far above the noise level is genuine and one below it cannot be distinguished from zero. Pivots in row reduction satisfy no such inequality, which is why they cannot be trusted to measure rank on measured data.

   (b) Pythagoras for the truncation. The expressions $A_k={\sum }_{i\le k}{\sigma }_i{\mathbf{u}}_i{\mathbf{v}}_i^T$ and $A-A_k={\sum }_{i>k}{\sigma }_i{\mathbf{u}}_i{\mathbf{v}}_i^T$ are each of SVD form (orthonormal $\mathbf{u}$'s, orthonormal $\mathbf{v}$'s, decreasing positive weights), so by the uniqueness theorem their singular values are ${\sigma }_1,\dots ,{\sigma }_k$ and ${\sigma }_{k+1},\dots ,{\sigma }_r$ respectively. The Frobenius formula then gives

   $$\Vert A_k{\Vert }_F^2+\Vert A-A_k{\Vert }_F^2=\sum _{i\le k}{\sigma }_i^2+\sum _{k<i\le r}{\sigma }_i^2=\sum _{i\le r}{\sigma }_i^2=\Vert A{\Vert }_F^2.■$$

   The geometric content: under the inner product $⟨X,Y⟩=\mathrm{tr}(X^{T}Y)$, whose norm is the Frobenius norm, $A_k$ and $A-A_k$ are orthogonal — indeed $A_k^T(A-A_k)={\sum }_{i\le k}{\sum }_{j>k}{\sigma }_i{\sigma }_j{\mathbf{v}}_i({\mathbf{u}}_i^T{\mathbf{u}}_j){\mathbf{v}}_j^T=0$ because ${\mathbf{u}}_i^T{\mathbf{u}}_j=0$ for $i\ne j$. Truncation is an orthogonal projection of $A$ onto the span of its first $k$ outer products, and Pythagoras follows.

   (c) The condition number is a relative distance to singularity. An $n\times n$ matrix is singular exactly when its rank is at most $n-1$. Apply Eckart–Young with $k=n-1$ (legitimate, as $r=n$):

   $$\mathrm{dist}(A,\text{singular})=\min \{\Vert A-B{\Vert }_2:\mathrm{rank}B\le n-1\}={\sigma }_n,$$

   attained by $B=A_{n-1}=A-{\sigma }_n{\mathbf{u}}_n{\mathbf{v}}_n^T$, which is singular. Therefore

   $$\kappa (A)=\frac{{\sigma }_1}{{\sigma }_n}=\frac{\Vert A{\Vert }_2}{\mathrm{dist}(A,\text{singular})}.■$$

   A matrix is ill-conditioned precisely when it is close to a singular matrix relative to its own size, which is why scaling by a constant changes nothing. For the shear $B=\left(\begin{array}{cc}1& 2\\ 0& 1\end{array}\right)$, with ${\sigma }_2=\sqrt{2}-1$, there is a singular matrix within spectral distance $\sqrt{2}-1\approx 0.41$, and none closer.

9. 9.Critique · 8 min

   A student is asked for $A^{+}\mathbf{b}$ with $A=\left(\begin{array}{cc}1& 2\\ 2& 4\end{array}\right)$ and $\mathbf{b}=(5,0)$, and writes the following.

   Step 1. $\mathbf{b}$ is not a multiple of $(1,2)$, so $A\mathbf{x}=\mathbf{b}$ has no solution and I look for a least-squares solution instead.

   Step 2. The least-squares solutions are the $\mathbf{x}$ with $A\mathbf{x}=\mathbf{p}$, where $\mathbf{p}$ is the projection of $\mathbf{b}$ onto $\mathrm{Col}A=\mathrm{span}\{(1,2)\}$. With $\mathbf{a}=(1,2)$, $\mathbf{p}=\frac{\mathbf{b}\cdot \mathbf{a}}{\mathbf{a}\cdot \mathbf{a}}\mathbf{a}=\frac{5}{5}(1,2)=(1,2)$.

   Step 3. $A\mathbf{x}=(1,2)$ reduces to the single equation $x_1+2x_2=1$, whose solutions are $(1-2t,t)$ for any $t$.

   Step 4. By the Penrose conditions $A^{+}$ is unique, so the least-squares solution is unique. Taking $t=0$ gives $A^{+}\mathbf{b}=(1,0)$.

   Exactly one step contains an error, and the final answer is wrong.

   1. (a)Identify the erroneous step. State precisely which two things are being confused, and say in words which of the vectors $(1-2t,t)$ the pseudoinverse actually returns. Find it by minimising along the line.
   2. (b)Compute $A^{+}$ from an SVD of $A$ and hence $A^{+}\mathbf{b}$. Check that your answer is a least-squares solution and compare its norm with the student's answer.
   3. (c)The student adds: “As a check, $A{A}^{+}$ should equal $I$.” Explain why it will not, compute $A{A}^{+}$, and identify the matrix you get.
   Show the solution to question 9

   (a) The error is in Step 4. Steps 1 to 3 are correct: $(5,0)$ is not a multiple of $(1,2)$; the projection formula onto a line is applied correctly, with $\mathbf{b}\cdot \mathbf{a}=5$ and $\mathbf{a}\cdot \mathbf{a}=5$; and the solution set of $x_1+2x_2=1$ is indeed the line $(1-2t,t)$.

   Step 4 confuses two different uniqueness statements. The Penrose conditions say that the matrix $A^{+}$ is unique. They say nothing about least-squares solutions being unique, and here they are not: $\mathrm{Null}A=\mathrm{span}\{(-2,1)\}$ is a line, so every minimiser can be shifted along it without changing $A\mathbf{x}$, which is exactly what Step 3 found. The least-squares theorem for the pseudoinverse says which minimiser $A^{+}\mathbf{b}$ is: the one of smallest norm, equivalently the unique minimiser lying in $\mathrm{Row}A=\mathrm{span}\{(1,2)\}$. Choosing $t=0$ picked an arbitrary point of the line, not the closest one to the origin.

   Minimising along the line: $\Vert (1-2t,t){\Vert }^2=1-4t+5t^2$, with derivative $-4+10t$, zero at $t=\frac{2}{5}$. So the correct value is $(1-\frac{4}{5},\frac{2}{5})=(\frac{1}{5},\frac{2}{5})$, which is indeed a multiple of $(1,2)$ ✓.

   (b) The pseudoinverse from an SVD. $A^{T}A=\left(\begin{array}{cc}5& 10\\ 10& 20\end{array}\right)$ has trace $25$ and determinant $0$, so ${\lambda }_1=25$, ${\lambda }_2=0$: ${\sigma }_1=5$, $r=1$. (The full-column-rank formula $(A^{T}A{)}^{-1}{A}^T$ is unavailable, which is presumably why the student avoided it.) The eigenvector for $25$ satisfies $-20x+10y=0$, i.e. $y=2x$, so ${\mathbf{v}}_1=\frac{1}{\sqrt{5}}(1,2)$ and

   $${\mathbf{u}}_1=\frac{A{\mathbf{v}}_1}{{\sigma }_1}=\frac{1}{5}\cdot \frac{1}{\sqrt{5}}\left(\begin{array}{c}5\\ 10\end{array}\right)=\frac{1}{\sqrt{5}}\left(\begin{array}{c}1\\ 2\end{array}\right).$$

   Then

   $$A^{+}=\frac{1}{{\sigma }_1}{\mathbf{v}}_1{\mathbf{u}}_1^T=\frac{1}{5}\cdot \frac{1}{5}\left(\begin{array}{cc}1& 2\\ 2& 4\end{array}\right)=\frac{1}{25}\left(\begin{array}{cc}1& 2\\ 2& 4\end{array}\right),A^{+}\mathbf{b}=\frac{1}{25}\left(\begin{array}{c}5\\ 10\end{array}\right)=\left(\begin{array}{c}1/5\\ 2/5\end{array}\right),$$

   agreeing with (a). Check it is a least-squares solution: $A\hat{\mathbf{x}}=(\frac{1}{5}+\frac{4}{5},\frac{2}{5}+\frac{8}{5})=(1,2)=\mathbf{p}$ ✓, and the residual $\mathbf{b}-\mathbf{p}=(4,-2)$ is orthogonal to $(1,2)$ since $4-4=0$ ✓. Norms: $\Vert \hat{\mathbf{x}}{\Vert }^2=\frac{1}{25}+\frac{4}{25}=\frac{1}{5}$, against $\Vert (1,0){\Vert }^2=1$ for the student's answer. Both fit the data equally well; only one is the pseudoinverse solution.

   (c) $A{A}^{+}$ is a projection, not the identity. $A{A}^{+}=I$ would force $\mathrm{Col}A={\mathbb{R}}^2$, i.e. full row rank, and $A$ has rank $1$. Computing,

   $$A{A}^{+}=\left(\begin{array}{cc}1& 2\\ 2& 4\end{array}\right)\cdot \frac{1}{25}\left(\begin{array}{cc}1& 2\\ 2& 4\end{array}\right)=\frac{1}{25}\left(\begin{array}{cc}5& 10\\ 10& 20\end{array}\right)=\frac{1}{5}\left(\begin{array}{cc}1& 2\\ 2& 4\end{array}\right).$$

   This is symmetric and idempotent — $(\frac{1}{5}\left(\begin{array}{cc}1& 2\\ 2& 4\end{array}\right){)}^2=\frac{1}{25}\left(\begin{array}{cc}5& 10\\ 10& 20\end{array}\right)$ is itself again — with column space $\mathrm{span}\{(1,2)\}$: it is the orthogonal projection onto $\mathrm{Col}A$, which is what $A{A}^{+}$ always is (write $A{A}^{+}=U\Sigma {\Sigma }^{+}{U}^T={\sum }_{i\le r}{\mathbf{u}}_i{\mathbf{u}}_i^T$). Applied to $\mathbf{b}$ it returns $\frac{1}{5}(5,10)=(1,2)=\mathbf{p}$, the projection the student computed by hand in Step 2 ✓. The correct check for a matrix of this shape is the Penrose condition $A{A}^{+}A=A$, not $A{A}^{+}=I$.

10. 10.Computation · 10 min

    Four observations of two variables are recorded: $(1,1)$, $(2,4)$, $(4,2)$, $(5,5)$. Observations are rows, and $m=4$.

    1. (a)Centre the data, write the centred matrix $X$, and compute $X^{T}X$ and the sample covariance matrix $C$.
    2. (b)Find both principal components, the singular values of $X$, the variance explained by each component, and the fraction of total variance explained by the first.
    3. (c)Compute the scores of the four observations on the first component and verify that their sample variance equals the eigenvalue from (b). Then form the rank-one truncation $X_1$, add the mean back, describe geometrically where each point has gone, and check that $\Vert X-X_1{\Vert }_F^2={\sigma }_2^2$.
    4. (d)Let $X_0$ be the raw (uncentred) matrix and $\bar{\mathbf{x}}$ the mean vector. Prove that $X_0^T{X}_0=X^{T}X+m\bar{\mathbf{x}}{\bar{\mathbf{x}}}^T$, evaluate it for these data, and explain what an analysis that skips the centring would report and why it is misleading.
    Show the solution to question 10

    (a) Centre and form the covariance. Means: $\bar{x}=\frac{1+2+4+5}{4}=3$, $\bar{y}=\frac{1+4+2+5}{4}=3$. Subtracting $(3,3)$ from each row,

    $$X=\left(\begin{array}{cc}-2& -2\\ -1& 1\\ 1& -1\\ 2& 2\end{array}\right),X^{T}X=\left(\begin{array}{cc}4+1+1+4& 4-1-1+4\\ 4-1-1+4& 4+1+1+4\end{array}\right)=\left(\begin{array}{cc}10& 6\\ 6& 10\end{array}\right),C=\frac{1}{m-1}{X}^{T}X=\frac{1}{3}\left(\begin{array}{cc}10& 6\\ 6& 10\end{array}\right).$$

    The diagonal entries $\frac{10}{3}$ are the sample variances of the two variables and the off-diagonal $2$ is their covariance.

    (b) Principal components. $X^{T}X$ has trace $20$ and determinant $100-36=64$, so ${\lambda }^2-20\lambda +64=(\lambda -16)(\lambda -4)$: eigenvalues $16$ and $4$, hence singular values of $X$ are ${\sigma }_1=4$ and ${\sigma }_2=2$. For $16$, $-6x+6y=0$ gives ${\mathbf{v}}_1=\frac{1}{\sqrt{2}}(1,1)$; for $4$, $6x+6y=0$ gives ${\mathbf{v}}_2=\frac{1}{\sqrt{2}}(1,-1)$. The variances explained are ${\sigma }_i^2/(m-1)$: $\frac{16}{3}$ and $\frac{4}{3}$, whose sum $\frac{20}{3}=\mathrm{tr}C$ ✓. The first component explains

    $$\frac{16}{16+4}=0.8,$$

    so a single coordinate along the line $y=x$ (through the mean) captures $80\%$ of the spread.

    (c) Scores, and the reconstruction. The scores are $X{\mathbf{v}}_1=\frac{1}{\sqrt{2}}(-4,0,0,4)=(-2\sqrt{2},0,0,2\sqrt{2})$. They have mean zero, so their sample variance is

    $$\frac{8+0+0+8}{3}=\frac{16}{3}={\lambda }_1✓$$

    — the first-component-maximises-variance theorem in action. Since $X{\mathbf{v}}_1={\sigma }_1{\mathbf{u}}_1$, ${\mathbf{u}}_1=\frac{1}{\sqrt{2}}(-1,0,0,1)$, and the rank-one truncation is

    $$X_1={\sigma }_1{\mathbf{u}}_1{\mathbf{v}}_1^T=4\cdot \frac{1}{2}\left(\begin{array}{c}-1\\ 0\\ 0\\ 1\end{array}\right)\left(\begin{array}{cc}1& 1\end{array}\right)=\left(\begin{array}{cc}-2& -2\\ 0& 0\\ 0& 0\\ 2& 2\end{array}\right).$$

    Adding the mean back, the reconstructed points are $(1,1),(3,3),(3,3),(5,5)$: each original point has been dropped perpendicularly onto the line $y=x$. The residual is $X-X_1$, with rows $(0,0),(-1,1),(1,-1),(0,0)$, so $\Vert X-X_1{\Vert }_F^2=1+1+1+1=4={\sigma }_2^2$ ✓, which is the sum of the squared distances from the points to the line. That equality is Eckart–Young: no other line through the mean has a smaller total squared distance to the data.

    (d) What forgetting to centre does. Write $1$ for the all-ones vector in ${\mathbb{R}}^m$, so that $X_0=X+1{\bar{\mathbf{x}}}^T$. Then

    $$X_0^T{X}_0=X^{T}X+X^{T}1{\bar{\mathbf{x}}}^T+\bar{\mathbf{x}}{1}^{T}X+\bar{\mathbf{x}}(1^{T}1){\bar{\mathbf{x}}}^T=X^{T}X+m\bar{\mathbf{x}}{\bar{\mathbf{x}}}^T,$$

    because $X^{T}1$ is the vector of column sums of the centred matrix, which is $0$, and $1^{T}1=m$. $■$

    Here $m\bar{\mathbf{x}}{\bar{\mathbf{x}}}^T=4\left(\begin{array}{cc}9& 9\\ 9& 9\end{array}\right)$, so $X_0^T{X}_0=\left(\begin{array}{cc}46& 42\\ 42& 46\end{array}\right)$ (direct check from the raw rows: $1+4+16+25=46$ and $1+8+8+25=42$ ✓). Its eigenvalues are $46\pm 42$, namely $88$ and $4$, so the uncentred procedure reports a leading direction $\frac{1}{\sqrt{2}}(1,1)$ with “explained fraction” $\frac{88}{92}\approx 0.957$ instead of the true $0.8$. The extra term is rank one, points along the mean $\bar{\mathbf{x}}$, and has eigenvalue $m\Vert \bar{\mathbf{x}}{\Vert }^2=72$ — it measures where the cloud sits, not how it varies, and it dominates whenever the mean is large compared with the spread. In this example the direction happened to survive only because $\bar{\mathbf{x}}=(3,3)$ lies along the genuine first component; move the data to have mean $(3,-3)$ and the uncentred leading direction would swing to $\frac{1}{\sqrt{2}}(1,-1)$, the wrong axis entirely.

11. 11.Computation · 10 min

    Let $A=\left(\begin{array}{cc}1& 3\\ 3& 1\end{array}\right)$. Its polar decomposition is $A=QS$ with $Q$ orthogonal and $S$ symmetric positive semidefinite.

    1. (a)Compute $S=(A^{T}A{)}^{1/2}$ by diagonalising $A^{T}A$, then $Q=A{S}^{-1}$. Verify that $Q$ is orthogonal and that $QS=A$.
    2. (b)Compute an SVD of $A$, form $Q=U{V}^T$ and $S=V\Sigma V^T$, and confirm they agree with (a). Explain why the sign freedom in the singular vectors cannot change $Q$ or $S$, and describe $Q$ geometrically.
    3. (c)Prove that for an invertible $A=QS$, $Q$ is a rotation ($\det Q=+1$) if and only if $\det A>0$, and classify the $Q$ found above. Then show that $\Vert A-Q{\Vert }_F=\Vert \Sigma -I{\Vert }_F$ and evaluate it, checking directly from the entries of $A-Q$.
    Show the solution to question 11

    (a) The stretch factor from a square root. $A$ is symmetric, so $A^{T}A=A^2=\left(\begin{array}{cc}1+9& 3+3\\ 3+3& 9+1\end{array}\right)=\left(\begin{array}{cc}10& 6\\ 6& 10\end{array}\right)$, with eigenvalues $10\pm 6$, namely $16$ and $4$, and eigenvectors $\frac{1}{\sqrt{2}}(1,1)$ and $\frac{1}{\sqrt{2}}(1,-1)$. The positive definite square root acts as $\sqrt{16}=4$ and $\sqrt{4}=2$ on those eigenspaces:

    $$S=4\cdot \frac{1}{2}\left(\begin{array}{cc}1& 1\\ 1& 1\end{array}\right)+2\cdot \frac{1}{2}\left(\begin{array}{cc}1& -1\\ -1& 1\end{array}\right)=\left(\begin{array}{cc}3& 1\\ 1& 3\end{array}\right).$$

    Check: $S^2=\left(\begin{array}{cc}9+1& 3+3\\ 3+3& 1+9\end{array}\right)=\left(\begin{array}{cc}10& 6\\ 6& 10\end{array}\right)=A^{T}A$ ✓, and $S$ is positive definite (eigenvalues $4,2$). Since $\det S=8$, $S^{-1}=\frac{1}{8}\left(\begin{array}{cc}3& -1\\ -1& 3\end{array}\right)$ and

    $$Q=A{S}^{-1}=\frac{1}{8}\left(\begin{array}{cc}1& 3\\ 3& 1\end{array}\right)\left(\begin{array}{cc}3& -1\\ -1& 3\end{array}\right)=\frac{1}{8}\left(\begin{array}{cc}3-3& -1+9\\ 9-1& -3+3\end{array}\right)=\left(\begin{array}{cc}0& 1\\ 1& 0\end{array}\right).$$

    $Q^{T}Q=I$ ✓, and $QS=\left(\begin{array}{cc}1& 3\\ 3& 1\end{array}\right)=A$ ✓. Uniqueness of the polar factors of an invertible matrix says these are the factors.

    (b) The same factors from the SVD. Singular values are $\sqrt{16}=4$ and $\sqrt{4}=2$, with ${\mathbf{v}}_1=\frac{1}{\sqrt{2}}(1,1)$, ${\mathbf{v}}_2=\frac{1}{\sqrt{2}}(1,-1)$, and

    $${\mathbf{u}}_1=\frac{A{\mathbf{v}}_1}{4}=\frac{1}{4\sqrt{2}}\left(\begin{array}{c}4\\ 4\end{array}\right)=\frac{1}{\sqrt{2}}\left(\begin{array}{c}1\\ 1\end{array}\right),{\mathbf{u}}_2=\frac{A{\mathbf{v}}_2}{2}=\frac{1}{2\sqrt{2}}\left(\begin{array}{c}-2\\ 2\end{array}\right)=\frac{1}{\sqrt{2}}\left(\begin{array}{c}-1\\ 1\end{array}\right).$$

    (The eigenvalue $-2$ of $A$ has become the singular value $2$, and the sign has moved into ${\mathbf{u}}_2=-{\mathbf{v}}_2$.) Then

    $$Q=U{V}^T={\mathbf{u}}_1{\mathbf{v}}_1^T+{\mathbf{u}}_2{\mathbf{v}}_2^T=\frac{1}{2}\left(\begin{array}{cc}1& 1\\ 1& 1\end{array}\right)+\frac{1}{2}\left(\begin{array}{cc}-1& 1\\ 1& -1\end{array}\right)=\left(\begin{array}{cc}0& 1\\ 1& 0\end{array}\right),$$

    and $S=V\Sigma V^T=4{\mathbf{v}}_1{\mathbf{v}}_1^T+2{\mathbf{v}}_2{\mathbf{v}}_2^T$, which is the sum computed in (a). Both agree ✓. Sign choices cannot matter: replacing $({\mathbf{u}}_i,{\mathbf{v}}_i)$ by $(-{\mathbf{u}}_i,-{\mathbf{v}}_i)$ leaves each product ${\mathbf{u}}_i{\mathbf{v}}_i^T$ and ${\mathbf{v}}_i{\mathbf{v}}_i^T$ unchanged, and if a singular value were repeated, ${\mathbf{u}}_i{\mathbf{v}}_i^T$ summed over its eigenspace would likewise be basis-independent.

    Geometrically $Q$ swaps the coordinates: it is the reflection across the line $y=x$, not a rotation. So $A$ is “stretch by $4$ along $(1,1)$ and by $2$ along $(1,-1)$, then reflect in the line $y=x$”.

    (c) Rotation or reflection, and the distance to $Q$. From $A=QS$, $\det A=\det Q\det S$. The eigenvalues of $S$ are the singular values ${\sigma }_i>0$, so $\det S={\sigma }_1\cdots {\sigma }_n>0$, and $\det Q=\pm 1$ since $Q$ is orthogonal. Hence $\det Q=+1$ exactly when $\det A>0$. $■$ Here $\det A=1-9=-8<0$, so $\det Q=-1$ and $Q$ is a reflection, in agreement with (b).

    For the distance, $Q=U{V}^T$ and orthogonal invariance of the Frobenius norm give

    $$\Vert A-Q{\Vert }_F=\Vert U\Sigma V^T-UI{V}^T{\Vert }_F=\Vert U(\Sigma -I)V^T{\Vert }_F=\Vert \Sigma -I{\Vert }_F=\sqrt{(4-1{)}^2+(2-1{)}^2}=\sqrt{10}.$$

    Direct check: $A-Q=\left(\begin{array}{cc}1& 2\\ 2& 1\end{array}\right)$, whose entries square to $1+4+4+1=10$ ✓. Since $Q$ is the orthogonal matrix nearest to $A$, no orthogonal matrix lies within Frobenius distance $\sqrt{10}$ of $A$.

12. 12.Proof · 11 min

    Let $A=U\Sigma V^T$ be a full SVD of an $m\times n$ matrix of rank $r$, let $\mathbf{b}\in {\mathbb{R}}^m$, and write ${\beta }_i={\mathbf{u}}_i^T\mathbf{b}$ for the coordinates of $\mathbf{b}$ in the basis ${\mathbf{u}}_1,\dots ,{\mathbf{u}}_m$. Write $\hat{\mathbf{x}}=A^{+}\mathbf{b}$. This question is about truncated SVD regularisation: fixing a threshold $\epsilon >0$, letting $k$ be the number of singular values with ${\sigma }_i>\epsilon$, and using

    $${\mathbf{x}}_{\epsilon }=\sum _{i=1}^k\frac{{\beta }_i}{{\sigma }_i}{\mathbf{v}}_i$$

    in place of $\hat{\mathbf{x}}$.

    1. (a)Show that $\hat{\mathbf{x}}=\sum _{i=1}^r\frac{{\beta }_i}{{\sigma }_i}{\mathbf{v}}_i$. Deduce that if $\mathbf{b}$ is replaced by $\mathbf{b}+\delta \mathbf{b}$ then $\hat{\mathbf{x}}$ changes by at most $\Vert \delta \mathbf{b}\Vert /{\sigma }_r$, and identify a $\delta \mathbf{b}$ for which this is an equality.
    2. (b)Prove that ${\mathbf{x}}_{\epsilon }=A_k^{+}\mathbf{b}$, where $A_k$ is the rank-$k$ truncation of $A$, and that a perturbation $\delta \mathbf{b}$ changes ${\mathbf{x}}_{\epsilon }$ by less than $\Vert \delta \mathbf{b}\Vert /\epsilon$, whatever the value of ${\sigma }_r$.
    3. (c)Prove that $\Vert A{\mathbf{x}}_{\epsilon }-\mathbf{b}{\Vert }^2=\Vert A\hat{\mathbf{x}}-\mathbf{b}{\Vert }^2+\sum _{i=k+1}^r{\beta }_i^2$. Then illustrate (a), (b) and (c) with $A=\left(\begin{array}{cc}1& 0\\ 0& 1/100\end{array}\right)$, $\mathbf{b}=(1,1)$, $\epsilon =\frac{1}{10}$ and $\delta \mathbf{b}=(0,\frac{1}{100})$, computing every quantity exactly.
    Show the solution to question 12

    (a) The pseudoinverse solution, coordinate by coordinate. By definition $A^{+}=V{\Sigma }^{+}{U}^T={\sum }_{i\le r}{\sigma }_i^{-1}{\mathbf{v}}_i{\mathbf{u}}_i^T$, so

    $$\hat{\mathbf{x}}=A^{+}\mathbf{b}=\sum _{i=1}^r\frac{{\mathbf{u}}_i^T\mathbf{b}}{{\sigma }_i}{\mathbf{v}}_i=\sum _{i=1}^r\frac{{\beta }_i}{{\sigma }_i}{\mathbf{v}}_i.$$

    Each component of $\mathbf{b}$ along ${\mathbf{u}}_i$ is divided by ${\sigma }_i$: the smallest singular value is the largest amplifier. Replacing $\mathbf{b}$ by $\mathbf{b}+\delta \mathbf{b}$ changes $\hat{\mathbf{x}}$ by $\delta \hat{\mathbf{x}}=A^{+}\delta \mathbf{b}={\sum }_{i\le r}{\sigma }_i^{-1}({\mathbf{u}}_i^T\delta \mathbf{b}){\mathbf{v}}_i$, and because the ${\mathbf{v}}_i$ are orthonormal,

    $$\Vert \delta \hat{\mathbf{x}}{\Vert }^2=\sum _{i=1}^r\frac{({\mathbf{u}}_i^T\delta \mathbf{b}{)}^2}{{\sigma }_i^2}\le \frac{1}{{\sigma }_r^2}\sum _{i=1}^r({\mathbf{u}}_i^T\delta \mathbf{b}{)}^2\le \frac{1}{{\sigma }_r^2}\sum _{i=1}^m({\mathbf{u}}_i^T\delta \mathbf{b}{)}^2=\frac{\Vert \delta \mathbf{b}{\Vert }^2}{{\sigma }_r^2},$$

    the last step being Parseval for the orthonormal basis ${\mathbf{u}}_1,\dots ,{\mathbf{u}}_m$ of ${\mathbb{R}}^m$. So $\Vert \delta \hat{\mathbf{x}}\Vert \le \Vert \delta \mathbf{b}\Vert /{\sigma }_r$, with equality when $\delta \mathbf{b}$ is a multiple of ${\mathbf{u}}_r$, since then only the $i=r$ term survives and both inequalities are equalities. $■$

    (b) The truncated solution is a pseudoinverse solution for $A_k$. The truncation $A_k={\sum }_{i\le k}{\sigma }_i{\mathbf{u}}_i{\mathbf{v}}_i^T$ is written in SVD form with rank $k$, so its pseudoinverse, by the definition applied to that SVD, is $A_k^{+}={\sum }_{i\le k}{\sigma }_i^{-1}{\mathbf{v}}_i{\mathbf{u}}_i^T$, and

    $$A_k^{+}\mathbf{b}=\sum _{i=1}^k\frac{{\beta }_i}{{\sigma }_i}{\mathbf{v}}_i={\mathbf{x}}_{\epsilon }.$$

    (Uniqueness via the Penrose conditions guarantees this does not depend on which SVD of $A$ we started from.) A perturbation now moves ${\mathbf{x}}_{\epsilon }$ by $A_k^{+}\delta \mathbf{b}$, and the computation of (a) with $r$ replaced by $k$ gives

    $$\Vert A_k^{+}\delta \mathbf{b}{\Vert }^2=\sum _{i=1}^k\frac{({\mathbf{u}}_i^T\delta \mathbf{b}{)}^2}{{\sigma }_i^2}\le \frac{1}{{\epsilon }^2}\sum _{i=1}^k({\mathbf{u}}_i^T\delta \mathbf{b}{)}^2\le \frac{\Vert \delta \mathbf{b}{\Vert }^2}{{\epsilon }^2},$$

    because every retained ${\sigma }_i$ exceeds $\epsilon$. For $\delta \mathbf{b}\ne 0$ at least one of the two inequalities is strict: the first if some ${\mathbf{u}}_i^T\delta \mathbf{b}$ with $i\le k$ is nonzero (as ${\sigma }_i>\epsilon$ there), and otherwise the second, since then all of $\Vert \delta \mathbf{b}{\Vert }^2$ sits in the omitted terms $i>k$. So the amplification is capped at $1/\epsilon$, a number chosen by the user, however tiny ${\sigma }_r$ may be. $■$

    (c) The price: a larger residual. Expand $\mathbf{b}={\sum }_{i\le m}{\beta }_i{\mathbf{u}}_i$. Since $A{\mathbf{v}}_i={\sigma }_i{\mathbf{u}}_i$,

    $$A\hat{\mathbf{x}}=\sum _{i\le r}\frac{{\beta }_i}{{\sigma }_i}{\sigma }_i{\mathbf{u}}_i=\sum _{i\le r}{\beta }_i{\mathbf{u}}_i,A{\mathbf{x}}_{\epsilon }=\sum _{i\le k}{\beta }_i{\mathbf{u}}_i.$$

    The first is the projection of $\mathbf{b}$ onto $\mathrm{Col}A$, as it should be. Subtracting from $\mathbf{b}$ and using orthonormality of the ${\mathbf{u}}_i$,

    $$\Vert A\hat{\mathbf{x}}-\mathbf{b}{\Vert }^2=\sum _{i>r}{\beta }_i^2,\Vert A{\mathbf{x}}_{\epsilon }-\mathbf{b}{\Vert }^2=\sum _{k<i\le r}{\beta }_i^2+\sum _{i>r}{\beta }_i^2,$$

    and the difference is ${\sum }_{k<i\le r}{\beta }_i^2$: exactly the part of $\mathbf{b}$ that lived in the discarded singular directions. $■$ Regularisation trades a controlled amount of misfit (bias) for immunity to noise (variance).

    The example. $A=\mathrm{diag}(1,\frac{1}{100})$ is its own SVD with $U=V=I$, ${\sigma }_1=1$, ${\sigma }_2=\frac{1}{100}$, $r=2$, and $\beta =(1,1)$.

    By (a), $\hat{\mathbf{x}}=(\frac{1}{1},\frac{1}{1/100})=(1,100)$, and $\delta \mathbf{b}=(0,\frac{1}{100})=\frac{1}{100}{\mathbf{u}}_2$ gives $\delta \hat{\mathbf{x}}=(0,1)$: a perturbation of length $\frac{1}{100}$ moved the solution by $1$, which is $\Vert \delta \mathbf{b}\Vert /{\sigma }_2$ exactly, the equality case.

    With $\epsilon =\frac{1}{10}$ we have ${\sigma }_1>\epsilon >{\sigma }_2$, so $k=1$ and ${\mathbf{x}}_{\epsilon }=(1,0)$. The same $\delta \mathbf{b}$ has ${\mathbf{u}}_1^T\delta \mathbf{b}=0$, so ${\mathbf{x}}_{\epsilon }$ does not move at all — comfortably within the cap $\Vert \delta \mathbf{b}\Vert /\epsilon =\frac{1}{10}$ from (b).

    Residuals: $A\hat{\mathbf{x}}-\mathbf{b}=(1,1)-(1,1)=0$, while $A{\mathbf{x}}_{\epsilon }-\mathbf{b}=(1,0)-(1,1)=(0,-1)$, of squared length $1={\beta }_2^2$, matching (c) with $k=1$, $r=2$. The regularised fit misses $\mathbf{b}$ by $1$ in the direction it has chosen not to trust, and in exchange a $1\%$ change in the data no longer produces a $100\%$ change in the answer.