SVD, eigendecomposition and LU in practice

Three factorisations at a glance

Factorisation	Form	Exists when	Used for
Eigendecomposition	$A = S\Lambda S^{-1}$	$A$ square, with $n$ independent eigenvectors	powers, dynamics
Spectral	$A = Q\Lambda Q^\top$	$A$ real symmetric	quadratic forms, PCA
SVD	$A = U\Sigma V^\top$	every matrix	rank, low-rank approximation, least squares
LU	$A = LU$ (or $PA = LU$)	square; $PA = LU$ always works	solving systems
QR	$A = QR$	independent columns	least squares, eigenvalue algorithms
Cholesky	$A = LL^\top$	symmetric positive definite	fast solves, sampling

Eigenvalue facts used everywhere

For an $n \times n$ matrix with eigenvalues $\lambda_1, \dots, \lambda_n$, counted with multiplicity:

• $\operatorname{trace} A = \sum \lambda_i$ and $\det A = \prod \lambda_i$.
• $A^k$ has eigenvalues $\lambda_i^k$. $A^{-1}$ has $1/\lambda_i$ (when $A$ is invertible). $A + cI$ has $\lambda_i + c$, and a polynomial $p(A)$ has $p(\lambda_i)$. The eigenvectors stay the same.
• $A$ and $A^\top$ have the same eigenvalues.
• $AB$ and $BA$ have the same non-zero eigenvalues.
• Cayley–Hamilton: every matrix satisfies its own characteristic polynomial. For a $2 \times 2$ matrix, $A^2 - (\operatorname{tr} A)A + (\det A) I = 0$.

Example 1: an inverse from Cayley–Hamilton. $A = \begin{pmatrix} 2 & 1 \\ 1 & 2 \end{pmatrix}$ has trace 4 and determinant 3, so $A^2 - 4A + 3I = 0$. Multiplying by $A^{-1}$:

$A^{-1} = \frac{4I - A}{3} = \frac13\begin{pmatrix} 2 & -1 \\ -1 & 2 \end{pmatrix}.$

Example 2: a matrix polynomial. If $A$ has eigenvalues 1, 2 and 3, then $A^2 - 2A + I$ has eigenvalues $(\lambda - 1)^2$: that is 0, 1 and 4. So it is singular.

Diagonalisation

$A = S\Lambda S^{-1}$, where the columns of $S$ are the eigenvectors. It is possible exactly when $A$ has $n$ independent eigenvectors. It is guaranteed when the $n$ eigenvalues are distinct, or when $A$ is symmetric.

Defective example. $\begin{pmatrix} 1 & 1 \\ 0 & 1 \end{pmatrix}$ has the eigenvalue 1 twice, but only one eigenvector direction, $(1, 0)$, since $(A - I)v = 0$ forces $v_2 = 0$. It cannot be diagonalised. Its algebraic multiplicity is 2 and its geometric multiplicity is 1.

Powers. $A^k = S\Lambda^k S^{-1}$.

Example 3. $A = \begin{pmatrix} 2 & 1 \\ 1 & 2\end{pmatrix}$ has eigenvalues 3 and 1, with eigenvectors $(1, 1)$ and $(1, -1)$. Then

$A^k = \frac12\begin{pmatrix} 3^k + 1 & 3^k - 1 \\ 3^k - 1 & 3^k + 1 \end{pmatrix}.$

Check: with $k = 1$ this gives $\frac12\begin{pmatrix} 4 & 2 \\ 2 & 4\end{pmatrix} = A$. Correct.

The singular value decomposition

Statement. Every real $m \times n$ matrix factors as

$A = U\Sigma V^\top = \sum_{i=1}^{r} \sigma_i\, u_i v_i^\top,$

where:

• $U$ is $m \times m$ and orthogonal; its columns are the left singular vectors;
• $V$ is $n \times n$ and orthogonal; its columns are the right singular vectors;
• $\Sigma$ is $m \times n$, with singular values $\sigma_1 \ge \sigma_2 \ge \dots \ge \sigma_r > 0$ on its diagonal and zeros elsewhere;
• $r = \operatorname{rank} A$.