Power Iteration

In 1998, two Stanford students needed to rank every page on the web by importance. Their insight — that a page is important if important pages link to it — reduced to a single mathematical object: the dominant eigenvector of a huge matrix encoding all the links. The algorithm they used to find it was almost embarrassingly simple.

Start with any vector. Multiply by the matrix. Normalize so the length stays controlled. Multiply again. Normalize again. Repeat until the vector stops changing.

That loop is power iteration — one of the oldest ideas in numerical linear algebra, first described by Richard von Mises and Hilda Pollaczek-Geiringer in 1929. Its convergence is not a coincidence: each multiplication amplifies the component pointing in the direction of the largest eigenvalue and shrinks every other direction. After enough steps only one direction survives.

The reason it works is the same reason a population of rabbits eventually looks like the fastest-growing demographic: the dominant mode crowds out the rest.

Pick one of the preset matrices and press Step to apply one round of multiply-then-normalize, or Run to animate until convergence. The blue arrow is the current vector; the red dashed arrow is the true dominant eigenvector.

<div class="controls">
  <label>{{lbl_matrix}}
    <select id="matrixSelect">
      <option value="asym">{{opt_asym}}</option>
      <option value="slow">{{opt_slow}}</option>
      <option value="big">{{opt_big}}</option>
    </select>
  </label>
  <button id="stepBtn" type="button">{{btn_step}}</button>
  <button id="runBtn" type="button">{{btn_run}}</button>
  <button id="resetBtn" type="button" class="ghost">{{btn_reset}}</button>
</div>
<canvas id="canvas" width="320" height="320"></canvas>
<div id="info" class="info">
  <span id="iterLabel">{{iter_label_init}}</span>
  <span id="ratioLabel">{{rq_label_init}}</span>
  <span id="convLabel"></span>
</div>

* { box-sizing: border-box; }
body { font-family: system-ui, sans-serif; color: #222; margin: 0; background: #fff; }
.controls { display: flex; flex-wrap: wrap; gap: .5rem; align-items: center; margin-bottom: .7rem; }
label { font-size: .88rem; color: #444; }
select { font-size: .88rem; padding: .3rem .5rem; border: 1px solid #ccc; border-radius: 6px; }
button { font: 600 13px system-ui; padding: .4rem .85rem; border: 1px solid #1d3557;
         background: #1d3557; color: #fff; border-radius: 7px; cursor: pointer; }
button.ghost { background: #fff; color: #1d3557; }
canvas { display: block; border: 1px solid #dde3ea; border-radius: 10px; background: #f8fafc; }
.info { display: flex; flex-wrap: wrap; gap: 1rem; margin-top: .55rem; font-size: .85rem; color: #444; }
#convLabel { color: #0a7d33; font-weight: 600; }

// Code not found

Watch how quickly the blue arrow locks onto the red one — even when you start far away. The ratio shown is the Rayleigh quotient, an estimate of the dominant eigenvalue that also converges to the true value.

Power iteration is provably correct — for any real symmetric matrix (and many non-symmetric ones) it converges to the dominant eigenvector — but its speed depends on one number: the spectral gap.

If the largest eigenvalue is λ₁ and the second-largest is λ₂, the error shrinks by a factor of roughly |λ₂/λ₁| each step. When that ratio is small (eigenvalues well separated), convergence is fast. When it is close to 1, convergence is painfully slow.

• Each step costs $O(n^{2})$ for a dense n×n matrix, or $O(nnz)$ for sparse matrices — for the web's link matrix, almost all entries are zero, so each step is cheap.
• Total iterations typically reach the desired precision in 20–100 steps; the exact count depends on the spectral gap and the starting vector.
• Failure modes: if two eigenvalues have the same magnitude but opposite sign, the iteration oscillates and never settles. Deflation (projecting out converged eigenvectors) and shifts (replacing A with A − σI) are standard fixes.

For PageRank, the link matrix has a spectral gap built in by design — a small damping factor (0.85) ensures the iteration converges in around 50–100 matrix–vector products, even for a graph with billions of nodes.

The dominant eigenvector is one of the most useful objects in applied mathematics, and power iteration is still the go-to way to compute it at scale:

• PageRank: Google's original ranking algorithm is literally power iteration on the web's link matrix. The stationary distribution of a random surfer equals the dominant eigenvector.
• Principal Component Analysis (PCA): the first principal component is the dominant eigenvector of the covariance matrix. Power iteration (or its block variant) finds it without forming the full matrix.
• Spectral clustering: algorithms that partition graphs by their second eigenvector use power iteration with deflation to reach it.
• Physics and engineering: vibration modes of structures, quantum ground states, and population models all reduce to dominant eigenvector problems.
• Recommendation systems: collaborative filtering via matrix factorization uses power-iteration-like updates to find the most informative latent directions.

Whenever a system can be described as a matrix and you care most about its strongest mode, power iteration is often the first tool you reach for — and frequently the last one you need.

Power iteration is a rare example of an algorithm where the idea and the implementation are almost the same sentence: multiply by the matrix, normalize, repeat. Its correctness follows from a simple geometric fact — repeated multiplication amplifies the dominant direction — and its practical speed comes from the spectral gap wired into the problem by design.

From a 1929 paper on eigenvalues to the index of the modern web, the same three-line loop has quietly done much of the heavy lifting. The next time you search for something and a ranked list appears in under a second, remember: somewhere upstream, a vector was multiplied by a matrix, divided by its length, and that happened a few dozen times. Simple ideas, enormous reach.

Curious how PageRank turns this into a web-ranking algorithm, or how dimensionality reduction uses the same eigenvector ideas to compress data? Both build directly on the loop you just watched.