Eigendecomposition is a way of breaking a square matrix down into simpler pieces: a set of special directions (eigenvectors) and the scaling factors along those directions (eigenvalues). Formally, it rewrites a matrix A as the product A = PDP⁻¹, where P is a matrix whose columns are the eigenvectors, D is a diagonal matrix of eigenvalues, and P⁻¹ is the inverse of P. This factorization reveals the core behavior of a linear transformation, making it easier to analyze, compute with, and apply in fields from data science to web search.
The Core Idea in Plain Language
When a matrix acts on a vector, it usually changes both the vector’s direction and its length. But certain vectors are special: the matrix only stretches or compresses them without rotating them at all. These are the eigenvectors, and they represent the “stable directions” of the transformation. The amount each eigenvector gets stretched or compressed is its eigenvalue. An eigenvalue of 2 means the vector doubles in length. An eigenvalue of 0.5 means it shrinks to half. A negative eigenvalue flips the vector to point the opposite way while scaling it.
Eigendecomposition collects all of these eigenvectors and eigenvalues into a compact formula. Instead of thinking of a matrix as a complicated operation that does different things in different directions, you rewrite it in terms of its simplest behavior: pure scaling along a set of axes. Those axes are the eigenvectors, and the scaling amounts are the eigenvalues.
The Formula: A = PDP⁻¹
For an n×n matrix A with n linearly independent eigenvectors, the decomposition works like this:
- P is the matrix formed by placing each eigenvector as a column, side by side.
- D is a diagonal matrix with the corresponding eigenvalues along the diagonal and zeros everywhere else.
- P⁻¹ is the inverse of P, which essentially “undoes” the change of basis that P introduces.
You can read the equation A = PDP⁻¹ as a three-step process. First, P⁻¹ translates your vector into the coordinate system defined by the eigenvectors. Then D scales each component by its eigenvalue. Finally, P translates back to the original coordinate system. The result is identical to multiplying by A directly, but the middle step is trivially simple because D is diagonal.
This structure makes certain calculations dramatically easier. Raising A to a large power, for example, becomes A^k = PD^kP⁻¹, and raising a diagonal matrix to a power just means raising each diagonal entry to that power. Computing the inverse of A is similarly straightforward: A⁻¹ = PD⁻¹P⁻¹, where you simply take the reciprocal of each eigenvalue.
When Eigendecomposition Is Possible
Not every square matrix can be eigendecomposed. The key requirement is that the matrix must have n linearly independent eigenvectors for an n×n matrix. When this condition holds, the matrix is called “diagonalizable.”
The technical test involves two quantities for each eigenvalue. The algebraic multiplicity is how many times that eigenvalue appears as a root of the characteristic polynomial. The geometric multiplicity is the number of independent eigenvectors associated with it. A matrix is diagonalizable only when, for every eigenvalue, these two multiplicities match. If any eigenvalue has fewer independent eigenvectors than its algebraic multiplicity would suggest, the decomposition fails. In practice, most matrices you encounter in applied work are diagonalizable, but the exceptions matter in certain engineering and physics problems.
Eigendecomposition is also defined only for square matrices. If your matrix is rectangular (more rows than columns, or vice versa), you need a different factorization like Singular Value Decomposition, which generalizes many of the same ideas to matrices of any shape.
The Special Case of Symmetric Matrices
Real symmetric matrices (where the entry in row i, column j always equals the entry in row j, column i) have two properties that make eigendecomposition especially clean. First, all their eigenvalues are guaranteed to be real numbers, never complex. Second, eigenvectors belonging to different eigenvalues are always perpendicular to each other. This means the eigenvector matrix P is orthogonal, so P⁻¹ is just the transpose of P, which is trivial to compute. Symmetric matrices come up constantly in statistics and physics, which is one reason eigendecomposition is so widely used in those fields.
How PCA Uses Eigendecomposition
Principal Component Analysis, one of the most common techniques in data science, is eigendecomposition applied to a covariance or correlation matrix. When you have a dataset with many variables, the covariance matrix captures how all those variables move together. Eigendecomposing that matrix reveals the directions of greatest variation in the data.
The eigenvector with the largest eigenvalue points along the direction where the data varies most. The next eigenvector captures the second-most variation, and so on. Each eigenvalue tells you how much variance its direction accounts for. By keeping only the top few eigenvectors and discarding the rest, you reduce a high-dimensional dataset to a smaller number of meaningful dimensions while losing as little information as possible. The error from this approximation equals the sum of the discarded eigenvalues, so you can quantify exactly how much you’re giving up.
This same principle powers applications beyond tabular data. In image analysis, eigenvectors of an image covariance matrix (sometimes called “eigenimages” or, in facial recognition, “eigenfaces”) capture the dominant patterns of variation across a collection of images. Each image can then be represented as a short list of coordinates along those eigenvector directions instead of thousands of pixel values, making classification and recognition far more efficient.
Eigendecomposition in Google’s PageRank
The original PageRank algorithm that powered Google’s search engine is built on eigendecomposition. The web is modeled as a giant matrix M where each entry represents the probability of following a link from one page to another. A page’s importance score satisfies the equation r = Mr, which means the vector of all page rankings is an eigenvector of M with eigenvalue 1.
Specifically, PageRank is the principal eigenvector of this matrix, the one associated with the largest eigenvalue. The algorithm finds it through a process called power iteration: start with a random guess, multiply by M repeatedly, and the result converges toward the dominant eigenvector. All other eigenvectors fade away because their eigenvalues are smaller than 1, so raising them to high powers drives them toward zero. What remains is the ranking vector. The actual implementation adds a damping factor (typically around 0.85) to handle pages with no outgoing links and ensure convergence, but the core mechanism is still finding the principal eigenvector of a matrix.
Computational Cost
For an n×n matrix, eigendecomposition generally costs on the order of n³ operations. The most common numerical approach is the QR algorithm, which iteratively transforms the matrix until the eigenvalues emerge on the diagonal. The Jacobi algorithm, another iterative method, also runs in O(n³) time. A divide-and-conquer approach splits the problem recursively and runs in roughly (4/3)n³ operations.
For small to moderate matrices (a few thousand rows), these algorithms run quickly on modern hardware. For very large matrices, like the web link matrix in PageRank, computing a full decomposition is impractical. Instead, iterative methods that extract only the top few eigenvectors are used, avoiding the cost of decomposing the entire matrix.
Eigendecomposition vs. Singular Value Decomposition
Singular Value Decomposition (SVD) is a closely related factorization that works on any matrix, square or rectangular. Eigendecomposition requires a square matrix and may not exist if the matrix isn’t diagonalizable. SVD always exists. For symmetric positive-definite matrices, the two decompositions produce equivalent results: the singular values equal the eigenvalues, and the singular vectors match the eigenvectors.
In practice, the choice depends on the problem. If you’re working with a square matrix that you know is symmetric (like a covariance matrix in PCA), eigendecomposition is natural and efficient. If your data lives in a rectangular matrix, or you can’t guarantee diagonalizability, SVD is the safer and more general tool. Many software libraries compute PCA using SVD under the hood for exactly this reason, even though the mathematical motivation comes from eigendecomposition.