Eigendecomposition
Motivation
Most matrices act on different directions of space in different ways: stretching one direction, shearing another, rotating a third. The complexity of a generic matrix’s behavior comes from these mixed effects all happening at once. Eigendecomposition factors a matrix into a representation in which the only thing it does is scale — and the scaling is along a fixed set of preferred directions (Trefethen and Bau 1997).
When a matrix admits an eigendecomposition, that factorization makes matrix powers, matrix exponentials, and “iterate this transformation” problems essentially trivial. It is the foundational tool behind solving linear difference and differential equations, analyzing the long-run behavior of Markov chains, computing matrix functions like \(\exp(A)\), and understanding principal components analysis. For symmetric matrices the decomposition takes an especially clean form — the spectral theorem — which underlies the singular value decomposition.
Definition
An eigendecomposition (or spectral decomposition) of a square matrix \(A \in \mathbb{R}^{n \times n}\) is a factorization
\[ A = P D P^{-1}, \]
where:
- \(P \in \mathbb{R}^{n \times n}\) has the eigenvectors of \(A\) as its columns,
- \(D = \operatorname{diag}(\lambda_1, \ldots, \lambda_n)\) is the diagonal matrix of corresponding eigenvalues, and
- \(P\) is invertible, meaning \(A\) has \(n\) linearly independent eigenvectors.
A matrix that admits such a decomposition is called diagonalizable. Not every square matrix is diagonalizable (over \(\mathbb{R}\)) — the obstruction is studied in the diagonalization article.
The equation \(A = PDP^{-1}\) is equivalent to \(AP = PD\), which column by column reads
\[ A \mathbf{p}_i = \lambda_i \mathbf{p}_i, \]
so the columns of \(P\) are exactly the eigenvectors and the diagonal entries of \(D\) are their eigenvalues.
A \(2 \times 2\) example
Take
\[ A = \begin{pmatrix} 3 & 1 \\ 0 & 2 \end{pmatrix}. \]
From eigenvalues and eigenvectors, \(A\) has eigenvalues \(\lambda_1 = 3\) and \(\lambda_2 = 2\) with eigenvectors \(\mathbf{p}_1 = (1, 0)^\top\) and \(\mathbf{p}_2 = (1, -1)^\top\). Then
\[ P = \begin{pmatrix} 1 & 1 \\ 0 & -1 \end{pmatrix}, \quad D = \begin{pmatrix} 3 & 0 \\ 0 & 2 \end{pmatrix}, \quad P^{-1} = \begin{pmatrix} 1 & 1 \\ 0 & -1 \end{pmatrix}, \]
and direct multiplication confirms \(A = P D P^{-1}\).
Geometric Interpretation
The eigendecomposition expresses the action of \(A\) as the composition of three steps:
- \(P^{-1}\): re-express the input in the eigenbasis \(\{\mathbf{p}_1, \ldots, \mathbf{p}_n\}\). The new coordinates of a vector \(\mathbf{x}\) are the coordinates of \(\mathbf{x}\) with respect to the eigenvectors.
- \(D\): scale each eigenbasis coordinate by its eigenvalue.
- \(P\): re-express the result back in the original basis.
In the eigenbasis, \(A\) is just a coordinate-wise scaling. All the apparent complexity of \(A\) is bookkeeping introduced by working in the wrong coordinates.
For a symmetric matrix, the eigenvectors can be chosen orthonormal, so \(P\) is an orthogonal matrix and \(P^{-1} = P^\top\). The decomposition \(A = Q \Lambda Q^\top\) is a rotation, followed by axis-aligned scaling, followed by the inverse rotation — the same geometric picture as the SVD applied to a symmetric matrix.
Computing the Decomposition
The standard procedure:
- Find eigenvalues. Solve \(\det(\lambda I - A) = 0\) for the \(n\) roots \(\lambda_1, \ldots, \lambda_n\) of the characteristic polynomial.
- Find eigenvectors. For each eigenvalue \(\lambda_i\), solve \((A - \lambda_i I) \mathbf{v} = \mathbf{0}\) to find a basis of the eigenspace.
- Assemble. Stack the eigenvectors as columns of \(P\) and the eigenvalues on the diagonal of \(D\). If the total number of independent eigenvectors collected is \(n\), then \(A = PDP^{-1}\).
In symbolic work this procedure is exact. In numerical work, the characteristic polynomial is not solved directly — it is numerically ill-conditioned. Production algorithms (the \(QR\) iteration, Arnoldi iteration, Jacobi rotations) compute the eigendecomposition without ever forming the characteristic polynomial (Golub and Van Loan 2013).
Worked example
Take
\[ A = \begin{pmatrix} 4 & 1 \\ 2 & 3 \end{pmatrix}. \]
Step 1. Characteristic polynomial: \(\det(\lambda I - A) = (\lambda - 4)(\lambda - 3) - 2 = \lambda^2 - 7\lambda + 10\). Roots: \(\lambda_1 = 5, \lambda_2 = 2\).
Step 2. For \(\lambda_1 = 5\): \((A - 5I)\mathbf{v} = \mathbf{0}\) gives \(-v_1 + v_2 = 0\), so \(\mathbf{p}_1 = (1, 1)^\top\). For \(\lambda_2 = 2\): \((A - 2I)\mathbf{v} = \mathbf{0}\) gives \(2v_1 + v_2 = 0\), so \(\mathbf{p}_2 = (1, -2)^\top\).
Step 3. Assemble:
\[ P = \begin{pmatrix} 1 & 1 \\ 1 & -2 \end{pmatrix}, \quad D = \begin{pmatrix} 5 & 0 \\ 0 & 2 \end{pmatrix}, \quad P^{-1} = \tfrac{1}{-3} \begin{pmatrix} -2 & -1 \\ -1 & 1 \end{pmatrix} = \tfrac{1}{3} \begin{pmatrix} 2 & 1 \\ 1 & -1 \end{pmatrix}. \]
Check: \(PDP^{-1} = \tfrac{1}{3} \begin{pmatrix} 1 & 1 \\ 1 & -2 \end{pmatrix} \begin{pmatrix} 5 & 0 \\ 0 & 2 \end{pmatrix} \begin{pmatrix} 2 & 1 \\ 1 & -1 \end{pmatrix} = \begin{pmatrix} 4 & 1 \\ 2 & 3 \end{pmatrix} = A.\) ✓
Applications
Matrix powers
The defining payoff of eigendecomposition:
\[ A^k = P D^k P^{-1}, \qquad D^k = \operatorname{diag}(\lambda_1^k, \ldots, \lambda_n^k). \]
Computing \(A^k\) via repeated multiplication is \(\Theta(k \cdot n^3)\). Via eigendecomposition it is \(\Theta(n^3)\) for the one-time factorization plus \(\Theta(n)\) per additional power — a transformative reduction whenever \(k\) is large.
The same identity shows that the long-run behavior of \(A^k\) is governed by the eigenvalue of largest absolute value: \(A^k \approx \lambda_{\max}^k \mathbf{p}_{\max} \mathbf{q}_{\max}^\top\) for large \(k\), where \(\mathbf{q}_{\max}^\top\) is the row of \(P^{-1}\) paired with \(\lambda_{\max}\). This is the basis of the power iteration algorithm and of the analysis of Markov chain mixing.
Matrix functions
Any function \(f : \mathbb{R} \to \mathbb{R}\) expressible as a power series extends to diagonalizable matrices by applying it eigenvalue-wise:
\[ f(A) = P f(D) P^{-1}, \qquad f(D) = \operatorname{diag}(f(\lambda_1), \ldots, f(\lambda_n)). \]
The most important case is the matrix exponential:
\[ e^A = P e^D P^{-1} = P \operatorname{diag}(e^{\lambda_1}, \ldots, e^{\lambda_n}) P^{-1}. \]
This is the workhorse for solving linear ODEs \(\mathbf{x}'(t) = A\mathbf{x}(t)\), whose solution is \(\mathbf{x}(t) = e^{tA} \mathbf{x}(0)\).
Linear recurrences
A linear recurrence such as the Fibonacci sequence can be written as \(\mathbf{x}_{k+1} = A \mathbf{x}_k\), and its closed form follows from \(\mathbf{x}_k = A^k \mathbf{x}_0 = P D^k P^{-1} \mathbf{x}_0\). The eigenvalues appear as the growth rates of the sequence; the formula \(F_k = (\phi^k - \psi^k) / \sqrt{5}\) with \(\phi = (1 + \sqrt{5})/2\) comes directly from diagonalizing the \(2 \times 2\) Fibonacci matrix.
Change of basis
Equivalently, \(A = PDP^{-1}\) says that in the eigenbasis (i.e., using coordinates \(\mathbf{c} = P^{-1} \mathbf{x}\)), the matrix \(A\) acts as the diagonal \(D\). Changing variables to the eigenbasis decouples the action of \(A\) into independent one-dimensional problems.
Spectral Decomposition for Symmetric Matrices
When \(A\) is real and symmetric, the spectral theorem guarantees that the eigenvectors can be chosen orthonormal, so \(P\) is an orthogonal matrix \(Q\) and the decomposition simplifies:
\[ A = Q \Lambda Q^\top. \]
This is the form used in principal components analysis, in the proof that every matrix has a singular value decomposition, and in quadratic-form optimization.
A useful expansion follows from this:
\[ A = \sum_{i=1}^n \lambda_i \, \mathbf{q}_i \mathbf{q}_i^\top. \]
Each summand is a rank-1 outer product, and the eigenvalues weigh the contributions of the corresponding eigenvector directions. Truncating the sum to the \(k\) largest eigenvalues gives the best rank-\(k\) approximation in the spectral norm — the symmetric analog of the Eckart-Young theorem.
When Eigendecomposition Fails
Not every square matrix is diagonalizable. The matrix
\[ J = \begin{pmatrix} 0 & 1 \\ 0 & 0 \end{pmatrix} \]
has eigenvalue \(\lambda = 0\) with algebraic multiplicity \(2\) but only a one-dimensional eigenspace — there is no second linearly independent eigenvector, so no invertible \(P\) exists. This is a defective matrix.
For defective matrices, the closest analogues of eigendecomposition are the Jordan canonical form (Jordan 1870) (block-diagonal with \(1\)s on the superdiagonal) and the singular value decomposition, which exists for every matrix and provides similar computational power. In numerical work the SVD is almost always preferred, since it is stable for any matrix and avoids the discontinuous nature of the Jordan form.
The full criterion for diagonalizability — when does \(A = PDP^{-1}\) exist? — is the subject of the diagonalization article.
Properties
Eigenvalues are basis-invariant. The eigenvalues of \(A\) are the diagonal of \(D\), and they do not depend on the choice of eigenvectors. Different choices of \(P\) rearrange the order or rescale the columns; the values \(\lambda_i\) are intrinsic to \(A\).
Trace and determinant. \(\operatorname{tr}(A) = \sum_i \lambda_i\) and \(\det(A) = \prod_i \lambda_i\). Both follow from \(A = PDP^{-1}\) and the cyclic and multiplicative properties of trace and determinant.
Invertibility. \(A\) is invertible if and only if every \(\lambda_i \neq 0\). When invertible, \(A^{-1} = P D^{-1} P^{-1}\) with \(D^{-1} = \operatorname{diag}(1/\lambda_1, \ldots, 1/\lambda_n)\).
Similarity. Two diagonalizable matrices with the same eigenvalues (counting multiplicity) are similar: there exists invertible \(S\) with \(A = S B S^{-1}\). The eigenvalues are a complete invariant of the similarity class among diagonalizable matrices.