POWER ITERATION hit any vector with the matrix, over and over — it aligns with the biggest eigenvalue
To find the dominant eigenvector (dart 367) without solving anything: pick any vector and apply the matrix repeatedly, renormalising. Every component grows by its eigenvalue each step, so the biggest one wins — the vector rotates into alignment with the top eigenvector, and the ratio of successive lengths converges to the top eigenvalue. It is the simplest eigen-algorithm and the one behind PageRank: the web's link matrix, applied over and over to a uniform vector, settles on the stationary importance of every page — a fixed point the whole internet is ranked by.
THE TECHNIQUE iterate v → Av/‖Av‖; converges to the dominant eigenpair
The demo applies [[2,1],[1,2]] (eigenvalues 3 and 1) to a lopsided start — the Rayleigh ratio converges to the dominant eigenvalue 3: live demo
HISTORY & CREDIT von Mises & Pollaczek-Geiringer, 1929
“Eigenvalues need the characteristic polynomial.” — the dominant one falls out of just applying the matrix repeatedly; the biggest eigenvalue drowns the rest. PageRank is this, at web scale. cited
1929 · von Mises & Pollaczek-Geiringer — the power method. why · each step multiplies component i by λi; the largest dominates. 1998 · Page & Brin — PageRank: the stationary vector of the web link matrix, found by power iteration.
Apply, renormalise, repeat — the biggest eigenvalue swallows the vector, and the whole web gets ranked by the fixed point. von Mises 1929
RECOMMEND FOR I-13 the dominant eigenvalue, on the compiler
On the canonical compiler, power iteration on [[2,1],[1,2]] converges to the dominant eigenvalue 3:
$ i13 run f_poweriteration.i13 # v -> Av, Rayleigh ratio
RUN OK · 956 step(s) · peak stack 5 · call depth 32
eigval = 2.9999999999999902 -- the dominant eigenvalue 3, by repeated application
Recommend: power iteration is the fixed point as importance — apply the matrix until the vector aligns with its dominant direction — and i13 recovers eigenvalue 3; the same move ranks the web (PageRank). Not a keeper (convergence to the dominant eigenpair is witnessed). The dart that turns the abstract eigenvector into an algorithm, and the algorithm into the ranking under a trillion searches.