---
tag: 31AT4VJF68
kind: proof
name: Proof of the singular value decomposition from the spectral theorem
msc: [15A18, 15A23]
proves: 000NPTMX6J
uses: [0AM050KCAW, 0DGZBQWZWN, 0D6RMJ10M9, 0EX045E2BP, 0Q5SM60HTH, 0753Y2X5K6, 0TYMASG33Y, 0K2TX12X58, 09VYHEF2VT, 0Y85GYEGSF, 0WK0Y8RH1M, 0QK7FPE6VE, 068BZBXE0C]
sources:
  - url: https://en.wikipedia.org/wiki/Singular_value_decomposition
    locator: Proof of existence, based on the spectral theorem
---

## Proof

Here $^*$ is the [[conjugate transpose|0EX045E2BP]], and $\C^k$ carries the inner product $\ip{x}{y} = y^* x$.

1. A square matrix is [[unitary|0D6RMJ10M9]] exactly when its columns form an [[orthonormal family|09VYHEF2VT]]. Indeed the $(i, j)$ entry of $W^* W$ is $w_i^* w_j = \ip{w_j}{w_i}$ for the columns $w_i$ of $W$.
2. By [[the Gram matrix result|0AM050KCAW]], $A^* A$ is a positive semidefinite Hermitian $n \times n$ matrix.
3. By the [[spectral theorem|0DGZBQWZWN]], $A^* A = V_0 D_0 V_0^*$ with $V_0$ unitary and $D_0$ real diagonal.
4. Choose a [[permutation matrix|0Q5SM60HTH]] $\Pi$ such that $D = \Pi^T D_0 \Pi$ is diagonal with entries $\lambda_1 \ge \lambda_2 \ge \cdots \ge \lambda_n$. This permutes the diagonal entries of $D_0$ into decreasing order.
5. The matrix $\Pi$ is real with $\Pi^T \Pi = I$, so it is unitary. By the [[one-sided inverse theorem|0753Y2X5K6]], $\Pi \Pi^T = I$. Let $V = V_0 \Pi$. It is unitary, since $V^* V = \Pi^T V_0^* V_0 \Pi = \Pi^T \Pi = I$.
6. Then $V D V^* = V_0 \Pi \Pi^T D_0 \Pi \Pi^T V_0^* = A^* A$. Also $V V^* = I$ by the one-sided inverse theorem.
7. Let $v_1, \dots, v_n$ be the columns of $V$. They are orthonormal by step 1. From $A^* A V = V D$ we get $A^* A v_i = \lambda_i v_i$.
8. For each $i$, $\lambda_i = \lambda_i v_i^* v_i = v_i^* A^* A v_i = (A v_i)^* (A v_i) \ge 0$.
9. Since $D = V^* (A^* A) V$ and $V^* = V^{-1}$, the matrices $A^* A$ and $D$ have the [[same characteristic polynomial|0TYMASG33Y]]. So $\lambda_1 \ge \cdots \ge \lambda_n$ are the eigenvalues of $A^* A$, with multiplicity.
10. By the definition of [[singular values|0K2TX12X58]], they are $\sigma_i = \sqrt{\lambda_i}$, using the [[square roots of nonnegative reals|068BZBXE0C]]. So $\sigma_1 \ge \cdots \ge \sigma_n \ge 0$.
11. Let $r$ be the number of $i$ with $\lambda_i > 0$. Then $\lambda_i > 0$ for $i \le r$, and $\lambda_i = 0$ for $i > r$.
12. For $i \le r$, let $u_i = A v_i / \sigma_i \in \C^m$. By step 7, $u_i^* u_j = v_i^* A^* A v_j / (\sigma_i \sigma_j) = \lambda_j\, v_i^* v_j / (\sigma_i \sigma_j)$.
13. This is $0$ for $i \ne j$, and $\lambda_i / \sigma_i^2 = 1$ for $i = j$. So $u_1, \dots, u_r$ is an orthonormal family in $\C^m$.
14. By the [[existence of an orthonormal basis|0Y85GYEGSF]], it extends to an orthonormal basis $u_1, \dots, u_m$ of $\C^m$. This basis has $m$ vectors, by the [[dimension theorem|0WK0Y8RH1M]] and [[the dimension of the coordinate space|0QK7FPE6VE]]. So $r \le m$.
15. Let $U$ be the $m \times m$ matrix with columns $u_1, \dots, u_m$. By step 1, $U$ is unitary.
16. For $i > r$, step 8 gives $(A v_i)^* (A v_i) = \lambda_i = 0$. A vector $y$ with $y^* y = \sum_k \abs{y_k}^2 = 0$ is zero, so $A v_i = 0$.
17. Let $\Sigma$ be the $m \times n$ matrix with $\Sigma_{ii} = \sigma_i$ for $i \le \min(m, n)$ and all other entries $0$.
18. Column $j$ of $U \Sigma$ is $\sum_i \Sigma_{ij} u_i$. This is $\sigma_j u_j$ if $j \le m$, and $0$ if $j > m$.
19. Column $j$ of $AV$ is $A v_j$. For $j \le r$, we have $j \le m$ and $A v_j = \sigma_j u_j$ by step 12.
20. For $j > r$, $A v_j = 0$ by step 16. Column $j$ of $U\Sigma$ is also $0$, since either $j > m$ or $\sigma_j = 0$.
21. By steps 18 to 20, $AV = U \Sigma$. By step 6, $A = A V V^* = U \Sigma V^*$.
22. The diagonal entries of $\Sigma$ are $\sigma_1 \ge \cdots \ge \sigma_{\min(m,n)} \ge 0$. If $m < n$, the remaining singular values $\sigma_i$ with $i > m$ are $0$, because $r \le m$.
23. So $A = U \Sigma V^*$ with $U$ and $V$ unitary, $\Sigma_{ij} = 0$ for $i \ne j$, and decreasing diagonal entries given by the singular values of $A$.

## Idea

The matrix $A^* A$ is Hermitian, so it has an orthonormal basis of eigenvectors $v_i$. The images $A v_i$ are automatically orthogonal, with lengths $\sigma_i$. Normalising them and completing to an orthonormal basis gives $U$.