Linear Algebra › Section G · Symmetric matrices and quadratic forms › Topic G.4
The singular value decomposition
Not every matrix can be diagonalised, and a rectangular matrix has no eigenvalues at all. The singular value decomposition factors every matrix into a rotation, a stretch along perpendicular axes and another rotation, and it is one of the most useful factorisations in applied mathematics.
From eigenvalues to singular values
Eigenvalues describe how a square matrix stretches its eigenvectors, but many matrices have too few eigenvectors, and an \(m \times n\) matrix with \(m \ne n\) cannot have any, since \(A\mathbf{x}\) and \(\mathbf{x}\) live in different spaces. The fix is to ask a different question: in which directions does \(A\) stretch unit vectors the most, and by how much? By "Constrained optimization", the largest value of
is the largest eigenvalue of the symmetric matrix \(A^TA\). That single observation leads to the whole decomposition.
Singular values
Let \(\mathbf{v}_1, \dots, \mathbf{v}_n\) be orthonormal eigenvectors of \(A^TA\), with eigenvalues \(\lambda_1 \ge \lambda_2 \ge \cdots \ge \lambda_n\). These eigenvalues are never negative, since \(\lambda_i = \|A\mathbf{v}_i\|^2\). The singular values of \(A\) are their square roots,
listed in decreasing order. So \(\sigma_1\) is the greatest stretch \(A\) applies to any unit vector, reached at \(\mathbf{v}_1\) and called the 2-norm of \(A\), and \(\sigma_n\) is the smallest, which is zero if some non-zero vector is sent to \(\mathbf{0}\). The vectors \(A\mathbf{v}_i\) are also mutually orthogonal: for \(i \ne j\), \((A\mathbf{v}_i) \cdot (A\mathbf{v}_j) = \mathbf{v}_i^T(\lambda_j\mathbf{v}_j) = 0\).
Singular values reveal the rank
Suppose exactly \(r\) of the singular values are non-zero. Then the non-zero vectors \(A\mathbf{v}_1, \dots, A\mathbf{v}_r\) are orthogonal, so they are linearly independent, and any \(A\mathbf{x}\) is a combination of them, because the remaining \(A\mathbf{v}_i\) are zero. So they form an orthogonal basis for the column space, and
This is how software computes rank in practice, finding the SVD directly, without forming \(A^TA\), by stable methods going back to Gene Golub and William Kahan in 1965. Rounding errors rarely leave an exact zero, so singular values below a small tolerance are treated as zero. Counting pivots after row reduction is far more fragile, because one rounding error can create or destroy a pivot.
The decomposition
Every \(m \times n\) matrix \(A\) of rank \(r\) can be written
where \(V\) is an \(n \times n\) orthogonal matrix with columns \(\mathbf{v}_i\), the right singular vectors; \(U\) is an \(m \times m\) orthogonal matrix with columns \(\mathbf{u}_i\), the left singular vectors; and \(\Sigma\) is \(m \times n\), the same shape as \(A\), with \(\sigma_1, \dots, \sigma_r\) down its diagonal and zeros everywhere else. For \(i \le r\), \(\mathbf{u}_i = A\mathbf{v}_i / \sigma_i\). Read from right to left, \(A\mathbf{x}\) rotates \(\mathbf{x}\) by \(V^T\), stretches along the coordinate axes by \(\Sigma\), and rotates again by \(U\). An orthogonal matrix may also reflect, but it never changes lengths or angles.
Worked example: a square matrix
Find an SVD of \(A\) with rows \((2, 2)\) and \((-1, 1)\). 1. \(A^TA\) has rows \((5, 3)\) and \((3, 5)\), with eigenvalues 8 and 2 and unit eigenvectors \(\mathbf{v}_1 = (1, 1)/\sqrt{2}\) and \(\mathbf{v}_2 = (1, -1)/\sqrt{2}\). 2. The singular values are \(\sigma_1 = \sqrt{8} = 2\sqrt{2}\) and \(\sigma_2 = \sqrt{2}\). 3. \(A\mathbf{v}_1 = (4, 0)/\sqrt{2}\), of length \(2\sqrt{2}\), so \(\mathbf{u}_1 = (1, 0)\). \(A\mathbf{v}_2 = (0, -2)/\sqrt{2}\), so \(\mathbf{u}_2 = (0, -1)\). 4. Assemble:
5. Check: \(\sigma_1\sigma_2 = 4 = |\det A|\), as it must be for a square matrix.
Worked example: a tall matrix
Find an SVD of the \(3 \times 2\) matrix \(A\) with rows \((1, 1)\), \((0, 1)\), \((1, 0)\). 1. \(A^TA\) has rows \((2, 1)\) and \((1, 2)\): eigenvalues 3 and 1, with \(\mathbf{v}_1 = (1, 1)/\sqrt{2}\), \(\mathbf{v}_2 = (1, -1)/\sqrt{2}\). 2. So \(\sigma_1 = \sqrt{3}\), \(\sigma_2 = 1\), and \(\Sigma\) is \(3 \times 2\) with a zero bottom row. 3. \(A\mathbf{v}_1 = (2, 1, 1)/\sqrt{2}\), giving \(\mathbf{u}_1 = (2, 1, 1)/\sqrt{6}\); \(A\mathbf{v}_2 = (0, -1, 1)/\sqrt{2}\), giving \(\mathbf{u}_2 = (0, -1, 1)/\sqrt{2}\). 4. \(U\) needs a third column: any unit vector orthogonal to both, such as \(\mathbf{u}_3 = (1, -1, -1)/\sqrt{3}\). Check: \((2, 1, 1) \cdot (1, -1, -1) = 0\) and \((0, -1, 1) \cdot (1, -1, -1) = 0\). 5. Multiplying out \(U\Sigma V^T\) returns \(A\).
Bases for the four fundamental subspaces
An SVD hands you orthonormal bases for all four fundamental subspaces of an \(m \times n\) matrix of rank \(r\) at once. The first \(r\) columns of \(U\) span the column space of \(A\), and the remaining \(m - r\) span the null space of \(A^T\). The first \(r\) columns of \(V\) span the row space of \(A\), and the remaining \(n - r\) span the null space of \(A\), since \(A\mathbf{v}_i = \mathbf{0}\) when \(\sigma_i = 0\). In the tall example, \(r = 2\), so \(\mathbf{u}_3\) spans the null space of \(A^T\), and the null space of \(A\) is just \(\{\mathbf{0}\}\). For an invertible \(n \times n\) matrix, all \(n\) singular values are positive.
Condition number and the pseudoinverse
For an invertible \(n \times n\) matrix, the condition number \(\sigma_1 / \sigma_n\) measures how much relative errors in \(\mathbf{b}\) can be magnified in the solution of \(A\mathbf{x} = \mathbf{b}\). The square example has condition number 2, which is excellent; values in the millions signal trouble. Keeping only the non-zero part gives the reduced SVD \(A = U_rDV_r^T\), with \(D\) the \(r \times r\) diagonal matrix of non-zero singular values. Its pseudoinverse, named after E. H. Moore and Roger Penrose, is
For any \(\mathbf{b}\), \(\hat{\mathbf{x}} = A^+\mathbf{b}\) is the least-squares solution of smallest length, even when \(A\) has dependent columns. For the tall example and \(\mathbf{b} = (1, 1, 1)\), it gives \(\hat{\mathbf{x}} = (2/3, 2/3)\).
The geometric picture
Apply \(A\) to the unit circle in \(\mathbb{R}^2\). \(V^T\) turns it, leaving a circle; \(\Sigma\) stretches it into an ellipse with semi-axes \(\sigma_1\) and \(\sigma_2\) along the coordinate axes; and \(U\) turns that ellipse into place. So the image of the unit circle is an ellipse whose semi-axes are \(\sigma_1\mathbf{u}_1\) and \(\sigma_2\mathbf{u}_2\), the images of \(\mathbf{v}_1\) and \(\mathbf{v}_2\). In the square example the unit circle becomes an ellipse with semi-axes \(2\sqrt{2} \approx 2.83\) along \((1, 0)\) and \(\sqrt{2} \approx 1.41\) along \((0, -1)\). In higher dimensions the unit sphere becomes an ellipsoid, flattened completely in any direction where a singular value is zero.
Common mistakes to avoid
First, taking singular values to be eigenvalues: the matrix with rows \((1, 1)\) and \((0, 1)\) has the single eigenvalue 1, but singular values of about 1.618 and 0.618. Second, forgetting the square root: the singular values are \(\sqrt{\lambda_i}\), not the eigenvalues of \(A^TA\) themselves. Third, giving \(\Sigma\) the wrong shape; it must match \(A\), so a \(3 \times 2\) matrix has a \(3 \times 2\) \(\Sigma\). Fourth, using \(\mathbf{u}_i = A\mathbf{v}_i / \sigma_i\) when \(\sigma_i = 0\); those columns of \(U\) must come from extending to an orthonormal basis. Fifth, choosing \(\mathbf{u}_i\) independently of \(\mathbf{v}_i\), which can flip a sign so that \(U\Sigma V^T \ne A\).
Key takeaways
Every m × n matrix has a singular value decomposition A = UΣVᵀ, with U and V orthogonal and Σ the same shape as A. The singular values σᵢ are the square roots of the eigenvalues of AᵀA, listed in decreasing order, and σᵢ = ‖Avᵢ‖. The columns of V are orthonormal eigenvectors of AᵀA, and uᵢ = Avᵢ/σᵢ for each non-zero σᵢ, with U completed to an orthonormal basis if needed. The number of non-zero singular values is the rank, and the columns of U and V give orthonormal bases of the four fundamental subspaces. Geometrically, A rotates, stretches and rotates. The condition number is σ₁/σₙ, and the pseudoinverse A⁺ = V_r D⁻¹ U_rᵀ gives minimum-length least-squares solutions.
Flashcards
Flashcard
A = UΣVᵀ, with U and V orthogonal
Test your understanding
Question 1 of 5
AᵀA has eigenvalues 16, 9 and 0. What are the singular values of A, and what is its rank?
Question 2 of 5
A is a 5 × 3 matrix. What are the sizes of U, Σ and V in A = UΣVᵀ?
Question 3 of 5
Which statement about the matrix with rows (1, 1) and (0, 1) is true?
Question 4 of 5
In an SVD of a 4 × 3 matrix A of rank 2, which vectors form an orthonormal basis for the null space of A?
Question 5 of 5
An invertible matrix has singular values 50, 4 and 0.5. What is its condition number?
