Mathematics
The Power Method for Computing Eigenvalues and Eigenvectors
Quick fact
The power method can compute the dominant eigenvalue of a matrix with just a few lines of code, yet it's the engine behind Google's original PageRank algorithm, which ranks web pages by iteratively multiplying a vector by a link matrix.
Why this is interesting
Ever wondered how Google ranks billions of web pages in an instant? Or how engineers predict whether a bridge will collapse? Both rely on a surprisingly simple trick: repeatedly multiplying a vector by a matrix until it settles into a pattern.
Read the full explanation
Understanding The Power Method for Computing Eigenvalues and Eigenvectors
Imagine you have a matrix that transforms a vector. The eigenvectors of that matrix are special vectors that, when transformed, only get stretched or shrunk, not rotated. The eigenvalue tells you how much stretching occurs. The 'dominant' eigenvector is the one with the largest stretch factor. The power method exploits a remarkable property: if you take any random starting vector and repeatedly multiply it by the matrix, the vector gradually aligns itself with the dominant eigenvector. Why? Because each multiplication amplifies the component along the dominant eigenvector more than any other component, so over time, that component dominates. To prevent numbers from exploding, we normalize the vector after each step. After many iterations, the vector points nearly in the direction of the dominant eigenvector, and the factor by which its length grew gives the dominant eigenvalue.
A deeper explanation
Let's formalize the mechanism. Suppose a matrix A has eigenvectors v1, v2, ..., vn with corresponding eigenvalues λ1, λ2, ..., λn, where |λ1| |λ2| ≥ ... ≥ |λn|. Any vector w can be expressed as a linear combination: w = c1v1 + c2v2 + ... + cnvn. Multiplying by A gives Aw = c1λ1v1 + c2λ2v2 + ... + cnλnvn. After k multiplications, we have Akw = c1λ1^k v1 + c2λ2^k v2 + ... + cnλn^k vn. Since |λ1| |λ2|, the term c1λ1^k v1 grows fastest, while the others become relatively negligible as k increases. Normalizing at each step ensures the vector doesn't overflow and converges to a multiple of v1. The eigenvalue is then approximated by the Rayleigh quotient: (x^T A x) / (x^T x), or simply by the ratio of successive norms. The method works beautifully for a dominant eigenvalue that is well-separated from the others, but it fails if the starting vector has no component along v1 (a rare and pathological case) or if the dominant eigenvalue is complex or repeated. In practice, the power method is simple, memory-efficient, and ideal for large sparse matrices, but its linear convergence rate (error decreasing by a factor of |λ2/λ1| per iteration) can be slow. This is why it forms the foundation for more sophisticated iterative methods, such as shifted inverse iteration and Rayleigh quotient iteration, and why it is so effective in applications like PageRank, where the matrix is huge and sparse.