Every Matrix Has a Singular Value Decomposition
Claim
For any matrix \(A \in \mathbb{R}^{m \times n}\) with rank \(r\) (Trefethen and Bau 1997), there exist orthogonal matrices \(U \in \mathbb{R}^{m \times m}\), \(V \in \mathbb{R}^{n \times n}\), and a matrix \(\Sigma \in \mathbb{R}^{m \times n}\) with non-negative entries only on its main diagonal, such that
\[ A = U \Sigma V^\top. \]
Proof
Step 1: Eigendecompose \(A^\top A\).
The matrix \(A^\top A \in \mathbb{R}^{n \times n}\) is symmetric and positive semidefinite. By the spectral theorem it has an orthonormal eigenbasis \(\mathbf{v}_1, \ldots, \mathbf{v}_n\) with real eigenvalues \(\lambda_1 \geq \cdots \geq \lambda_n \geq 0\). Since
\[ \lambda_i \|\mathbf{v}_i\|^2 = \mathbf{v}_i^\top (A^\top A) \mathbf{v}_i = \|A\mathbf{v}_i\|^2 \geq 0, \]
all eigenvalues are non-negative. Define the singular values \(\sigma_i = \sqrt{\lambda_i} \geq 0\). Let \(r\) be the number of positive singular values.
Step 2: Construct \(U\).
For \(i = 1, \ldots, r\), define
\[ \mathbf{u}_i = \frac{A \mathbf{v}_i}{\sigma_i}. \]
These are unit vectors: \(\|\mathbf{u}_i\|^2 = \|A\mathbf{v}_i\|^2 / \sigma_i^2 = \lambda_i / \lambda_i = 1\).
They are mutually orthogonal: for \(i \neq j\),
\[ \mathbf{u}_i^\top \mathbf{u}_j = \frac{\mathbf{v}_i^\top A^\top A \mathbf{v}_j}{\sigma_i \sigma_j} = \frac{\lambda_j \mathbf{v}_i^\top \mathbf{v}_j}{\sigma_i \sigma_j} = 0. \]
Extend \(\mathbf{u}_1, \ldots, \mathbf{u}_r\) to a full orthonormal basis \(\mathbf{u}_1, \ldots, \mathbf{u}_m\) of \(\mathbb{R}^m\) by any orthonormal completion (e.g., Gram-Schmidt).
Step 3: Verify \(A = U \Sigma V^\top\).
Let \(V = [\mathbf{v}_1 \;\cdots\; \mathbf{v}_n]\) and \(U = [\mathbf{u}_1 \;\cdots\; \mathbf{u}_m]\). For \(i \leq r\):
\[ A \mathbf{v}_i = \sigma_i \mathbf{u}_i = U \Sigma \mathbf{e}_i, \]
where \(\mathbf{e}_i\) is the \(i\)-th standard basis vector and \(\Sigma\) has \(\sigma_i\) in position \((i,i)\) and zeros elsewhere.
For \(i > r\), \(\sigma_i = 0\) so \(\|A\mathbf{v}_i\|^2 = \lambda_i = 0\), meaning \(A\mathbf{v}_i = \mathbf{0} = U\Sigma\mathbf{e}_i\).
Therefore \(AV = U\Sigma\), and since \(V\) is orthogonal (\(V^\top V = I\)):
\[ A = U \Sigma V^\top. \qquad \square \]