Singular Value Decomposition and Its Geometry

Definition Let $A$ be a real $m \times n$ matrix, a map from $\mathbb{R}^n$ to $\mathbb{R}^m$, and let $q = \min(m, n)$. A singular value decomposition, or SVD, of $A$ is a factorization

in which $U$ is an $m \times m$ orthogonal matrix, $V$ is an $n \times n$ orthogonal matrix, and $\Sigma$ is an $m \times n$ rectangular diagonal matrix. That means $\Sigma_{ij} = 0$ whenever $i \ne j$, and the diagonal entries $\Sigma_{ii} = \sigma_i$ for $i = 1, \dots, q$ satisfy

Every real matrix has a singular value decomposition, and the next card explains where the factors come from. Read from right to left, the factorization acts in three steps. First $V^{\top}$ gives the coordinates of an input along the orthonormal columns of $V$. Then $\Sigma$ multiplies the first $q$ coordinates by $\sigma_1, \dots, \sigma_q$, drops any coordinates beyond the $m$th, and fills the remaining output coordinates with zeros when $m > n$. Finally $U$ assembles the output from the orthonormal columns of $U$. The orthogonal factors preserve lengths and angles and may include reflections as well as rotations, so every change of length happens in $\Sigma$.

Definition The singular values of a real $m \times n$ matrix $A$ are the diagonal entries $\sigma_1 \ge \cdots \ge \sigma_q \ge 0$ of $\Sigma$ in an SVD, where $q = \min(m, n)$. They are determined by $A$ alone, whichever SVD is used. The $n \times n$ matrix $A^{\top}A$ is symmetric, and $\mathbf{x}^{\top}A^{\top}A\mathbf{x} = \lVert A\mathbf{x} \rVert^2 \ge 0$ for every $\mathbf{x}$, so its eigenvalues are real and nonnegative. If they are listed with repetition as $\lambda_1 \ge \cdots \ge \lambda_n$, then

and when $n > m$ the remaining eigenvalues $\lambda_{m+1}, \dots, \lambda_n$ are all $0$. The positive singular values are also the square roots of the positive eigenvalues of the $m \times m$ matrix $AA^{\top}$, with the same multiplicities.

This is also why an SVD exists. The spectral theorem gives an orthonormal basis $\mathbf{v}_1, \dots, \mathbf{v}_n$ of $\mathbb{R}^n$ made of eigenvectors of $A^{\top}A$, listed so that their eigenvalues decrease. For each $i$ with $\sigma_i > 0$ set $\mathbf{u}_i = A\mathbf{v}_i / \sigma_i$. These vectors are orthonormal, because

which is $1$ when $i = j$ and $0$ otherwise. The remaining $\mathbf{v}_i$ satisfy $A\mathbf{v}_i = \mathbf{0}$, since $\lVert A\mathbf{v}_i \rVert^2 = \lambda_i = 0$. Any orthonormal basis of $\mathbb{R}^m$ that extends the $\mathbf{u}_i$ gives $U$, and then $AV = U\Sigma$.

Definition In an SVD $A = U\Sigma V^{\top}$ of a real $m \times n$ matrix, the columns $\mathbf{v}_1, \dots, \mathbf{v}_n$ of $V$ are the right singular vectors, an orthonormal basis of the input space $\mathbb{R}^n$. The columns $\mathbf{u}_1, \dots, \mathbf{u}_m$ of $U$ are the left singular vectors, an orthonormal basis of the output space $\mathbb{R}^m$. Comparing columns in $AV = U\Sigma$ and in $A^{\top}U = V\Sigma^{\top}$ gives

When $n > m$, the right singular vectors without a partner satisfy $A\mathbf{v}_i = \mathbf{0}$ for $i > m$. When $m > n$, the left singular vectors without a partner satisfy $A^{\top}\mathbf{u}_i = \mathbf{0}$ for $i > n$. Each $\mathbf{v}_i$ is an eigenvector of $A^{\top}A$ and each $\mathbf{u}_i$ is an eigenvector of $AA^{\top}$, with eigenvalue $\sigma_i^2$ when $i \le q$ and eigenvalue $0$ beyond.

Definition Let $A$ be a real $m \times n$ matrix with largest singular value $\sigma_1$ and first right singular vector $\mathbf{v}_1$. Then

and the maximum is attained at $\mathbf{x} = \mathbf{v}_1$, so $\sigma_1$ equals the induced Euclidean norm $\lVert A \rVert_2$. To see this, write a unit vector as $\mathbf{x} = c_1\mathbf{v}_1 + \cdots + c_n\mathbf{v}_n$ with $c_1^2 + \cdots + c_n^2 = 1$. Then $A\mathbf{x} = \sigma_1 c_1\mathbf{u}_1 + \cdots + \sigma_q c_q\mathbf{u}_q$, and since the $\mathbf{u}_i$ are orthonormal,

When $m \ge n$ the same computation shows that the smallest stretch of a unit vector is $\sigma_n$, attained at $\mathbf{v}_n$. For an invertible $n \times n$ matrix this gives the condition number $\kappa_2(A) = \sigma_1 / \sigma_n$.

Definition Let $A = U\Sigma V^{\top}$ be an SVD of a real $m \times n$ matrix, and let $r$ be the number of positive singular values, counted with repetition. Then $\operatorname{rank} A = r$, and

where a span of no vectors means $\{\mathbf{0}\}$. The reason is that $\mathbf{x} = c_1\mathbf{v}_1 + \cdots + c_n\mathbf{v}_n$ goes to $A\mathbf{x} = \sigma_1 c_1\mathbf{u}_1 + \cdots + \sigma_r c_r\mathbf{u}_r$. These outputs fill the span of $\mathbf{u}_1, \dots, \mathbf{u}_r$, and the output is zero exactly when $c_1 = \cdots = c_r = 0$. The same argument applied to $A^{\top}\mathbf{u}_i = \sigma_i\mathbf{v}_i$ gives the other two lines. So the kernel is spanned by the right singular vectors with singular value zero together with the unpaired ones beyond index $m$. All of this is exact. When singular values are computed in floating point, a tiny value may stand for an exact zero or for a genuinely small stretch, and treating it as zero is a separate decision that should be stated.

Definition Eigenvalues and singular values answer different questions. An eigenvalue of a square matrix $A$ is a number $\lambda$ with $A\mathbf{x} = \lambda\mathbf{x}$ for some nonzero $\mathbf{x}$, so input and output are compared in the same space. A diagonalization $A = PDP^{-1}$ uses one basis on both sides, that basis need not be orthonormal, and over $\mathbb{R}$ it may not exist. Eigenvalues can be negative and need not be real. Singular values exist for every real matrix of any shape, are real and nonnegative, and come with two orthonormal bases, one for each space. For a square matrix

because $\det U$ and $\det V$ equal $\pm 1$. If $A$ is symmetric with eigenvalues $\lambda_1, \dots, \lambda_n$, its singular values are $\lvert \lambda_1 \rvert, \dots, \lvert \lambda_n \rvert$ arranged in decreasing order, and if $A$ is also positive semidefinite the two lists coincide. Symmetric positive semidefinite matrices are the only real square matrices whose eigenvalues, counted with multiplicity, are exactly their singular values, so for every other real square matrix the two lists differ.