The singular value decomposition

Theorem

The singular value decomposition

T-050Home MU-202Threads structure

Statement

Let \( A \in \mathbb{R}^{m \times n} \) be any real \( m \times n \) matrix (no rank, symmetry, or squareness assumption). Then there exist an orthogonal matrix \( U \in \mathbb{R}^{m \times m} \) (i.e. \( U^{\top}U = I_m \)), an orthogonal matrix \( V \in \mathbb{R}^{n \times n} \), and a rectangular diagonal matrix \( \Sigma \in \mathbb{R}^{m \times n} \) whose only nonzero entries are \( \Sigma_{ii} = \sigma_i \) with \[ \sigma_1 \ge \sigma_2 \ge \cdots \ge \sigma_r \gt 0, \qquad \sigma_{r+1} = \cdots = \sigma_{\min(m,n)} = 0, \] such that \[ A = U \Sigma V^{\top}. \] The number \( r \) equals \( \operatorname{rank}(A) \), and the \( \sigma_i \) — the singular values of \( A \) — are uniquely determined by \( A \): they are the nonnegative square roots of the eigenvalues of \( A^{\top}A \), listed in decreasing order. (The matrices \( U \) and \( V \) are in general not unique.) The same statement holds for \( A \in \mathbb{C}^{m \times n} \) with \( U, V \) unitary and \( {}^{\top} \) replaced by the conjugate transpose \( {}^{*} \); the singular values remain real and nonnegative.

Why it matters

The SVD is the exact geometric anatomy of an arbitrary linear map: every \( A \) sends the unit sphere of \( \mathbb{R}^n \) to a (possibly degenerate) hyperellipse in \( \mathbb{R}^m \), and the theorem says this is all a linear map can do — rotate/reflect (\( V^{\top} \)), stretch along perpendicular axes (\( \Sigma \)), rotate/reflect again (\( U \)). Unlike eigendecomposition, it exists for every matrix, square or not, and its ingredients are orthonormal, hence numerically stable.

Almost every quantitative question about a matrix is answered by its singular values: the operator norm is \( \sigma_1 \), the rank is the number of nonzero \( \sigma_i \), the distance to the nearest rank-\( k \) matrix is \( \sigma_{k+1} \) (Eckart–Young), the condition number is \( \sigma_1/\sigma_n \), and the least-squares problem is solved in closed form by the pseudoinverse \( V\Sigma^{+}U^{\top} \). Principal component analysis, low-rank compression, and the numerical determination of rank are all direct applications.

Hypotheses

The entries lie in \( \mathbb{R} \) (or \( \mathbb{C} \) with the Hermitian form).Over \( \mathbb{Q} \) the theorem fails: for \( A = \begin{pmatrix} 1 & 1 \\ 0 & 1 \end{pmatrix} \), the matrix \( A^{\top}A \) has eigenvalues \( \frac{3 \pm \sqrt{5}}{2} \notin \mathbb{Q} \), so the singular values \( \sqrt{(3\pm\sqrt 5)/2} \) do not exist in the field, and no factorisation with rational orthogonal factors is possible. Over a finite field there is no order, so "\( \sigma_1 \ge \cdots \ge \sigma_r \gt 0 \)" is not even a meaningful condition. The proof needs square roots of nonnegative numbers and the spectral theorem, both of which are real-closed-field phenomena.

\( U \) and \( V \) orthogonal with respect to the standard Euclidean inner products on \( \mathbb{R}^m \) and \( \mathbb{R}^n \).If orthogonality is weakened to mere invertibility, the statement collapses into triviality: every rank-\( r \) matrix factors as \( A = P \begin{pmatrix} I_r & 0 \\ 0 & 0 \end{pmatrix} Q^{-1} \) with invertible \( P, Q \) (rank normal form), so all metric information — every stretching factor — can be normalised away to \( 1 \). The singular values are only well-defined because the factors are required to be isometries.

Finite dimensions.In infinite dimensions the correct generalisation (the Schmidt decomposition \( A = \sum_i \sigma_i \, u_i \langle v_i, \cdot \rangle \)) holds for compact operators between Hilbert spaces, but fails for general bounded operators: the multiplication operator \( (Mf)(x) = x\,f(x) \) on \( L^2[0,1] \) satisfies \( M^{*}M = M^2 \), which has purely continuous spectrum and no eigenvectors at all, so there is no orthonormal system \( (v_i) \) with \( Mv_i = \sigma_i u_i \). Compactness is exactly what restores a discrete singular system with \( \sigma_i \to 0 \).

The decreasing ordering \( \sigma_1 \ge \cdots \ge \sigma_{\min(m,n)} \).This is a normalising convention, but dropping it destroys the uniqueness of \( \Sigma \): permuting the diagonal (with matching permutations of the columns of \( U \) and \( V \)) gives infinitely many "diagonal" factorisations. With the ordering imposed, \( \Sigma \) is unique even though \( U, V \) are not.

Proof

We prove the real case; the complex case is identical with \( {}^{\top} \) replaced by \( {}^{*} \) and the spectral theorem for Hermitian matrices in place of the real symmetric one. Throughout, \( \| \cdot \| \) is the Euclidean norm.

\[ A^{\top}A \in \mathbb{R}^{n \times n} \text{ is symmetric and positive semidefinite.} \]

