The Singular Value Decomposition

Diagonalization $A = P D P^{- 1}$ requires a square matrix with enough independent eigenvectors, and even that can fail. The Spectral Theorem supplies an orthogonal $P$ in the symmetric case, but neither result covers a rectangular matrix. The singular value decomposition has no such restriction: any $m \times n$ matrix factors as $A = U Σ V^{⊤}$ with $U$ and $V$ orthogonal and $Σ$ nonnegative diagonal. The three factors describe the geometry of $x \mapsto A x$ .

Stretching, measured by AᵀA

For a symmetric matrix, $∣ λ ∣$ measures how much $A$ stretches its eigenvector: if $A x = λ x$ with $∥ x ∥ = 1$ , then $∥ A x ∥ = ∣ λ ∣$ . A rectangular $A$ has no eigenvectors, but the quantity $∥ A x ∥$ still has a largest value on the unit sphere, and finding it leads straight to $A^{⊤} A$ . Because

∥ A x ∥^{2} = (A x)^{⊤} (A x) = x^{⊤} (A^{⊤} A) x,

maximizing $∥ A x ∥$ is a constrained optimization of the quadratic form of $A^{⊤} A$ . That matrix is symmetric, since $(A^{⊤} A)^{⊤} = A^{⊤} A$ , and positive semidefinite, since the form equals $∥ A x ∥^{2} \geq 0$ . Its eigenvalues are therefore real and nonnegative.

For example, take $A = [48117 14 - 2]$ , which maps the unit sphere in $R^{3}$ onto an ellipse in $R^{2}$ . Compute

A^{⊤} A = 801004010017014040140200,

with eigenvalues $λ_{1} = 360$ , $λ_{2} = 90$ , $λ_{3} = 0$ and unit eigenvectors

v_{1} = 1/3 2/3 2/3, v_{2} = - 2/3 - 1/3 2/3, v_{3} = 2/3 - 2/3 1/3 .

The maximum of $∥ A x ∥^{2}$ is $λ_{1} = 360$ , attained at $v_{1}$ , so the longest output has length $∥ A v_{1} ∥ = 360 = 610$ , reached in the direction $A v_{1} = (18, 6)$ . The second-largest stretch, over directions orthogonal to $v_{1}$ , is $90 = 310$ at $v_{2}$ , with $A v_{2} = (3, - 9)$ . These are the semi-axes of the image ellipse.

Singular values

The identity $∥ A v_{i} ∥ = σ_{i}$ follows from $∥ A v_{i} ∥^{2} = v_{i}^{⊤} (A^{⊤} A) v_{i} = λ_{i} ∥ v_{i} ∥^{2} = λ_{i}$ . In the example, the singular values are $610$ , $310$ , and $0$ . The number of nonzero singular values equals the rank.

Counting nonzero singular values is the numerically dependable way to find rank. Counting pivots after row reduction is fragile: rounding easily turns a true zero into a tiny nonzero pivot and reports full rank. In practice, singular values below a small threshold are treated as zero, and the count of the rest is the effective rank.

A sends the orthonormal right singular vectors v₁, v₂ on the unit circle to orthogonal image vectors Av₁, Av₂ along the axes of an ellipse, with lengths equal to the singular values s₁, s₂.

The decomposition

Normalizing the image vectors $A v_{i}$ produces the left half of the factorization.

The columns of $V$ are right singular vectors, the columns of $U$ are left singular vectors, and the diagonal of $Σ$ holds the singular values. The construction:

Right singular vectors. Take $V = [v_{1} \dots v_{n}]$ , the orthonormal eigenvectors of $A^{⊤} A$ .
Singular value matrix. Place $σ_{1}, \dots, σ_{r}$ on the diagonal of $Σ$ , padded with zeros to size $m \times n$ .
Left singular vectors. For $i \leq r$ set $u_{i} = \frac{1}{σ _{i}} A v_{i}$ , a unit vector; then $A v_{i} = σ_{i} u_{i}$ . Extend ${u_{1}, \dots, u_{r}}$ to an orthonormal basis ${u_{1}, \dots, u_{m}}$ of $R^{m}$ .

By construction $U$ and $V$ are orthogonal, and $A V = [σ_{1} u_{1} \dots σ_{r} u_{r} 0 \dots 0] = U Σ$ . Right-multiplying by $V^{⊤}$ , and using $V V^{⊤} = I$ , gives $A = U Σ V^{⊤}$ . The singular values are determined by $A$ , but $U$ and $V$ are not unique.

The factorization A = UΣVᵀ writes an m×n matrix as an orthogonal rotation Vᵀ, an axiswise scaling Σ by the singular values, and an orthogonal rotation U; the block S carries the singular values on its diagonal.

A rectangular example

Extending U when there are zero singular values

When $r < m$ , the left singular vectors from image normalization fall short of a full basis and must be extended.

Worked example. Decompose $A = 122122$ , with $A^{⊤} A = [9999]$ , eigenvalues $18$ and $0$ , and unit eigenvectors $v_{1} = \frac{1}{2} (1, 1)$ , $v_{2} = \frac{1}{2} (1, - 1)$ . The only singular value is $σ_{1} = 18 = 32$ , so $r = 1$ and

