Singular Values of a Matrix

Diagonalization $A=SDS^T$ requires $A$ to be square and symmetric. To reach every matrix we take a detour through $A^TA$. For any $n\times m$ matrix $A$, the product $A^TA$ is an $m\times m$ symmetric matrix, since $(A^TA)^T=A^T(A^T)^T=A^TA$. By the spectral theorem of the previous section, a symmetric matrix has real eigenvalues and an orthonormal eigenbasis. Lemma 9.3 adds the crucial fact that these eigenvalues are never negative. The proof is one line: if $A^TA\mathbf{v}=\lambda\mathbf{v}$ with $\mathbf{v}\neq\mathbf{0}$, then $\|A\mathbf{v}\|^2=(A\mathbf{v})\cdot(A\mathbf{v})=(A\mathbf{v})^T(A\mathbf{v})=\mathbf{v}^TA^TA\mathbf{v}=\mathbf{v}^T(\lambda\mathbf{v})=\lambda\,\|\mathbf{v}\|^2.$ The left-hand side is a squared length, so it is $\ge 0$, and $\|\mathbf{v}\|^2>0$; dividing gives $\lambda=\|A\mathbf{v}\|^2/\|\mathbf{v}\|^2\ge 0$. In other words $A^TA$ is positive semidefinite — which is exactly what makes it legal to take square roots in the next definition.

By Definition 9.2, the singular values of an $n\times m$ matrix $A$ are the square roots $\sigma_i=\sqrt{\lambda_i}$ of the eigenvalues $\lambda_i$ of the symmetric matrix $A^TA$, listed with their algebraic multiplicities (a doubled eigenvalue gives a doubled singular value). Lemma 9.3 is what guarantees each $\sqrt{\lambda_i}$ is a real number. By convention we order them decreasingly, $\sigma_1\ge\sigma_2\ge\cdots\ge\sigma_m\ge 0,$ which makes the list unique even though the eigenvectors behind it are not. Note there are always $m$ singular values — one per eigenvalue of the $m\times m$ matrix $A^TA$ — no matter how many rows $A$ has. (This echoes the symmetric case: if $A$ is symmetric with eigenpairs $A\mathbf{u}_i=\lambda_i\mathbf{u}_i$ and $\|\mathbf{u}_i\|=1$, then $\|A\mathbf{u}_i\|=|\lambda_i|$, previewing $\|A\mathbf{v}_i\|=\sigma_i$.) For example, $A=\begin{pmatrix}0&1&1\\1&1&0\end{pmatrix}$ gives $A^TA$ with eigenvalues $3,1,0$, so $\sigma_1=\sqrt3,\ \sigma_2=1,\ \sigma_3=0$.

For a symmetric matrix the orthonormal eigenvectors already have orthogonal images, $A\mathbf{u}_i=\lambda_i\mathbf{u}_i$. Theorem 9.2 says this good behaviour survives for any matrix provided we use the eigenvectors of $A^TA$. Pick an orthonormal eigenbasis $\mathbf{v}_1,\dots,\mathbf{v}_m$ of $\mathbb{R}^m$ with $A^TA\mathbf{v}_i=\lambda_i\mathbf{v}_i$ and $\lambda_i=\sigma_i^2$. Then two things hold. First the images are orthogonal: for $i\neq j$, $(A\mathbf{v}_i)\cdot(A\mathbf{v}_j)=\mathbf{v}_j^TA^TA\mathbf{v}_i=\mathbf{v}_j^T(\lambda_i\mathbf{v}_i)=\lambda_i(\mathbf{v}_i\cdot\mathbf{v}_j)=0.$ Second their lengths are the singular values: taking $i=j$ in the same calculation gives $\|A\mathbf{v}_i\|^2=\lambda_i$, so $\|A\mathbf{v}_i\|=\sqrt{\lambda_i}=\sigma_i$. Geometrically, $A$ carries the unit sphere $\{c_1\mathbf{v}_1+\cdots+c_m\mathbf{v}_m:\sum c_i^2=1\}$ to an ellipse whose semi-axes are the nonzero $\sigma_i$, pointing along the directions $A\mathbf{v}_i$. In the notes' Example 9.1 the unit sphere of $\mathbb{R}^3$ is squashed onto a filled ellipse in $\mathbb{R}^2$.

Because $\|A\mathbf{v}_i\|=\sigma_i$, the image $A\mathbf{v}_i$ is the zero vector exactly when $\sigma_i=0$. Order the basis so that $\sigma_1\ge\cdots\ge\sigma_r>0$ and $\sigma_{r+1}=\cdots=\sigma_m=0$. The surviving images $A\mathbf{v}_1,\dots,A\mathbf{v}_r$ are orthogonal and nonzero, hence linearly independent, and they span the image because any $A\mathbf{v}=A(c_1\mathbf{v}_1+\cdots+c_m\mathbf{v}_m)=c_1A\mathbf{v}_1+\cdots+c_rA\mathbf{v}_r$. So they form a basis of $\operatorname{im}(A)$, giving Proposition 9.3: $\operatorname{rank}(A)=r=\#\{\text{nonzero singular values}\}.$ This is a numerically stable way to find rank. A second payoff: the largest singular value $\sigma_1$ is the operator norm $\|A\|=\max_{\|\mathbf{x}\|=1}\|A\mathbf{x}\|$, the longest semi-axis of the image ellipse, while the smallest $\sigma_m$ measures the shortest.