The Factorization to Be Proved
The singular value decomposition expresses a real matrix as a product of two orthogonal changes of coordinates and a diagonal scaling. The construction is not limited to square or invertible matrices: rectangular matrices and matrices with zero singular values are included. The central task in the proof is to build the left singular vectors from the right ones, then handle any remaining left directions without changing the factorization.
Let \(\mathbf{A}\in\mathbb{R}^{m\times n}\). A square real matrix \(\mathbf{Q}\) is orthogonal if \(\mathbf{Q}^{\top}\mathbf{Q}=\mathbf{I}\); its columns are then an orthonormal basis. A rectangular diagonal matrix has entries only on its main diagonal, with every off-diagonal entry zero. The result below uses a full \(m\times m\) orthogonal matrix on the left and a full \(n\times n\) orthogonal matrix on the right.
The proof uses the real Spectral Theorem: every real symmetric matrix has an orthonormal basis of real eigenvectors. We use this standard result from earlier spectral theory. The matrix \(\mathbf{A}^{\top}\mathbf{A}\) is real and symmetric, so the theorem applies to it. First we check the sign of its eigenvalues, because the construction requires their square roots.
Proof. Suppose \(\lambda\) is an eigenvalue with eigenvector \(\mathbf{v}\ne\mathbf{0}\), so \(\mathbf{A}^{\top}\mathbf{A}\mathbf{v}=\lambda\mathbf{v}\). Multiplying on the left by \(\mathbf{v}^{\top}\) gives $$ \lambda\mathbf{v}^{\top}\mathbf{v} =\mathbf{v}^{\top}\mathbf{A}^{\top}\mathbf{A}\mathbf{v} =(\mathbf{A}\mathbf{v})^{\top}(\mathbf{A}\mathbf{v}) =\|\mathbf{A}\mathbf{v}\|^2\ge 0. $$ Since \(\mathbf{v}\ne\mathbf{0}\), we have \(\mathbf{v}^{\top}\mathbf{v}=\|\mathbf{v}\|^2>0\). Dividing by this positive number shows \(\lambda\ge0\). \(\square\)
From the Gram Matrix to Singular Vectors
Apply the Spectral Theorem to \(\mathbf{A}^{\top}\mathbf{A}\). Choose an orthonormal eigenbasis \(\mathbf{v}_1,\ldots,\mathbf{v}_n\), with eigenvalues ordered so that \(\lambda_1\ge\cdots\ge\lambda_n\ge0\). Define \(\sigma_j=\sqrt{\lambda_j}\). These nonnegative numbers are the singular values, and the vectors \(\mathbf{v}_j\) are the right singular vectors. The order ensures that positive singular values come first and any zeros come last.
For each positive singular value, define a vector in \(\mathbb{R}^m\) by $$ \mathbf{u}_j=\frac{\mathbf{A}\mathbf{v}_j}{\sigma_j}. $$ The division is valid precisely when \(\sigma_j>0\). These vectors are orthonormal: for indices \(i,j\) with positive singular values, the eigenvector equation gives $$ \mathbf{u}_i^{\top}\mathbf{u}_j =\frac{\mathbf{v}_i^{\top}\mathbf{A}^{\top}\mathbf{A}\mathbf{v}_j}{\sigma_i\sigma_j} =\frac{\lambda_j\mathbf{v}_i^{\top}\mathbf{v}_j}{\sigma_i\sigma_j}. $$ If \(i\ne j\), the right singular vectors are orthogonal, so this is \(0\). If \(i=j\), it is \(\lambda_i/\sigma_i^2=1\). Thus the constructed left vectors are orthonormal.
Now consider a zero singular value. If \(\sigma_j=0\), then \(\lambda_j=0\), and $$ \|\mathbf{A}\mathbf{v}_j\|^2 =\mathbf{v}_j^{\top}\mathbf{A}^{\top}\mathbf{A}\mathbf{v}_j =\lambda_j\mathbf{v}_j^{\top}\mathbf{v}_j=0. $$ A vector has norm zero only when it is the zero vector, so \(\mathbf{A}\mathbf{v}_j=\mathbf{0}\). The formula \(\mathbf{A}\mathbf{v}_j/\sigma_j\) cannot be used in this case; instead, the corresponding left basis vectors are chosen by completing the already constructed orthonormal list.
An orthonormal list in \(\mathbb{R}^m\) can be extended to an orthonormal basis. To see why, if its span is not all of \(\mathbb{R}^m\), at least one standard basis vector lies outside that span, since the standard basis spans \(\mathbb{R}^m\). Subtract its projections onto the vectors already chosen. The result is nonzero and orthogonal to those vectors; normalizing it adds one more orthonormal vector. Repeating this process finishes after at most \(m\) vectors. This also covers the case when there are no positive singular values: begin with an empty list and choose an orthonormal basis of \(\mathbb{R}^m\).
Proof of the Real Singular Value Decomposition
Proof. Let \(\lambda_1\ge\cdots\ge\lambda_n\ge0\) be the eigenvalues of \(\mathbf{A}^{\top}\mathbf{A}\), with corresponding orthonormal eigenvectors \(\mathbf{v}_1,\ldots,\mathbf{v}_n\). Set \(\sigma_j=\sqrt{\lambda_j}\), and let \(r\) be the number of positive \(\sigma_j\). For \(1\le j\le r\), define \(\mathbf{u}_j=\mathbf{A}\mathbf{v}_j/\sigma_j\). The calculation above proves that these \(r\) vectors are orthonormal. In particular, \(r\le m\), because an orthonormal list in \(\mathbb{R}^m\) has at most \(m\) vectors.
Complete \(\mathbf{u}_1,\ldots,\mathbf{u}_r\) to an orthonormal basis \(\mathbf{u}_1,\ldots,\mathbf{u}_m\) of \(\mathbb{R}^m\), and form the matrices $$ \mathbf{U}=\begin{bmatrix}\mathbf{u}_1&\cdots&\mathbf{u}_m\end{bmatrix}, \qquad \mathbf{V}=\begin{bmatrix}\mathbf{v}_1&\cdots&\mathbf{v}_n\end{bmatrix}. $$ Both are orthogonal because their columns are orthonormal bases. Define \(\boldsymbol{\Sigma}\in\mathbb{R}^{m\times n}\) by setting its \(j\)th diagonal entry to \(\sigma_j\) for \(1\le j\le\min(m,n)\), and all other entries to zero. For \(j\le r\), the definition of \(\mathbf{u}_j\) gives \(\mathbf{A}\mathbf{v}_j=\sigma_j\mathbf{u}_j\). For \(j>r\), \(\sigma_j=0\) and the norm calculation gives \(\mathbf{A}\mathbf{v}_j=\mathbf{0}\). Also \(r\le m\), so any index \(j>m\) has \(\sigma_j=0\). Consequently, the \(j\)th columns of \(\mathbf{A}\mathbf{V}\) and \(\mathbf{U}\boldsymbol{\Sigma}\) agree for every \(1\le j\le n\); hence \(\mathbf{A}\mathbf{V}=\mathbf{U}\boldsymbol{\Sigma}\). Multiplying on the right by \(\mathbf{V}^{\top}\), and using \(\mathbf{V}\mathbf{V}^{\top}=\mathbf{I}_n\), yields \(\mathbf{A}=\mathbf{U}\boldsymbol{\Sigma}\mathbf{V}^{\top}\). All diagonal entries of \(\boldsymbol{\Sigma}\) are nonnegative and ordered as required. \(\square\)
Worked Examples of the Construction
Worked Example: A Rank-Deficient Square Matrix
Consider \(\mathbf{A}=\begin{bmatrix}1&1\\1&1\end{bmatrix}\). We compute its Gram matrix: $$ \mathbf{A}^{\top}\mathbf{A} =\begin{bmatrix}1&1\\1&1\end{bmatrix} \begin{bmatrix}1&1\\1&1\end{bmatrix} =\begin{bmatrix}2&2\\2&2\end{bmatrix}. $$ The vectors \(\mathbf{v}_1=\frac{1}{\sqrt{2}}(1,1)^{\top}\) and \(\mathbf{v}_2=\frac{1}{\sqrt{2}}(1,-1)^{\top}\) are orthonormal. Direct multiplication gives \(\mathbf{A}^{\top}\mathbf{A}\mathbf{v}_1=4\mathbf{v}_1\) and \(\mathbf{A}^{\top}\mathbf{A}\mathbf{v}_2=\mathbf{0}\). Thus the singular values are \(2,0\). For the positive value, $$ \mathbf{A}\mathbf{v}_1 =\frac{1}{\sqrt{2}}\begin{bmatrix}2\\2\end{bmatrix} =\begin{bmatrix}\sqrt{2}\\\sqrt{2}\end{bmatrix}, \qquad \mathbf{u}_1=\frac{\mathbf{A}\mathbf{v}_1}{2} =\frac{1}{\sqrt{2}}\begin{bmatrix}1\\1\end{bmatrix}. $$ Complete this to an orthonormal basis by taking \(\mathbf{u}_2=\frac{1}{\sqrt{2}}(-1,1)^{\top}\). Therefore $$ \mathbf{U}=\frac{1}{\sqrt{2}}\begin{bmatrix}1&-1\\1&1\end{bmatrix}, \quad \boldsymbol{\Sigma}=\begin{bmatrix}2&0\\0&0\end{bmatrix}, \quad \mathbf{V}^{\top}=\frac{1}{\sqrt{2}}\begin{bmatrix}1&1\\1&-1\end{bmatrix}. $$ Check: Multiplication first gives \(\mathbf{U}\boldsymbol{\Sigma}=\begin{bmatrix}\sqrt{2}&0\\\sqrt{2}&0\end{bmatrix}\). Then $$ \mathbf{U}\boldsymbol{\Sigma}\mathbf{V}^{\top} =\begin{bmatrix}\sqrt{2}&0\\\sqrt{2}&0\end{bmatrix} \frac{1}{\sqrt{2}}\begin{bmatrix}1&1\\1&-1\end{bmatrix} =\begin{bmatrix}1&1\\1&1\end{bmatrix} =\mathbf{A}. $$
Worked Example: A Tall Rectangular Matrix
Let \(\mathbf{A}=\begin{bmatrix}0&1\\2&0\\0&0\end{bmatrix}\), a \(3\times2\) matrix. Its Gram matrix and an orthonormal eigenbasis are $$ \mathbf{A}^{\top}\mathbf{A} =\begin{bmatrix}4&0\\0&1\end{bmatrix}, \qquad \mathbf{v}_1=\begin{bmatrix}1\\0\end{bmatrix}, \quad \mathbf{v}_2=\begin{bmatrix}0\\1\end{bmatrix}. $$ Indeed, \(\mathbf{A}^{\top}\mathbf{A}\mathbf{v}_1=4\mathbf{v}_1\) and \(\mathbf{A}^{\top}\mathbf{A}\mathbf{v}_2=\mathbf{v}_2\). The singular values are \(2,1\). Applying the construction, $$ \mathbf{A}\mathbf{v}_1=\begin{bmatrix}0\\2\\0\end{bmatrix}, \quad \mathbf{u}_1=\frac{\mathbf{A}\mathbf{v}_1}{2}=\begin{bmatrix}0\\1\\0\end{bmatrix}, \qquad \mathbf{A}\mathbf{v}_2=\begin{bmatrix}1\\0\\0\end{bmatrix}, \quad \mathbf{u}_2=\frac{\mathbf{A}\mathbf{v}_2}{1}=\begin{bmatrix}1\\0\\0\end{bmatrix}. $$ A third unit vector orthogonal to both is \(\mathbf{u}_3=(0,0,1)^{\top}\). Thus $$ \mathbf{U}=\begin{bmatrix}0&1&0\\1&0&0\\0&0&1\end{bmatrix}, \quad \boldsymbol{\Sigma}=\begin{bmatrix}2&0\\0&1\\0&0\end{bmatrix}, \quad \mathbf{V}=\mathbf{I}_2. $$ Check: \(\mathbf{U}\boldsymbol{\Sigma}=\begin{bmatrix}0&1\\2&0\\0&0\end{bmatrix}\), and multiplying by \(\mathbf{V}^{\top}=\mathbf{I}_2\) leaves this matrix unchanged, which is exactly \(\mathbf{A}\). The columns of \(\mathbf{U}\) are orthonormal, as are those of \(\mathbf{V}\).
Worked Example: A Matrix with a Zero Right Singular Direction
Take \(\mathbf{A}=\begin{bmatrix}3&0&0\\0&2&0\end{bmatrix}\). Then $$ \mathbf{A}^{\top}\mathbf{A} =\begin{bmatrix}9&0&0\\0&4&0\\0&0&0\end{bmatrix}. $$ The standard basis vectors \(\mathbf{v}_1,\mathbf{v}_2,\mathbf{v}_3\) of \(\mathbb{R}^3\) are orthonormal eigenvectors with eigenvalues \(9,4,0\), respectively. The singular values are \(3,2,0\). For the first two, $$ \mathbf{A}\mathbf{v}_1=\begin{bmatrix}3\\0\end{bmatrix}, \quad \mathbf{u}_1=\begin{bmatrix}1\\0\end{bmatrix}, \qquad \mathbf{A}\mathbf{v}_2=\begin{bmatrix}0\\2\end{bmatrix}, \quad \mathbf{u}_2=\begin{bmatrix}0\\1\end{bmatrix}. $$ The third right vector is a zero direction: \(\mathbf{A}\mathbf{v}_3=\mathbf{0}\). Since the two left vectors already form an orthonormal basis of \(\mathbb{R}^2\), no additional left vector is needed. We obtain $$ \mathbf{U}=\mathbf{I}_2,\qquad \boldsymbol{\Sigma}=\begin{bmatrix}3&0&0\\0&2&0\end{bmatrix}, \qquad \mathbf{V}=\mathbf{I}_3. $$ Check: \(\mathbf{U}\boldsymbol{\Sigma}\mathbf{V}^{\top}=\mathbf{I}_2\boldsymbol{\Sigma}\mathbf{I}_3=\boldsymbol{\Sigma}=\mathbf{A}\). This example also verifies directly that a zero eigenvalue of \(\mathbf{A}^{\top}\mathbf{A}\) corresponds to a right vector mapped to zero by \(\mathbf{A}\).
Common Mistake: Dividing by the Eigenvalue
The left-vector formula uses the singular value \(\sigma_j=\sqrt{\lambda_j}\), not the eigenvalue \(\lambda_j\). For instance, in the last example, \(\lambda_1=9\) and \(\mathbf{A}\mathbf{v}_1=(3,0)^{\top}\). A tempting but incorrect calculation is $$ \frac{\mathbf{A}\mathbf{v}_1}{\lambda_1} =\begin{bmatrix}1/3\\0\end{bmatrix}. $$ This vector has norm \(1/3\), not \(1\), so it cannot be a column of an orthogonal matrix. The correct normalization is $$ \frac{\mathbf{A}\mathbf{v}_1}{\sigma_1} =\frac{1}{3}\begin{bmatrix}3\\0\end{bmatrix} =\begin{bmatrix}1\\0\end{bmatrix}, $$ which has norm \(1\). More generally, for a positive eigenvalue, \(\|\mathbf{A}\mathbf{v}_j\|^2=\lambda_j\) when \(\|\mathbf{v}_j\|=1\); therefore the norm of \(\mathbf{A}\mathbf{v}_j\) is \(\sqrt{\lambda_j}\), explaining why division by \(\sigma_j\) is exactly the required normalization.
Why Completing the Bases Is Essential
The factorization requires square orthogonal matrices \(\mathbf{U}\) and \(\mathbf{V}\), even when the vectors obtained directly from \(\mathbf{A}\mathbf{v}_j/\sigma_j\) do not fill \(\mathbb{R}^m\). Completing the left vectors supplies the missing columns of \(\mathbf{U}\). Those added directions do not alter the product: the corresponding diagonal entries of \(\boldsymbol{\Sigma}\) are zero, so their contributions vanish. Likewise, the eigenvectors for zero eigenvalues remain in \(\mathbf{V}\), and their images under \(\mathbf{A}\) are zero. These facts are what make the proof apply without assuming that \(\mathbf{A}\) is square, invertible, or of full rank.
In summary, the construction has three linked requirements: use an orthonormal eigenbasis of \(\mathbf{A}^{\top}\mathbf{A}\), normalize each nonzero image by the square root of its eigenvalue, and complete the left orthonormal list where necessary. The final identity follows because both sides send every right singular vector \(\mathbf{v}_j\) to the same vector. This column-by-column agreement is the essential verification of the real singular value decomposition.
Check Your Understanding
For each question, justify the claim using the eigenvector equations or the factorization construction.
- Why must every eigenvalue of \(\mathbf{A}^{\top}\mathbf{A}\) be nonnegative?
- If \(\lambda_j>0\) and \(\|\mathbf{v}_j\|=1\), show that \(\|\mathbf{A}\mathbf{v}_j\|=\sqrt{\lambda_j}\).
- Explain why \(\mathbf{A}\mathbf{v}_j=\mathbf{0}\) whenever \(\lambda_j=0\).
- For \(\mathbf{A}=\begin{bmatrix}2&0\\0&0\\0&0\end{bmatrix}\), find an orthonormal basis of left vectors after constructing the one associated with the positive singular value.
- In the proof, why does \(\mathbf{A}\mathbf{V}=\mathbf{U}\boldsymbol{\Sigma}\) imply \(\mathbf{A}=\mathbf{U}\boldsymbol{\Sigma}\mathbf{V}^{\top}\)?
