Eigendecomposition
| Article | |
|---|---|
| Topic area | linear-algebra |
| Prerequisites | Linear Algebra, Matrix |
Overview
Eigendecomposition is the factorization of a square matrix into a canonical form expressed in terms of its eigenvalues and eigenvectors. When a matrix $ A \in \mathbb{R}^{n \times n} $ admits the decomposition $ A = Q \Lambda Q^{-1} $, where $ \Lambda $ is a diagonal matrix of eigenvalues and the columns of $ Q $ are the corresponding eigenvectors, the matrix is said to be diagonalizable. This factorization exposes the intrinsic geometry of the linear map represented by $ A $: along each eigenvector direction, the map acts as a simple scaling by the associated eigenvalue. Eigendecomposition underpins a wide range of methods in numerical Linear Algebra, statistics, signal processing, and Machine Learning, including Principal Component Analysis, spectral clustering, Markov Chain analysis, and the study of dynamical systems. It is also the conceptual foundation for more general matrix factorizations such as the Singular Value Decomposition, which extends the idea to non-square and non-diagonalizable matrices.
Intuition
A linear map can stretch, rotate, and shear vectors in complicated ways, but eigenvectors are the special directions along which the map only stretches or compresses. If $ A v = \lambda v $ for some non-zero vector $ v $ and scalar $ \lambda $, then $ v $ is an eigenvector and $ \lambda $ is its eigenvalue. Geometrically, applying $ A $ to $ v $ leaves the line spanned by $ v $ invariant; only the magnitude (and possibly sign) changes. Eigendecomposition assembles a complete basis of such invariant directions, which converts the action of $ A $ into $ n $ independent one-dimensional scalings. This is why eigendecomposition is often described as finding a coordinate system in which a linear map becomes "as simple as possible" — namely, diagonal. In that basis, computations such as repeated multiplication, matrix powers, and matrix exponentials reduce to operations on scalars.
Mathematical Formulation
Let $ A \in \mathbb{C}^{n \times n} $. The eigenvalues of $ A $ are the roots of its characteristic polynomial,
$ {\displaystyle p_A(\lambda) = \det(A - \lambda I),} $
which is a polynomial of degree $ n $. By the fundamental theorem of algebra, $ A $ has exactly $ n $ eigenvalues over $ \mathbb{C} $ counting multiplicity. For each eigenvalue $ \lambda_i $, the associated eigenvectors form the kernel of $ A - \lambda_i I $; this subspace is the eigenspace of $ \lambda_i $, and its dimension is the geometric multiplicity. The algebraic multiplicity is the multiplicity of $ \lambda_i $ as a root of $ p_A $. A matrix is diagonalizable if and only if every eigenvalue's algebraic multiplicity equals its geometric multiplicity, equivalently, if its eigenvectors span $ \mathbb{C}^n $. In that case,
$ {\displaystyle A = Q \Lambda Q^{-1}, \qquad \Lambda = \operatorname{diag}(\lambda_1, \ldots, \lambda_n),} $
where the columns of $ Q $ are eigenvectors arranged in the same order as the eigenvalues on the diagonal of $ \Lambda $. When $ A $ is real symmetric (or complex Hermitian), the Spectral Theorem guarantees that $ A $ is diagonalizable by an orthogonal (respectively unitary) matrix and that all eigenvalues are real, so $ A = Q \Lambda Q^\top $ with $ Q^\top Q = I $.
Computation
For matrices of small size, eigendecomposition can be performed by writing out the characteristic polynomial, finding its roots, and solving the corresponding linear systems for eigenvectors. This approach is numerically unstable and impractical for large $ n $ because root-finding in finite-precision arithmetic amplifies errors and the polynomial coefficients themselves can be ill-conditioned. Production numerical libraries instead use iterative algorithms. The QR algorithm, introduced by Francis and Kublanovskaya in 1961, is the dominant method for dense general matrices: it repeatedly factorizes $ A_k = Q_k R_k $ and forms $ A_{k+1} = R_k Q_k $, with shifts and a preliminary reduction to Hessenberg form to accelerate convergence. For symmetric matrices, the symmetric QR algorithm or divide-and-conquer methods on tridiagonal form achieve $ O(n^3) $ complexity with strong numerical stability.[1] When only a few extreme eigenvalues are needed, Krylov subspace methods such as the Lanczos algorithm (symmetric case) and the Arnoldi iteration (non-symmetric case) are far more efficient, requiring only matrix-vector products and dominating large-scale applications.[2]
Applications
Eigendecomposition appears throughout applied mathematics. In statistics, Principal Component Analysis performs the eigendecomposition of a sample covariance matrix to identify directions of maximum variance, providing a foundation for Dimensionality Reduction. In graph theory and unsupervised learning, spectral methods use the eigenvectors of graph Laplacians to embed nodes for clustering or partitioning. In dynamical systems, the eigenvalues of a transition matrix determine asymptotic behavior: a discrete-time linear system $ x_{k+1} = A x_k $ is stable if and only if all eigenvalues lie strictly inside the unit disk in $ \mathbb{C} $. The matrix exponential $ e^{A t} $, which solves continuous-time linear ODEs, has the closed form $ Q e^{\Lambda t} Q^{-1} $ when $ A $ is diagonalizable, with $ e^{\Lambda t} $ diagonal. In quantum mechanics, the eigenvalues of a Hermitian operator are the possible measurement outcomes, and its eigenvectors form a complete orthonormal basis for the state space. In Deep Learning, eigendecomposition appears in second-order optimization, where the eigenstructure of the Hessian characterizes local curvature.
Variants and Generalizations
Several decompositions extend or specialize the basic eigendecomposition. The Singular Value Decomposition generalizes to rectangular matrices and always exists, even when eigendecomposition fails; for a real matrix $ A $, the singular values are the square roots of the eigenvalues of $ A^\top A $. The Jordan canonical form handles non-diagonalizable matrices by producing block-diagonal "Jordan blocks" instead of pure scalars on the diagonal; it is theoretically important but numerically fragile because tiny perturbations can change the block structure. The Schur decomposition $ A = U T U^* $ with $ U $ unitary and $ T $ upper-triangular always exists for any complex square matrix and is the workhorse for stable computation: it preserves eigenvalues on the diagonal of $ T $ while avoiding the conditioning problems of full diagonalization. Generalized eigenvalue problems of the form $ A v = \lambda B v $ arise in vibration analysis and statistics and are handled by the QZ algorithm.
Limitations
Not every square matrix is diagonalizable. Defective matrices — those with fewer linearly independent eigenvectors than their dimension — admit no eigendecomposition; the simplest example is the $ 2 \times 2 $ shear matrix with both eigenvalues equal to one but only a one-dimensional eigenspace. Even when diagonalizable, the conditioning of the eigenproblem depends on the matrix structure: nearly defective matrices have eigenvector matrices $ Q $ with very large condition numbers, making $ Q^{-1} $ numerically dangerous. Non-normal matrices (those that do not commute with their conjugate transpose) can have eigenvalues that are extremely sensitive to perturbations, so eigendecomposition should be used cautiously for stability or sensitivity analysis on such matrices; the Pseudospectrum is often a more informative tool. For very large sparse matrices, computing the full eigendecomposition is usually infeasible, and iterative or randomized methods are preferred.
Comparisons
Eigendecomposition and the Singular Value Decomposition are closely related but distinct. SVD applies to any matrix and always produces orthonormal factors, making it numerically robust and the default choice for practical applications such as low-rank approximation, Pseudoinverse computation, and PCA. Eigendecomposition applies only to square matrices and may not exist, but it preserves directional information about the underlying linear map that SVD does not: SVD always returns non-negative singular values, while eigenvalues can be negative or complex, encoding rotation, reflection, and growth. The Schur decomposition is a more numerically stable cousin of eigendecomposition that is preferred whenever full diagonalization is not strictly required. The choice among these factorizations is therefore guided by whether the application needs eigenvalues, singular values, or merely a triangular reduction.