Eigenvectors, the Spectral Theorem, and Why the SVD Always Exists

Invariant directions

For a square $A$, a non-zero $v$ with

is an eigenvector with eigenvalue $\lambda$: the map does not turn $v$ at all, it only scales it by $\lambda$. Find $n$ independent such directions and you have found the basis in which $A$ is trivial. Stack them as the columns of $P$ and, using the change-of-basis reading,

Applying $A$ a hundred times becomes $P\Lambda^{100}P^{-1}$: raise the diagonal entries to the hundredth power and stop. This is why eigenvalues govern the long-run behaviour of any repeated linear process — power iteration, Markov chains, linear recurrences, the stability of a linearised dynamical system.

When diagonalisation fails

It fails when there are not enough independent eigenvectors. The standard counterexample is the shear

Its characteristic polynomial is $(1-\lambda)^2$, so $\lambda = 1$ twice. But solving $(N - I)v = 0$ gives only the line spanned by $(1,0)^\top$: one eigendirection where two are needed. $N$ is defective and no $P$ exists. Nothing pathological is happening — a shear genuinely has only one invariant direction — but the eigendecomposition simply has no answer to give.

Even when diagonalisation succeeds, for non-symmetric $A$ the eigenvectors need not be orthogonal, $P$ can be badly conditioned, and the eigenvalues can be complex.

The symmetric case is different

If $A = A^\top$ with real entries, the spectral theorem guarantees all of the following: the eigenvalues are real, eigenvectors for distinct eigenvalues are orthogonal, and there is always an orthonormal basis of eigenvectors even with repeated eigenvalues. So

The inverse is now a transpose, which is numerically ideal. Covariance matrices, Gram matrices $X^\top X$, graph Laplacians and Hessians are all symmetric, which is why the spectral theorem does so much work in machine learning — PCA is exactly this decomposition applied to a covariance matrix.

The SVD: weaken the question, always get an answer

The eigenvalue question insists the output direction equal the input direction. Drop that. Ask instead for orthonormal directions $v_i$ in the domain that map to orthogonal directions $u_i$ in the codomain, with $Av_i = \sigma_i u_i$ and $\sigma_i \ge 0$. That question always has an answer, for any real $m \times n$ matrix, square or not:

Geometrically, since $U$ and $V$ are orthogonal, this reads rotate, scale along axes, rotate. Every linear map, however messy, is a rotation followed by an axis-aligned stretch followed by another rotation. The unit sphere is always sent to an ellipsoid whose semi-axis lengths are the singular values.

The connection to eigenvalues is one line of algebra:

$A^\top A$ is symmetric positive semi-definite, so this is its spectral decomposition: the right singular vectors are its eigenvectors, and $\sigma_i = \sqrt{\lambda_i(A^\top A)}$. Symmetrically, the left singular vectors are eigenvectors of $AA^\top$. (In practice nobody forms $A^\top A$ to compute an SVD — squaring the matrix squares its condition number — but the identity is the right mental model.)

A worked $2\times2$ example, exactly

Take

It is triangular, so its eigenvalues are 3 and 5, with eigenvectors $(1,-2)^\top/\sqrt5$ and $(0,1)^\top$ — not orthogonal, since $A$ is not symmetric.

Now the SVD. \(A^\top A = \begin{pmatrix} 25 & 20 \\ 20 & 25\end{pmatrix}\), whose eigenvalues are $25 \pm 20$, that is $45$ and $5$, with eigenvectors $(1,1)^\top/\sqrt2$ and $(1,-1)^\top/\sqrt2$. Hence

The left singular vectors follow from $u_i = Av_i/\sigma_i$. With $v_1 = (1,1)^\top/\sqrt2$ we get $Av_1 = (3, 9)^\top/\sqrt2$, and dividing by $3\sqrt5$ gives $u_1 = (1,3)^\top/\sqrt{10}$. Likewise $Av_2 = (3,-1)^\top/\sqrt2$ gives $u_2 = (3,-1)^\top/\sqrt{10}$, which is orthogonal to $u_1$ as promised.

Two sanity checks: $\sigma_1\sigma_2 = 3\sqrt5 \cdot \sqrt5 = 15 = \lvert\det A\rvert$, and $\sigma_1^2 + \sigma_2^2 = 45 + 5 = 50 = 3^2 + 0^2 + 4^2 + 5^2 = \lVert A\rVert_F^2$.

Low-rank approximation and Eckart–Young

Write the SVD as a sum of rank-one pieces, $A = \sum_i \sigma_i u_i v_i^\top$, and keep the largest $k$ terms. The Eckart–Young–Mirsky theorem says this truncation $A_k$ is optimal: among all matrices of rank at most $k$, it minimises both $\lVert A - A_k\rVert_F$ and the spectral norm $\lVert A - A_k\rVert_2$, with errors

For our $A$, the rank-one truncation is \(\sigma_1 u_1 v_1^\top = \begin{pmatrix} 1.5 & 1.5 \\ 4.5 & 4.5\end{pmatrix}\), and the residual \(A - A_1 = \begin{pmatrix} 1.5 & -1.5 \\ -0.5 & 0.5\end{pmatrix}\) has Frobenius norm $\sqrt{2.25+2.25+0.25+0.25} = \sqrt5 = \sigma_2$, exactly as the theorem predicts.

Where this shows up

PCA is the SVD of the centred data matrix; whitening, the pseudoinverse and stable rank-deficient least squares all come straight from $U\Sigma V^\top$. The condition number \(\kappa_2(A) = \sigma_{\max}/\sigma_{\min}\) — which governs error amplification and reappears in convergence rates — is about singular values, not eigenvalues.

References

1. Eckart, C., & Young, G. The approximation of one matrix by another of lower rank. Psychometrika 1(3), 211–218, 1936.
2. Trefethen, L. N., & Bau, D. Numerical Linear Algebra. SIAM, 1997 — lectures 4–5 on the SVD.
3. Golub, G. H., & Van Loan, C. F. Matrix Computations, 4th ed., ch. 2 and 8. Johns Hopkins University Press, 2013.
4. Strang, G. Introduction to Linear Algebra, 6th ed., ch. 6–7. Wellesley-Cambridge Press, 2023.
5. Halko, N., Martinsson, P.-G., & Tropp, J. A. Finding Structure with Randomness: Probabilistic Algorithms for Constructing Approximate Matrix Decompositions. SIAM Review 53(2), 217–288, 2011.