u_{1} = \frac{1}{3 2} A v_{1} = \frac{1}{3 2} 22222 = \frac{1}{3} 122 .

To finish $U$ , extend ${u_{1}}$ to an orthonormal basis of $R^{3}$ . Any completing vector must satisfy $u_{1}^{⊤} x = 0$ , i.e. $x_{1} + 2 x_{2} + 2 x_{3} = 0$ ; a basis for that plane is $w_{1} = (- 2, 1, 0)$ , $w_{2} = (- 2, 0, 1)$ . Applying Gram–Schmidt and normalizing gives

u_{2} = \frac{1}{5} - 2 10, u_{3} = \frac{1}{3 5} - 2 - 4 5 .

Then $U = [u_{1} u_{2} u_{3}]$ , $Σ = 3200000$ , and $A = U Σ V^{⊤}$ . The extra columns $u_{2}, u_{3}$ do not affect $A$ (they pair with zero rows of $Σ$ ), but they make $U$ orthogonal, and they are an orthonormal basis for $Nul A^{⊤}$ .

The rank-one expansion

Expanding $U Σ V^{⊤}$ columnwise, as with the spectral decomposition, writes $A$ as a sum of rank-one pieces, one per nonzero singular value:

A = σ_{1} u_{1} v_{1}^{⊤} + σ_{2} u_{2} v_{2}^{⊤} + \dots + σ_{r} u_{r} v_{r}^{⊤} .

Each term $u_{i} v_{i}^{⊤}$ is an $m \times n$ rank-one matrix, and the singular values order the terms by size: the $σ_{1}$ term contributes most, then the $σ_{2}$ term, and so on. Truncating the sum after $k < r$ terms yields the best rank- $k$ approximation of $A$ , the basis for compression and denoising.

The SVD builds A additively from rank-one layers σᵢuᵢvᵢᵀ ordered by singular value; keeping only the leading layers gives the best low-rank approximation.

The four fundamental subspaces

The SVD produces orthonormal bases for all four subspaces associated with $A$ at once, sorted by whether their singular value is zero. With rank $r$ :

Column space. ${u_{1}, \dots, u_{r}}$ is an orthonormal basis for $Col A$ , by the orthogonal-image-basis theorem.
Left null space. ${u_{r + 1}, \dots, u_{m}}$ is an orthonormal basis for $Nul A^{⊤} = (Col A)^{⊥}$ .
Row space. ${v_{1}, \dots, v_{r}}$ is an orthonormal basis for $Row A = Col A^{⊤}$ .
Null space. ${v_{r + 1}, \dots, v_{n}}$ is an orthonormal basis for $Nul A$ , since $A v_{i} = 0$ exactly when $σ_{i} = 0$ .

The action of $A$ is transparent in these bases: it sends each row-space basis vector $v_{i}$ to $σ_{i} u_{i}$ in the column space, and annihilates the null-space vectors. This ties together the four fundamental subspaces with the orthogonality that the SVD makes explicit.

The SVD splits the domain into Row A ⟂ Nul A and the codomain into Col A ⟂ Nul Aᵀ; A carries each vᵢ to σᵢuᵢ and sends the null-space vectors to zero.

The singular values also complete the Invertible Matrix Theorem: for a square $A$ , invertibility is equivalent to $A$ having $n$ nonzero singular values, to $Row A = R^{n}$ , and to $(Nul A)^{⊥} = R^{n}$ .

Condition number and least squares

Two applications follow immediately from the factorization, both explored in more depth in the numerical module. Because $U$ and $V$ preserve lengths, any sensitivity in solving $A x = b$ is carried by $Σ$ alone. For an invertible $A$ , the ratio of the largest to smallest singular value is the condition number

κ (A) = \frac{σ _{1}}{σ _{n}},

which measures how much a relative error in $b$ can be amplified in $x$ ; a large $κ$ signals an ill-conditioned system in which roundoff is amplified. The conditioning lesson develops this bound.

The reduced SVD keeps only the first $r$ columns, $A = U_{r} D V_{r}^{⊤}$ with $U_{r}$ ( $m \times r$ ), $D$ ( $r \times r$ invertible), and $V_{r}$ ( $n \times r$ ). It defines the pseudoinverse (Moore–Penrose inverse)

A^{+} = V_{r} D^{- 1} U_{r}^{⊤},

which gives the minimum-length least-squares solution of $A x = b$ as $\overset{x}{^} = A^{+} b$ . Substituting the reduced SVD shows $A \overset{x}{^} = U_{r} U_{r}^{⊤} b$ , the orthogonal projection of $b$ onto $Col A$ , so $\overset{x}{^}$ minimizes $∥ A x - b ∥$ exactly as the normal equations require.

Computing $A^{⊤} A$ by hand suits small examples, but in practice it is avoided: forming $A^{⊤} A$ squares the errors in $A$ . Stable algorithms compute the SVD directly from $A$ by iterative bidiagonalization.