The Singular Value Decomposition

(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. ✓

(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$ ✓.

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.✓$$

(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$.

(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.

(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.

(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.

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.

(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$.