Symmetry: \( (A^{\top}A)^{\top} = A^{\top}(A^{\top})^{\top} = A^{\top}A \). Positive semidefiniteness: for every \( x \in \mathbb{R}^n \), \( x^{\top}A^{\top}Ax = (Ax)^{\top}(Ax) = \|Ax\|^2 \ge 0 \). Both are direct computations from the definition of transpose. A

\[ \exists \text{ an orthonormal basis } v_1, \dots, v_n \text{ of } \mathbb{R}^n \text{ with } A^{\top}A\,v_i = \lambda_i v_i, \quad \lambda_1 \ge \lambda_2 \ge \cdots \ge \lambda_n \ge 0. \]

Existence of the orthonormal eigenbasis with real eigenvalues is the spectral theorem for real symmetric matrices, applied to \( A^{\top}A \) (Step 1). Nonnegativity of each \( \lambda_i \) follows from positive semidefiniteness: \( \lambda_i = \lambda_i \|v_i\|^2 = v_i^{\top}(A^{\top}A v_i) = \|Av_i\|^2 \ge 0 \). Reorder the basis so the eigenvalues are decreasing. B

\[ \text{Define } \sigma_i := \sqrt{\lambda_i} \ \ (1 \le i \le n), \qquad r := \#\{ i : \sigma_i \gt 0 \}. \quad \text{Then } \|Av_i\| = \sigma_i, \text{ and } Av_i = 0 \text{ for } i \gt r. \]

The square roots exist and are unique in \( \mathbb{R}_{\ge 0} \) because \( \lambda_i \ge 0 \) (this is where the field being real-closed is used). The identity \( \|Av_i\|^2 = v_i^{\top}A^{\top}Av_i = \lambda_i = \sigma_i^2 \) was computed in Step 2; in particular \( \lambda_i = 0 \) forces \( Av_i = 0 \), since a Euclidean norm vanishes only at the zero vector. A

\[ \text{For } 1 \le i \le r \text{ define } u_i := \frac{1}{\sigma_i} A v_i \in \mathbb{R}^m. \quad \text{Claim: } u_1, \dots, u_r \text{ are orthonormal.} \]

This is the key idea of the proof: the right singular vectors are transported through \( A \) and renormalised. For \( 1 \le i, j \le r \), \[ u_i^{\top}u_j = \frac{1}{\sigma_i \sigma_j} (Av_i)^{\top}(Av_j) = \frac{1}{\sigma_i \sigma_j} v_i^{\top} (A^{\top}A v_j) = \frac{\lambda_j}{\sigma_i \sigma_j} v_i^{\top}v_j = \frac{\sigma_j^2}{\sigma_i \sigma_j}\,\delta_{ij} = \delta_{ij}, \] using the eigenvector equation of Step 2 and the orthonormality of the \( v_j \). So orthogonality of the \( u_i \) is inherited, not imposed: eigenvectors of \( A^{\top}A \) for distinct directions stay perpendicular after passing through \( A \). B

\[ r \le m, \text{ and } \{u_1, \dots, u_r\} \text{ extends to an orthonormal basis } u_1, \dots, u_m \text{ of } \mathbb{R}^m. \]

An orthonormal set is linearly independent (if \( \sum c_i u_i = 0 \), pairing with \( u_j \) gives \( c_j = 0 \)), so \( r \le \dim \mathbb{R}^m = m \). The extension is the basis-extension theorem followed by Gram–Schmidt orthonormalisation applied to the appended vectors: extend to any basis, orthonormalise, and note Gram–Schmidt leaves the initial orthonormal segment \( u_1, \dots, u_r \) unchanged. Every vector produced is a unit vector orthogonal to all previous ones, which is exactly what is claimed. C

\[ \text{Set } U := \begin{pmatrix} u_1 & \cdots & u_m \end{pmatrix}, \quad V := \begin{pmatrix} v_1 & \cdots & v_n \end{pmatrix}, \quad \Sigma_{ij} := \begin{cases} \sigma_i, & i = j \le r \\ 0, & \text{otherwise.} \end{cases} \]

\( U \) and \( V \) are square matrices whose columns are orthonormal bases (Steps 2 and 5), hence orthogonal: \( U^{\top}U = I_m \), \( V^{\top}V = I_n \), by the definition of matrix product — the \( (i,j) \) entry of \( U^{\top}U \) is \( u_i^{\top}u_j = \delta_{ij} \). A

\[ (U^{\top} A V)_{ij} = u_i^{\top} A v_j = \begin{cases} u_i^{\top}(\sigma_j u_j) = \sigma_j \delta_{ij}, & j \le r \\ u_i^{\top} \cdot 0 = 0, & j \gt r \end{cases} \; = \; \Sigma_{ij}. \]

Entrywise verification: for \( j \le r \), \( Av_j = \sigma_j u_j \) by the definition of \( u_j \) in Step 4; for \( j \gt r \), \( Av_j = 0 \) by Step 3; then orthonormality of the \( u_i \) (Steps 4–5) evaluates each inner product. Every entry of \( U^{\top}AV \) has been computed, with no case omitted. C

\[ U^{\top} A V = \Sigma \;\Longrightarrow\; A = U \Sigma V^{\top}. \]

Multiply on the left by \( U \) and on the right by \( V^{\top} \): \( U(U^{\top}AV)V^{\top} = (UU^{\top})A(VV^{\top}) = A \), using \( UU^{\top} = I_m \) and \( VV^{\top} = I_n \), i.e. orthogonality of \( U \) and \( V \) from Step 6. (For a square orthogonal matrix, \( U^{\top}U = I \) implies \( UU^{\top} = I \), since a one-sided inverse of a square matrix is two-sided.) A

\[ r = \operatorname{rank}(A), \quad \text{and the } \sigma_i \text{ are uniquely determined by } A. \]

Rank is invariant under multiplication by the invertible matrices \( U \) and \( V^{\top} \), so \( \operatorname{rank}(A) = \operatorname{rank}(\Sigma) = r \) (a diagonal matrix has rank equal to its number of nonzero diagonal entries). Uniqueness: from \( A = U\Sigma V^{\top} \) we get \( A^{\top}A = V (\Sigma^{\top}\Sigma) V^{\top} \), so the \( \sigma_i^2 \) are precisely the eigenvalues of \( A^{\top}A \) (with multiplicity, in decreasing order) — an invariant of \( A \) alone, since the eigenvalues of a matrix do not depend on which orthogonal diagonalisation is chosen. Taking nonnegative square roots preserves uniqueness. B

\[ \text{Non-uniqueness of } U, V \text{: if } \sigma_i = \sigma_j \text{ for } i \ne j, \text{ or } r \lt \min(m,n), \text{ the factors admit genuine freedom.} \]

Completeness of the statement requires noting what is not claimed. Example: \( I_2 = Q\, I_2\, Q^{\top} \) for every orthogonal \( Q \), so \( U = V = Q \) works for all \( Q \) — within an eigenspace of \( A^{\top}A \) of dimension \( \ge 2 \), any orthonormal basis of that eigenspace may be chosen, and the columns \( u_{r+1}, \dots, u_m \) in Step 5 were an arbitrary orthonormal extension. Even for distinct singular values, each pair \( (u_i, v_i) \) can be replaced by \( (-u_i, -v_i) \). B

\( \blacksquare \)

Result

\[ \forall A \in \mathbb{R}^{m \times n} \ \ \exists\, U \in O(m),\ V \in O(n),\ \Sigma \in \mathbb{R}^{m\times n} \text{ diagonal, } \sigma_1 \ge \cdots \ge \sigma_r \gt 0: \quad A = U\,\Sigma\,V^{\top} \]

Reading. Every linear map, however lopsided or degenerate, is a rotation-or-reflection of the source, followed by independent nonnegative stretchings along perpendicular axes, followed by a rotation-or-reflection of the target. The stretch factors (singular values) are intrinsic to the map; the two rotations are not, but any valid pair works. Geometrically: the image of the unit sphere is always a hyperellipse whose semi-axis lengths are \( \sigma_1, \dots, \sigma_r \), pointing along \( u_1, \dots, u_r \).

Scope. Holds for every matrix over \( \mathbb{R} \) (orthogonal \( U, V \)) and every matrix over \( \mathbb{C} \) (unitary \( U, V \), conjugate transpose, singular values still real \( \ge 0 \)). It does not hold verbatim over \( \mathbb{Q} \) or finite fields, and in infinite dimensions it survives only for compact operators between Hilbert spaces (Schmidt decomposition). Uniqueness applies to \( \Sigma \) only, never to \( U, V \).

Corollaries & converses

Rank and the four subspaces. \( \operatorname{rank} A = r \); moreover \( \{u_1,\dots,u_r\} \) is an orthonormal basis of \( \operatorname{im} A \), \( \{u_{r+1},\dots,u_m\} \) of \( (\operatorname{im} A)^{\perp} = \ker A^{\top} \), \( \{v_{r+1},\dots,v_n\} \) of \( \ker A \), and \( \{v_1,\dots,v_r\} \) of \( (\ker A)^{\perp} = \operatorname{im} A^{\top} \). All four fundamental subspaces, with orthonormal bases, for free.
Norms. \( \|A\|_2 = \sigma_1 \) and \( \|A\|_F^2 = \sum_{i=1}^{r} \sigma_i^2 \) (Problems 2–3). Condition number of invertible \( A \): \( \kappa_2(A) = \sigma_1/\sigma_n \).
Pseudoinverse. \( A^{+} = V \Sigma^{+} U^{\top} \), where \( \Sigma^{+} \) inverts the nonzero diagonal entries and transposes the shape; \( A^{+}b \) is the minimum-norm least-squares solution of \( Ax = b \) (Worked example 2).
Polar decomposition. Square \( A \) factors as \( A = QP \) with \( Q \) orthogonal and \( P \) symmetric positive semidefinite (Problem 4).
Eckart–Young–Mirsky. The truncation \( A_k = \sum_{i=1}^{k} \sigma_i u_i v_i^{\top} \) is a best rank-\( \le k \) approximation to \( A \) in both the spectral and Frobenius norms, with \( \|A - A_k\|_2 = \sigma_{k+1} \) (Problem 5).
Spectral theorem recovered. If \( A \) is symmetric positive semidefinite, an SVD with \( U = V \) exists and coincides with the orthogonal eigendecomposition; for general symmetric \( A \), \( \sigma_i = |\lambda_i| \) and \( u_i = \pm v_i \).
Converse. Trivially true as an existence converse: for any orthogonal \( U, V \) and any diagonal \( \Sigma \) with decreasing nonnegative entries, \( U\Sigma V^{\top} \) is a matrix whose singular values are exactly those entries (compute \( (U\Sigma V^{\top})^{\top}(U\Sigma V^{\top}) = V\Sigma^{\top}\Sigma V^{\top} \)). But the uniqueness converse fails: distinct pairs \( (U,V) \ne (U',V') \) can produce the same \( A \) — e.g. \( I = Q I Q^{\top} \) for every orthogonal \( Q \) — so \( A \) does not determine its singular vector matrices.

Fails without

Field not real-closed. Over \( \mathbb{Q} \), take \( A = \begin{pmatrix} 1 & 1 \\ 0 & 1 \end{pmatrix} \). Then \( A^{\top}A = \begin{pmatrix} 1 & 1 \\ 1 & 2 \end{pmatrix} \) has characteristic polynomial \( \lambda^2 - 3\lambda + 1 \) with irrational roots \( \frac{3\pm\sqrt5}{2} \); the would-be singular values \( \sigma = \sqrt{(3\pm\sqrt5)/2} \) lie outside \( \mathbb{Q} \), so no factorisation \( A = U\Sigma V^{\top} \) with rational entries exists. The proof breaks at Steps 2–3: no rational orthonormal eigenbasis, no square roots.
Orthogonality of the factors dropped. If \( U, V \) need only be invertible, then every rank-\( r \) matrix equals \( P \begin{pmatrix} I_r & 0 \\ 0 & 0 \end{pmatrix} Q^{-1} \) — e.g. \( \begin{pmatrix} 0 & 1000 \\ 0 & 0 \end{pmatrix} = \begin{pmatrix} 1000 & 0 \\ 0 & 1 \end{pmatrix} \begin{pmatrix} 1 & 0 \\ 0 & 0 \end{pmatrix} \begin{pmatrix} 0 & 1 \\ 1 & 0 \end{pmatrix} \) — so the "diagonal" can always be normalised to zeros and ones and the singular values \( 1000, 0 \) become invisible. The metric content of the theorem lives entirely in the isometry requirement.
Compactness dropped in infinite dimensions. On \( L^2[0,1] \), the bounded self-adjoint operator \( (Mf)(x) = x f(x) \) has \( \|M\| = 1 \) but no eigenvectors: \( xf(x) = \sigma f(x) \) forces \( f = 0 \) almost everywhere. Hence no orthonormal families \( (u_i), (v_i) \) and scalars \( \sigma_i \) satisfy \( M = \sum_i \sigma_i u_i \langle v_i, \cdot \rangle \) even weakly, and the Schmidt/SVD expansion fails. For compact operators the expansion is restored, with \( \sigma_i \to 0 \).

Common errors

Singular values \( \ne \) eigenvalues. \( A = \begin{pmatrix} 0 & 1 \\ 0 & 0 \end{pmatrix} \) has both eigenvalues \( 0 \) but singular values \( 1, 0 \). Even for symmetric matrices the two differ in sign: \( A = (-1) \) (a \( 1\times1 \) matrix) has eigenvalue \( -1 \) but singular value \( +1 \). Only for symmetric positive semidefinite matrices do they coincide.
Decoupling \( U \) from \( V \). Diagonalising \( A^{\top}A \) for \( V \) and \( AA^{\top} \) for \( U \) independently, then hoping \( A = U\Sigma V^{\top} \). The sign (and, for repeated singular values, the whole basis) of each \( u_i \) is coupled to \( v_i \) by \( Av_i = \sigma_i u_i \); ignoring this typically flips the sign of some entries of the product. Always generate \( u_i = Av_i/\sigma_i \).
Assuming \( U, V \) unique. They never are: \( (u_i, v_i) \mapsto (-u_i, -v_i) \) always preserves the product, and repeated singular values allow continuous families (Step 10). Statements like "the first singular vector of \( A \)" are only well-defined up to sign, and only when \( \sigma_1 \gt \sigma_2 \).
Shape errors in \( \Sigma \). For \( m \ne n \), \( \Sigma \) is a rectangular \( m \times n \) matrix, not square; writing \( \Sigma \in \mathbb{R}^{r \times r} \) inside the full SVD makes \( U\Sigma V^{\top} \) undefined. (The thin SVD \( A = U_r \Sigma_r V_r^{\top} \) with \( U_r \in \mathbb{R}^{m \times r} \) is a different, also valid, statement — but then \( U_r \) is not orthogonal, merely has orthonormal columns.)
Rank from tiny-but-nonzero \( \sigma_i \). Concluding numerical rank \( = \) number of exactly nonzero computed singular values; in floating point one must threshold, since \( \sigma_i = 10^{-16} \) is numerically zero. The theorem is exact; its numerical use requires the Eckart–Young perspective.

Discussion

The theorem is best held as a geometric statement: choose orthonormal axes in the source so that their images under \( A \) remain perpendicular — the content of Step 4, and the genuinely surprising part — and the map becomes diagonal. Everything else is bookkeeping. This is why the SVD, unlike the Jordan form, is stable under perturbation: singular values are continuous (indeed \( 1 \)-Lipschitz, by Weyl's inequality \( |\sigma_i(A) - \sigma_i(B)| \le \|A - B\|_2 \)) functions of the matrix, whereas Jordan structure can change under arbitrarily small perturbations.

Historically the decomposition was found for square matrices by Beltrami (1873) and, independently, Jordan (1874), as a canonical form for bilinear forms under independent orthogonal changes of variables; Sylvester rediscovered it in 1889. Autonne (1915) extended it to complex matrices, and Eckart and Young (1936) to rectangular ones, in the same paper that proved the low-rank approximation theorem now bearing their names. The numerical story is separate and just as important: the Golub–Kahan bidiagonalisation (1965) and the Golub–Reinsch algorithm made the SVD computable backward-stably in \( \mathcal{O}(mn\min(m,n)) \) time, which is why it quietly underlies least squares, PCA, and rank determination in practice — one never forms \( A^{\top}A \) numerically, as squaring the matrix squares the condition number.

The SVD sits at a junction of results. It contains the spectral theorem as the special case \( A \) symmetric PSD, produces the polar decomposition \( A = QP \) (the matrix analogue of \( z = e^{i\theta} |z| \)), and gives the Courant–Fischer-type variational characterisation \( \sigma_k = \min_{\dim W = n-k+1}\, \max_{x \in W,\, \|x\| = 1} \|Ax\| \), from which the Eckart–Young theorem and Weyl's perturbation inequalities follow. In statistics it is PCA in disguise: the right singular vectors of a centred data matrix are the principal axes, and the squared singular values are (up to scaling) the variances captured.

In operator theory the theorem becomes E. Schmidt's 1907 expansion: a compact operator \( T : H_1 \to H_2 \) between Hilbert spaces admits \( T = \sum_{i} \sigma_i \langle v_i, \cdot \rangle u_i \) with orthonormal \( (v_i), (u_i) \) and \( \sigma_1 \ge \sigma_2 \ge \cdots \to 0 \), the series converging in operator norm — this is the historical origin of the term "singular values", from Schmidt's work on integral equations with unsymmetric kernels. The singular values then grade the compactness of \( T \): \( \sum \sigma_i \lt \infty \) defines the trace class, \( \sum \sigma_i^2 \lt \infty \) the Hilbert–Schmidt class, and the general Schatten \( p \)-classes interpolate. Deeper inequalities (Lidskii, Horn) govern how singular values of sums and products relate to those of the summands and factors, a subject that connects to representation theory via the Horn conjecture. Common misconceptions: the SVD is not "the eigendecomposition for rectangular matrices" — even for square non-normal matrices the two decompositions have different invariants (\( \begin{pmatrix} 0 & 1 \\ 0 & 0 \end{pmatrix} \) has spectrum \( \{0\} \) but \( \sigma_1 = 1 \)); the singular vectors are not unique; and "diagonalisable" in the SVD sense is a property of every matrix, so it carries no information about the matrix, unlike eigen-diagonalisability.

Worked examples

Example 1 (computing a full SVD from scratch). Find an SVD of \( A = \begin{pmatrix} 2 & 2 \\ -1 & 1 \end{pmatrix} \).

\[ A^{\top}A = \begin{pmatrix} 2 & -1 \\ 2 & 1 \end{pmatrix}\begin{pmatrix} 2 & 2 \\ -1 & 1 \end{pmatrix} = \begin{pmatrix} 5 & 3 \\ 3 & 5 \end{pmatrix}. \]

Form the Gram matrix, as dictated by Step 1 of the proof. A

\[ \det(A^{\top}A - \lambda I) = (5-\lambda)^2 - 9 = 0 \;\Longrightarrow\; \lambda_1 = 8, \ \lambda_2 = 2, \qquad \sigma_1 = 2\sqrt2, \ \sigma_2 = \sqrt2. \]

Characteristic polynomial of a \( 2\times2 \) symmetric matrix; singular values are the nonnegative square roots of the eigenvalues (Step 3 of the proof). Both are positive, so \( r = 2 = \operatorname{rank} A \). A

\[ v_1 = \frac{1}{\sqrt2}\begin{pmatrix} 1 \\ 1 \end{pmatrix} \ (\lambda = 8), \qquad v_2 = \frac{1}{\sqrt2}\begin{pmatrix} 1 \\ -1 \end{pmatrix} \ (\lambda = 2). \]

Solve \( (A^{\top}A - 8I)v = 0 \), i.e. \( -3v_{(1)} + 3v_{(2)} = 0 \), and similarly for \( \lambda = 2 \); normalise. They are orthogonal automatically (eigenvectors of a symmetric matrix for distinct eigenvalues). A

\[ u_1 = \frac{Av_1}{\sigma_1} = \frac{1}{2\sqrt2}\cdot\frac{1}{\sqrt2}\begin{pmatrix} 4 \\ 0 \end{pmatrix} = \begin{pmatrix} 1 \\ 0 \end{pmatrix}, \qquad u_2 = \frac{Av_2}{\sigma_2} = \frac{1}{\sqrt2}\cdot\frac{1}{\sqrt2}\begin{pmatrix} 0 \\ -2 \end{pmatrix} = \begin{pmatrix} 0 \\ -1 \end{pmatrix}. \]

Left singular vectors must be generated as \( u_i = Av_i / \sigma_i \) (Step 4 of the proof) — this is what couples the signs of \( U \) and \( V \) correctly. No extension step is needed since \( r = m = 2 \). B

\[ U\Sigma V^{\top} = \begin{pmatrix} 1 & 0 \\ 0 & -1 \end{pmatrix} \begin{pmatrix} 2\sqrt2 & 0 \\ 0 & \sqrt2 \end{pmatrix} \cdot \frac{1}{\sqrt2}\begin{pmatrix} 1 & 1 \\ 1 & -1 \end{pmatrix} = \begin{pmatrix} 2 & 2 \\ -1 & 1 \end{pmatrix} = A. \; \checkmark \]

Direct multiplication verifies the factorisation — always check, since sign errors in Step 4 are the classic failure mode. A

\[ A = \begin{pmatrix} 1 & 0 \\ 0 & -1 \end{pmatrix} \begin{pmatrix} 2\sqrt2 & 0 \\ 0 & \sqrt2 \end{pmatrix} \frac{1}{\sqrt2}\begin{pmatrix} 1 & 1 \\ 1 & -1 \end{pmatrix}, \qquad \sigma_1 = 2\sqrt2, \ \sigma_2 = \sqrt2. \]

Reading. \( A \) rotates the plane by \( 45^{\circ} \) (via \( V^{\top} \)), stretches by \( 2\sqrt2 \) horizontally and \( \sqrt2 \) vertically, then reflects across the horizontal axis. The unit circle maps to an ellipse with semi-axes \( 2\sqrt2 \) and \( \sqrt2 \).

Scope. This particular \( U, V \) pair is one valid choice; \( (u_i, v_i) \mapsto (-u_i, -v_i) \) gives another. \( \Sigma \) is forced.

Example 2 (least squares via the SVD / pseudoinverse). Find the least-squares solution of \( Ax = b \) for \( A = \begin{pmatrix} 1 & 0 \\ 0 & 1 \\ 1 & 0 \end{pmatrix} \), \( b = \begin{pmatrix} 1 \\ 2 \\ 3 \end{pmatrix} \), using an SVD of \( A \).

\[ A^{\top}A = \begin{pmatrix} 2 & 0 \\ 0 & 1 \end{pmatrix} \;\Longrightarrow\; \sigma_1 = \sqrt2, \ \sigma_2 = 1, \quad v_1 = \begin{pmatrix} 1 \\ 0 \end{pmatrix}, \ v_2 = \begin{pmatrix} 0 \\ 1 \end{pmatrix}. \]

\( A^{\top}A \) is already diagonal, so its eigenvectors are the standard basis vectors and the singular values are the square roots of the diagonal, in decreasing order. A

\[ u_1 = \frac{Av_1}{\sqrt2} = \frac{1}{\sqrt2}\begin{pmatrix} 1 \\ 0 \\ 1 \end{pmatrix}, \qquad u_2 = \frac{Av_2}{1} = \begin{pmatrix} 0 \\ 1 \\ 0 \end{pmatrix}. \]

Transport through \( A \) and normalise (Step 4 of the proof). Since \( r = 2 \lt m = 3 \), a third column \( u_3 = \frac{1}{\sqrt2}(1, 0, -1)^{\top} \) would complete the full SVD, but the least-squares computation only needs \( u_1, u_2 \). A

\[ \min_x \|Ax - b\|^2 = \min_y \|\Sigma y - U^{\top}b\|^2, \qquad y := V^{\top}x, \]

Substitute \( A = U\Sigma V^{\top} \) (the theorem) and use that multiplication by the orthogonal matrix \( U^{\top} \) preserves the Euclidean norm: \( \|Ax - b\| = \|U(\Sigma V^{\top}x - U^{\top}b)\| = \|\Sigma y - U^{\top}b\| \). This is the key move: the SVD converts a general least-squares problem into a diagonal one. B

\[ \|\Sigma y - c\|^2 = (\sigma_1 y_1 - c_1)^2 + (\sigma_2 y_2 - c_2)^2 + c_3^2, \qquad c = U^{\top}b, \]

Written out coordinatewise; \( c_3^2 \) is untouchable by \( y \) (it is the component of \( b \) orthogonal to \( \operatorname{im} A \)), and the first two terms are each minimised — indeed zeroed — by \( y_i = c_i/\sigma_i \). Separability of a sum of independent squares. A

\[ c_1 = u_1^{\top}b = \frac{1+3}{\sqrt2} = 2\sqrt2, \quad c_2 = u_2^{\top}b = 2 \;\Longrightarrow\; y = \begin{pmatrix} 2\sqrt2/\sqrt2 \\ 2/1 \end{pmatrix} = \begin{pmatrix} 2 \\ 2 \end{pmatrix}, \quad x = Vy = \begin{pmatrix} 2 \\ 2 \end{pmatrix}. \]

Numerical evaluation; \( V = I \) here so \( x = y \). Equivalently \( x = A^{+}b = \sum_{i=1}^{2} \frac{u_i^{\top}b}{\sigma_i} v_i \). Sanity check against the normal equations: \( A^{\top}A x = (4, 2)^{\top} = A^{\top}b \). \( \checkmark \) A

\[ x_{\mathrm{LS}} = A^{+}b = \begin{pmatrix} 2 \\ 2 \end{pmatrix}, \qquad \|Ax_{\mathrm{LS}} - b\| = |c_3| = \left| \tfrac{1-3}{\sqrt2} \right| = \sqrt2. \]

Reading. The SVD splits \( b \) into the part reachable by \( A \) (spanned by \( u_1, u_2 \)), which is matched exactly, and the unreachable part along \( u_3 \), whose length \( \sqrt2 \) is the irreducible residual.

Scope. The recipe \( x = \sum_{i \le r} (u_i^{\top}b/\sigma_i)v_i \) gives the minimum-norm least-squares solution for any \( A, b \), including rank-deficient \( A \) — the case where the normal equations alone do not determine \( x \).

Problems

Find a full SVD of \( A = \begin{pmatrix} 0 & 2 \\ 0 & 0 \end{pmatrix} \), and read off \( \operatorname{rank} A \), \( \|A\|_2 \), and orthonormal bases of \( \ker A \) and \( \operatorname{im} A \).
Solution
\( A^{\top}A = \begin{pmatrix} 0 & 0 \\ 0 & 4 \end{pmatrix} \), with eigenpairs \( \lambda_1 = 4, v_1 = (0,1)^{\top} \) and \( \lambda_2 = 0, v_2 = (1,0)^{\top} \) (ordered decreasingly). So \( \sigma_1 = 2, \sigma_2 = 0, r = 1 \). Then \( u_1 = Av_1/\sigma_1 = (2,0)^{\top}/2 = (1,0)^{\top} \); extend by \( u_2 = (0,1)^{\top} \). Thus \[ A = \begin{pmatrix} 1 & 0 \\ 0 & 1 \end{pmatrix} \begin{pmatrix} 2 & 0 \\ 0 & 0 \end{pmatrix} \begin{pmatrix} 0 & 1 \\ 1 & 0 \end{pmatrix}, \] where the third factor is \( V^{\top} \) with \( V = \begin{pmatrix} 0 & 1 \\ 1 & 0 \end{pmatrix} \). Check: the product is \( \begin{pmatrix} 2 & 0 \\ 0 & 0 \end{pmatrix}\begin{pmatrix} 0 & 1 \\ 1 & 0 \end{pmatrix} = \begin{pmatrix} 0 & 2 \\ 0 & 0 \end{pmatrix} \). \( \checkmark \) Read-off: \( \operatorname{rank} A = 1 \), \( \|A\|_2 = \sigma_1 = 2 \), \( \ker A = \operatorname{span}\{v_2\} = \operatorname{span}\{(1,0)^{\top}\} \), \( \operatorname{im} A = \operatorname{span}\{u_1\} = \operatorname{span}\{(1,0)^{\top}\} \). Note the eigenvalues of \( A \) are both \( 0 \) while \( \sigma_1 = 2 \): singular values are not eigenvalues.
Prove that \( \|A\|_2 := \sup_{x \ne 0} \frac{\|Ax\|}{\|x\|} = \sigma_1 \).
Solution
Write \( A = U\Sigma V^{\top} \) and, for \( x \ne 0 \), set \( y = V^{\top}x \), so \( \|y\| = \|x\| \) (orthogonal matrices are isometries: \( \|V^{\top}x\|^2 = x^{\top}VV^{\top}x = \|x\|^2 \)). Then \[ \|Ax\|^2 = \|U\Sigma y\|^2 = \|\Sigma y\|^2 = \sum_{i=1}^{r} \sigma_i^2 y_i^2 \le \sigma_1^2 \sum_{i=1}^{n} y_i^2 = \sigma_1^2\|x\|^2, \] using \( \sigma_i \le \sigma_1 \) for all \( i \). Hence \( \|A\|_2 \le \sigma_1 \). For the reverse inequality take \( x = v_1 \): then \( \|Av_1\| = \|\sigma_1 u_1\| = \sigma_1 = \sigma_1\|v_1\| \), so the supremum is attained and \( \|A\|_2 = \sigma_1 \). (If \( A = 0 \) then \( r = 0 \), \( \sigma_1 = 0 \), and the claim is trivial.)
Prove: (a) \( \|A\|_F^2 := \sum_{i,j} A_{ij}^2 = \sum_{i=1}^{r} \sigma_i^2 \); (b) \( A \) and \( A^{\top} \) have the same nonzero singular values; (c) if \( Q, P \) are orthogonal (of compatible sizes) then \( QAP \) has the same singular values as \( A \).
Solution
(a) \( \|A\|_F^2 = \operatorname{tr}(A^{\top}A) \) (expand: the \( j \)-th diagonal entry of \( A^{\top}A \) is \( \sum_i A_{ij}^2 \)). The trace equals the sum of eigenvalues of \( A^{\top}A \), which by the theorem (Step 9) are \( \sigma_1^2, \dots, \sigma_r^2 \) together with zeros. Hence \( \|A\|_F^2 = \sum_{i=1}^r \sigma_i^2 \). (b) Transposing \( A = U\Sigma V^{\top} \) gives \( A^{\top} = V \Sigma^{\top} U^{\top} \), which is itself an SVD of \( A^{\top} \) (\( V, U \) orthogonal, \( \Sigma^{\top} \) rectangular-diagonal with the same nonzero entries in the same order). By uniqueness of singular values (Step 9 applied to \( A^{\top} \)), the nonzero singular values of \( A^{\top} \) are exactly \( \sigma_1, \dots, \sigma_r \). (c) \( QAP = (QU)\,\Sigma\,(P^{\top}V)^{\top} \); products of orthogonal matrices are orthogonal, so this is an SVD of \( QAP \) with the same \( \Sigma \). By uniqueness of \( \Sigma \), the singular values agree. (This is the invariance property that makes singular values "geometric": they see the map only up to isometries of source and target.)
(Polar decomposition.) Let \( A \in \mathbb{R}^{n \times n} \) be square. Using the SVD, prove that \( A = QP \) with \( Q \) orthogonal and \( P \) symmetric positive semidefinite, and show \( P \) is unique (namely \( P = (A^{\top}A)^{1/2} \)) while \( Q \) is unique if and only if \( A \) is invertible.
Solution
Write \( A = U\Sigma V^{\top} \) with \( U, V \in O(n) \), \( \Sigma = \operatorname{diag}(\sigma_1, \dots, \sigma_n) \), \( \sigma_i \ge 0 \). Insert \( V^{\top}V = I \): \[ A = (UV^{\top})(V\Sigma V^{\top}) =: QP. \] \( Q = UV^{\top} \) is orthogonal (product of orthogonal matrices). \( P = V\Sigma V^{\top} \) is symmetric (\( P^{\top} = V\Sigma^{\top}V^{\top} = P \) since \( \Sigma \) is square diagonal) and positive semidefinite (\( x^{\top}Px = \sum_i \sigma_i (V^{\top}x)_i^2 \ge 0 \)). Uniqueness of \( P \): from \( A = QP \), \( A^{\top}A = P^{\top}Q^{\top}QP = P^2 \). A symmetric PSD matrix has a unique symmetric PSD square root (diagonalise \( A^{\top}A = W D W^{\top} \) orthogonally; any symmetric PSD \( P \) with \( P^2 = A^{\top}A \) commutes with \( A^{\top}A \), hence preserves its eigenspaces, and on each eigenspace for eigenvalue \( d \) must act as \( \sqrt d \cdot I \) since \( P \) is PSD with \( P^2 = dI \) there; so \( P = W D^{1/2} W^{\top} \) is forced). Hence \( P = (A^{\top}A)^{1/2} \). Uniqueness of \( Q \): if \( A \) is invertible then all \( \sigma_i \gt 0 \), \( P \) is invertible, and \( Q = AP^{-1} \) is determined. If \( A \) is singular, then \( P \) has nontrivial kernel \( K \ne \{0\} \). Choose \( R \in O(n) \) acting as the identity on \( \operatorname{im} P = K^{\perp} \) and as any orthogonal map on \( K \): then \( RP = P \), so \( (QR)P = QP = A \), and since \( \dim K \ge 1 \) there exists such an \( R \ne I \) (e.g. reflect one unit vector of \( K \)); thus \( QR \ne Q \) is a second valid orthogonal factor. So \( Q \) is non-unique exactly when \( A \) is singular.
(Eckart–Young, spectral norm.) Let \( A = U\Sigma V^{\top} \) with singular values \( \sigma_1 \ge \cdots \ge \sigma_{\min(m,n)} \ge 0 \), and for \( k \lt r \) set \( A_k = \sum_{i=1}^{k} \sigma_i u_i v_i^{\top} \). Prove \[ \min_{\operatorname{rank} B \le k} \|A - B\|_2 = \|A - A_k\|_2 = \sigma_{k+1}. \]
Solution
Upper bound. \( A - A_k = \sum_{i=k+1}^{r} \sigma_i u_i v_i^{\top} = U \Sigma' V^{\top} \) where \( \Sigma' \) is \( \Sigma \) with its first \( k \) diagonal entries zeroed. This exhibits an SVD of \( A - A_k \) (after reordering, its largest singular value is \( \sigma_{k+1} \)), so by Problem 2, \( \|A - A_k\|_2 = \sigma_{k+1} \). Also \( \operatorname{rank} A_k \le k \) since \( A_k \) is a sum of \( k \) rank-one matrices. Hence the minimum is \( \le \sigma_{k+1} \). Lower bound. Let \( B \) be any matrix with \( \operatorname{rank} B \le k \). By rank–nullity, \( \dim \ker B \ge n - k \). Let \( W = \operatorname{span}\{v_1, \dots, v_{k+1}\} \), of dimension \( k+1 \). Since \[ \dim(\ker B \cap W) \ge \dim \ker B + \dim W - n \ge (n-k) + (k+1) - n = 1, \] (the standard subspace dimension inequality \( \dim(X \cap Y) \ge \dim X + \dim Y - n \) in \( \mathbb{R}^n \), from Grassmann's formula \( \dim(X+Y) = \dim X + \dim Y - \dim(X \cap Y) \le n \)), there exists a unit vector \( x \in \ker B \cap W \). Write \( x = \sum_{i=1}^{k+1} c_i v_i \) with \( \sum c_i^2 = 1 \). Then \( Bx = 0 \), so \[ \|A - B\|_2^2 \ge \|(A-B)x\|^2 = \|Ax\|^2 = \Big\| \sum_{i=1}^{k+1} c_i \sigma_i u_i \Big\|^2 = \sum_{i=1}^{k+1} c_i^2 \sigma_i^2 \ge \sigma_{k+1}^2 \sum_{i=1}^{k+1} c_i^2 = \sigma_{k+1}^2, \] using \( Av_i = \sigma_i u_i \), orthonormality of the \( u_i \) (Pythagoras), and \( \sigma_i \ge \sigma_{k+1} \) for \( i \le k+1 \). Hence \( \|A - B\|_2 \ge \sigma_{k+1} \) for every rank-\( \le k \) matrix \( B \), and the truncation \( A_k \) attains the bound. \( \blacksquare \)