A wall you cannot wish away
In linear algebra you met eigenvalues as the numbers lambda for which A x = lambda x has a nonzero solution x — directions that A merely stretches without rotating. And you learned where they come from: lambda is an eigenvalue exactly when det(A - lambda I) = 0. Expand that determinant and you get a polynomial in lambda, the characteristic polynomial p(lambda), and the eigenvalues are precisely its roots. So far this looks like a solved problem. Compute the polynomial, find its roots, done. The whole reason this rung exists is that this clean picture, taken literally as an algorithm, falls apart on a computer.
There are two distinct walls, and it helps to keep them apart. The first is purely mathematical and absolute: for a general matrix of size 5-by-5 or larger, there is no finite formula in radicals — no clever combination of additions, multiplications, and nth roots — that gives the eigenvalues from the matrix entries. This is the Abel-Ruffini theorem in disguise: a 5-by-5 matrix can have a characteristic polynomial of degree 5, and the general quintic has no solution by radicals. So unlike a 2-by-2 case, where the quadratic formula hands you the answer in one shot, there can be no direct closed-form eigenvalue formula at all.
The obvious workaround is a trap
"Fine," you say, "no closed form — but I already know how to find polynomial roots numerically. From root-finding I have Newton's method and friends. So just form the characteristic polynomial p(lambda), then hunt its roots iteratively." This is the second wall, and it is the subtler and more dangerous one, because the plan SOUNDS reasonable and even runs — it just returns garbage. Forming the polynomial and then rooting it is one of the worst ways known to compute eigenvalues, and seeing exactly why is the gateway to appreciating the good algorithms.
The defect is conditioning. The roots of a polynomial can be wildly sensitive to tiny changes in its coefficients, even when the matrix's eigenvalues are perfectly tame and well-separated. Wilkinson's famous warning is the polynomial whose roots are the integers 1, 2, 3, ..., 20. Nudge the coefficient of lambda^19 by about 2^(-23) — a wobble in roughly the seventh decimal place — and some roots leap by several whole units and even split off into complex pairs. The journey matrix -> coefficients -> roots threads the problem through a violently ill-conditioned middle step: the rounding you cannot avoid when you store those coefficients gets amplified catastrophically by the root-finder.
This is the rung's first lesson in the master equation accuracy = conditioning x stability. Your original problem — find the eigenvalues of A — may be perfectly well-conditioned: a small change in A moves the eigenvalues only a little. But you chose to route it through an intermediate object, the polynomial coefficients, whose root map is hideously ill-conditioned. Even a flawless root-finder running in exact arithmetic on slightly-rounded coefficients must then return badly wrong roots. No clever, stable rooting algorithm can rescue you, because the damage was done the instant you formed the coefficients. The honest moral: do not change a well-conditioned problem into an ill-conditioned one for convenience.
Backwards, and just as bad
There is a tempting symmetry here worth naming, because libraries actually exploit it — in the opposite direction. Given a polynomial, you can build a special matrix, its companion matrix, whose characteristic polynomial is exactly that polynomial; so its eigenvalues are the polynomial's roots. That is genuinely how robust software roots a polynomial: it forms the companion matrix and calls a good eigensolver. Root-finding is reduced to eigenvalue-finding, not the other way around. The arrow points from polynomials to matrices precisely because the matrix world has a stable, trustworthy tool and the coefficient world does not.
TWO ROUTES, ONE GOOD
A --> p(lambda) --> roots (the trap: ill-conditioned middle)
----------------------------
form find roots
char. poly of polynomial
p(lambda) --> companion C --> eigenvalues (what libraries do)
--------------------------------
build C run the
from coeffs QR algorithm
rule of thumb: stay in matrix-land; never round-trip through
polynomial coefficients.So both naive routes are closed: you cannot solve for eigenvalues with a formula (Abel-Ruffini), and you must not detour through the characteristic polynomial (ill-conditioning). What remains is to work on the matrix directly, with an iteration that produces a sequence lambda_0, lambda_1, lambda_2, ... creeping toward a true eigenvalue, and a matching sequence of vectors creeping toward an eigenvector. The art of the next four guides is making those sequences converge fast and, crucially, in a backward-stable way — returning the exact eigenvalues of a matrix within round-off of your A, the most an honest method can promise.
The shape of an eigensolver
It helps to see the simplest honest iteration before the polished ones. Take any starting vector and just keep multiplying it by A: v, A v, A^2 v, A^3 v, and so on (renormalizing to unit length each step so it does not blow up or vanish). If A has one eigenvalue larger in magnitude than all the rest, this sequence of directions tilts steadily toward that dominant eigenvector, and the stretch factor each step converges to the dominant eigenvalue. That is the entire idea of the power method, and it is the seed crystal from which the serious algorithms grow.
- Pick a random nonzero starting vector v_0 and scale it to length 1.
- Multiply: w = A v_n. This is the one essential operation — you only ever need to apply A to a vector, never to invert or even fully store it.
- Renormalize: v_{n+1} = w / ||w||. The length factor ||w|| is your current estimate of the dominant eigenvalue's magnitude.
- Check a stopping test — has v stopped moving, is the residual ||A v - lambda v|| small enough? — and loop back if not. You stop at "close enough," never at "exact."
Two features of that loop are the DNA of the whole rung. First, the only thing it asks of A is "multiply me by a vector." That is gold for the huge sparse matrices of real applications, where A may have billions of entries but mostly zeros — a matrix-times-vector product is cheap and you never form anything dense. Krylov methods like Lanczos and Arnoldi, later in this rung, are built entirely on that single privilege. Second, convergence speed depends on the GAP between eigenvalues: the power method crawls when the top two are close in size, and a big theme ahead is engineering bigger gaps on purpose, through shifts, to make the iteration sprint.
What this rung builds
Here is the road ahead, so the pieces snap together. Next we sharpen the power method into the power method and inverse iteration: a twin trick that, by working with (A - mu I)^{-1} for a chosen shift mu, can chase ANY eigenvalue you point it at, not just the biggest — and converge blisteringly fast. Then comes the QR algorithm, the genuine workhorse inside every numerical library's eig() routine: think of it as the power method run on a whole basis at once, cleverly reorganized so the matrix marches toward triangular form and reveals all its eigenvalues together.
A recurring relief is symmetry. When A is symmetric (A = A^T) the eigenvalues are real, the eigenvectors are orthogonal, and the whole problem becomes far better behaved — the symmetric eigenproblem has its own faster, more accurate machinery. And for matrices too big to ever write down densely, the Krylov solvers (Lanczos for symmetric, Arnoldi for general) extract a few extreme eigenvalues from nothing but those matrix-times-vector products you saw above, living entirely in a Krylov subspace.