Proof Of The Complex Singular Value Decomposition

From the Gram Matrix to a Factorization

For a real matrix, the singular value decomposition is built from an orthonormal eigenbasis of its transpose-times-itself matrix. Over \(\mathbb{C}\), the corresponding matrix is \(\mathbf{A}^{*}\mathbf{A}\), where \(\mathbf{A}^{*}\) is the conjugate transpose. The conjugation matters: it ensures that the eigenvalues are nonnegative and that the lengths of the images of eigenvectors are controlled by those eigenvalues.

Let \(\mathbf{A}\in\mathbb{C}^{m\times n}\), with \(m,n\in\mathbb{N}\). A list of columns is orthonormal if each column has length one and the product of the conjugate transpose of one column with a different column is zero. A square matrix \(\mathbf{Q}\) is unitary if \(\mathbf{Q}^{*}\mathbf{Q}=\mathbf{I}\); its columns are then an orthonormal basis. An SVD is a factorization with a unitary matrix on each side and a rectangular diagonal matrix between them.

The earlier result on an orthonormal eigenbasis for \(\mathbf{A}^{*}\mathbf{A}\) applies because this matrix is Hermitian: \((\mathbf{A}^{*}\mathbf{A})^{*}=\mathbf{A}^{*}\mathbf{A}\). It gives an orthonormal basis of eigenvectors. Moreover, if \(\mathbf{v}\ne\mathbf{0}\) is an eigenvector with eigenvalue \(\lambda\), then

Since \(\|\mathbf{v}\|^2>0\), every eigenvalue is nonnegative. This is the key fact that makes its square root a real singular value, even though the matrix and its eigenvectors may be complex.

Constructing the Left Singular Vectors

Choose an orthonormal eigenbasis \(\mathbf{v}_1,\ldots,\mathbf{v}_n\) of \(\mathbf{A}^{*}\mathbf{A}\), ordering the eigenvalues so that \(\lambda_1\ge\cdots\ge\lambda_n\ge0\). Set \(\sigma_i=\sqrt{\lambda_i}\). Let \(r\) be the number of positive eigenvalues. For each \(i\le r\), define \(\mathbf{u}_i=\mathbf{A}\mathbf{v}_i/\sigma_i\). This definition is valid because \(\sigma_i>0\); zero eigenvalues must be treated separately.

For \(i,j\le r\), the eigenvector equation gives

If \(i\ne j\), the last expression is zero because the eigenvectors are orthogonal. If \(i=j\), it equals \(\lambda_i=\sigma_i^2\). Dividing by \(\sigma_i\sigma_j\) shows that \(\mathbf{u}_i^{*}\mathbf{u}_j\) is zero when \(i\ne j\) and one when \(i=j\). Thus the left vectors constructed from positive eigenvalues are orthonormal.

If \(i>r\), then \(\lambda_i=0\), and \(\|\mathbf{A}\mathbf{v}_i\|^2=\lambda_i\|\mathbf{v}_i\|^2=0\). A vector has squared length zero only if it is the zero vector, so \(\mathbf{A}\mathbf{v}_i=\mathbf{0}\). Such vectors already describe the zero part of the factorization; there is no need to divide by \(\sigma_i=0\).

Completing the Left Basis

The vectors \(\mathbf{u}_1,\ldots,\mathbf{u}_r\) are orthonormal in \(\mathbb{C}^m\). To form a square unitary matrix, they must be extended to an orthonormal basis of that space. The following finite-dimensional argument also covers the case \(r=0\).

Proof. Start with the given orthonormal list and examine the standard basis vectors \(\mathbf{e}_1,\ldots,\mathbf{e}_m\) in order. For each \(\mathbf{e}_j\), subtract its components along the vectors currently in the list, writing the residual as \(\mathbf{w}=\mathbf{e}_j-\sum_k(\mathbf{q}_k^{*}\mathbf{e}_j)\mathbf{q}_k\), where the \(\mathbf{q}_k\) are the current orthonormal vectors. For each listed vector \(\mathbf{q}_\ell\), orthonormality gives \(\mathbf{q}_\ell^{*}\mathbf{w}=\mathbf{q}_\ell^{*}\mathbf{e}_j-\sum_k(\mathbf{q}_\ell^{*}\mathbf{q}_k)(\mathbf{q}_k^{*}\mathbf{e}_j)=0\). If \(\mathbf{w}=\mathbf{0}\), no vector is added. If \(\mathbf{w}\ne\mathbf{0}\), append \(\mathbf{w}/\|\mathbf{w}\|\); this vector has length one and is orthogonal to every vector already listed. After all \(m\) standard basis vectors have been considered, each \(\mathbf{e}_j\) belongs to the span of the resulting list, since it is either already in the span or equals its subtracted components plus the residual that was appended. The list therefore spans \(\mathbb{C}^m\) and is orthonormal, so it is an orthonormal basis. \(\square\)

