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.