Power Iteration & Finding Dominant Eigenvectors
The simple algorithm behind PageRank and fast approximate PCA.
On this page
Beginner: section 1.7 introduced eigenvalues and eigenvectors, but never said how to actually find them by computer for a matrix too large to solve by hand. Power iteration is the simplest possible algorithm: start with any vector, repeatedly multiply it by the matrix, and normalize after each step. That's the whole algorithm.
Intermediate: why does this work? Every starting vector is (loosely speaking) a mix of all the matrix's eigenvector directions. Each multiplication by A scales the component along the dominant eigenvector (the one with the largest eigenvalue) more than every other component — so with each repetition, that direction comes to dominate the mix more and more, until essentially nothing else is left.
Advanced: the running estimate of the eigenvalue itself, at any step, is given by the Rayleigh quotient, vᵀAv / vᵀv — and this is precisely what the real QR algorithm (section 1.14's expert note) generalizes into a full, robust method for finding every eigenvalue of a matrix, not just the dominant one.
Suppose A is symmetric with orthonormal eigenvectors u₁, u₂, …, uₙ and eigenvalues |λ₁| > |λ₂| ≥ ⋯ ≥ |λₙ| (a strictly dominant top eigenvalue). Any starting vector can be written in this eigenbasis as v₀ = c₁u₁ + c₂u₂ + ⋯ + cₙuₙ. Applying A is easy in this basis, since Auᵢ = λᵢuᵢ:
Factor out the dominant term λ₁ᵏ:
Since |λ₂/λ₁| < 1, every term but the first shrinks geometrically to zero as k → ∞. After normalizing away the diverging or vanishing scale factor λ₁ᵏ, all that survives is the direction of u₁ — exactly the dominant eigenvector, and the rate of convergence is governed by the ratio |λ₂/λ₁|: the further apart the top two eigenvalues are, the faster power iteration locks on.
Where this is used: this convergence argument is exactly why PageRank (section 1.28) reliably converges regardless of the enormous size of the web graph, and why the convergence can stall badly on graphs where the top two eigenvalues happen to be close together (a known practical failure mode of naive power iteration).
Drag the starting arrow anywhere, then iterate — within a handful of steps it locks onto the same direction every time.
Twenty lines, no library eigenvalue solver needed — and this genuinely is (a simplified version of) how PageRank was originally computed at web scale.
import numpy as np
A = np.array([[3., 1.], [1., 3.]]) # symmetric, dominant eigenvalue is 4
v = np.random.rand(2)
v /= np.linalg.norm(v)
for i in range(20):
v = A @ v
v /= np.linalg.norm(v)
eigenvalue_estimate = v @ A @ v # Rayleigh quotient
print(v, eigenvalue_estimate) # converges to [0.707, 0.707]-ish direction, eigenvalue ~ 4
# Sanity check against the exact answer:
eigvals, eigvecs = np.linalg.eig(A)
print(eigvals)- PageRank (section 1.28) is power iteration applied to a web link matrix — exactly this algorithm, at a scale of billions of pages.
- Fast approximate PCA on very large datasets often uses power iteration (or its extension, Lanczos iteration) to find just the top few principal components, without ever computing a full eigendecomposition.
- Estimating a neural network's largest weight-matrix singular value (relevant to spectral normalization, section 1.20) in practice uses a fast one-step power-iteration approximation rather than a full SVD, for speed.
- Power iteration only finds the dominant eigenvalue/eigenvector — if you need all of them, you need the full QR algorithm or an eigensolver, not repeated power iteration alone.
- Convergence can be very slow if the top two eigenvalues are close in magnitude — the convergence rate depends directly on the ratio between the largest and second-largest eigenvalue.
Going deeper
Power iteration only finds the single dominant eigenvector. Inverse iteration (applying A⁻¹ instead of A) converges to the smallest eigenvalue instead, and shifted inverse iteration can target any eigenvalue near a chosen guess — the same core idea, retargeted.
At the master level: real-world eigensolvers for large sparse matrices (e.g. scipy.sparse.linalg.eigsh) use Lanczos/Arnoldi iteration, which extracts far more information from the same sequence of matrix-vector products that power iteration generates, converging to several eigenvalues at once instead of just the dominant one — it's power iteration's ideas, engineered to their full potential.