Apply the lemma to the constructed left vectors, and call the resulting basis \(\mathbf{u}_1,\ldots,\mathbf{u}_m\). Put these columns into \(\mathbf{U}\). Put the eigenbasis \(\mathbf{v}_1,\ldots,\mathbf{v}_n\) into \(\mathbf{V}\), and define \(\boldsymbol{\Sigma}\) to have \(\sigma_i\) in position \((i,i)\) for \(1\le i\le r\), with zeros elsewhere. The dimensions are \(\mathbf{U}\in\mathbb{C}^{m\times m}\), \(\mathbf{V}\in\mathbb{C}^{n\times n}\), and \(\boldsymbol{\Sigma}\in\mathbb{C}^{m\times n}\). In particular, \(r\le m\), because the \(r\) constructed vectors are orthonormal in \(\mathbb{C}^m\).

Proof of the theorem. The columns of \(\mathbf{U}\) and \(\mathbf{V}\) are orthonormal bases, so \(\mathbf{U}\) and \(\mathbf{V}\) are unitary. It remains to prove the factorization. For \(j\le r\), \(\mathbf{V}^{*}\mathbf{v}_j=\mathbf{e}_j\), and hence \(\mathbf{U}\boldsymbol{\Sigma}\mathbf{V}^{*}\mathbf{v}_j=\sigma_j\mathbf{u}_j=\mathbf{A}\mathbf{v}_j\), by the definition of \(\mathbf{u}_j\). For \(j>r\), \(\boldsymbol{\Sigma}\mathbf{e}_j=\mathbf{0}\), so \(\mathbf{U}\boldsymbol{\Sigma}\mathbf{V}^{*}\mathbf{v}_j=\mathbf{0}=\mathbf{A}\mathbf{v}_j\). Thus the two linear maps agree on every vector of the basis \(\mathbf{v}_1,\ldots,\mathbf{v}_n\). For any \(\mathbf{x}=\sum_{j=1}^n c_j\mathbf{v}_j\), linearity gives equality on \(\mathbf{x}\) as well. Therefore \(\mathbf{A}=\mathbf{U}\boldsymbol{\Sigma}\mathbf{V}^{*}\). The eigenvalues were ordered nonincreasingly and are nonnegative, so their square roots have the required order. \(\square\)

Worked Constructions

Common Pitfalls and Why the Proof Matters

Do not divide by a zero singular value. In the wide-matrix example, \(\mathbf{v}_2=\mathbf{e}_2\) has eigenvalue zero and \(\mathbf{A}\mathbf{v}_2=\mathbf{0}\). The tempting expression \(\mathbf{A}\mathbf{v}_2/\sqrt{0}\) is undefined; it is not a left singular vector. Instead, the left basis is completed independently, while the zero singular value contributes a zero in \(\boldsymbol{\Sigma}\).

Use the conjugate transpose, not the transpose. For the column \(\mathbf{a}=(1,i)^{\top}\), the correct Gram entry is \(\mathbf{a}^{*}\mathbf{a}=1+(-i)i=2\). The incorrect calculation \(\mathbf{a}^{\top}\mathbf{a}=1+i^2=0\) would wrongly suggest a zero squared length. Complex conjugation is essential for the nonnegativity and length identity used in the proof.

The construction establishes more than the existence of a product with suitable dimensions. It explains why the right vectors come from \(\mathbf{A}^{*}\mathbf{A}\), why the positive singular values are square roots of its positive eigenvalues, and why zero eigenvalues require a separate step. Completing both bases makes the factorization valid for square, tall, wide, and rank-deficient matrices alike.