Eigenvalue computation — power method, inverse iteration: Visual walkthrough

Step 1 — What a matrix does to an arrow

WHAT. A matrix $A$ is a machine: feed it an arrow (a vector), it spits out another arrow. Usually it both turns the arrow and changes its length.

WHY we care. Eigenvectors are the special arrows that the machine does not turn at all — it only stretches or shrinks them. If we can find those, we understand the machine completely.

PICTURE. In the figure, the grey arrows are ordinary inputs — each output (dashed) points a different way than its input. But the two coloured arrows come back pointing the same way, only longer or shorter. Those are the eigenvectors.

Figure — Eigenvalue computation — power method, inverse iteration

$λ$ can be bigger than 1 (stretch), between 0 and 1 (shrink), or negative (flip and stretch). We will meet all of these.

Step 2 — Line up the eigenvectors by strength

WHAT. Suppose our $n \times n$ matrix $A$ has $n$ eigenvectors $v_{1}, \dots, v_{n}$ , one per eigenvalue. We sort the eigenvalues by size, biggest first: $∣ λ_{1} ∣ > ∣ λ_{2} ∣ \geq \dots \geq ∣ λ_{n} ∣.$

WHY the absolute value $∣ \cdot ∣$ ? Because we care about how much an arrow gets stretched, not which way it flips. A stretch factor of $- 4$ pulls an arrow just as hard as $+ 4$ ; the length multiplies by $∣ - 4 ∣ = 4$ either way. The bars $∣ λ ∣$ measure raw stretching power.

WHY the strict $>$ at the front. We demand $∣ λ_{1} ∣$ be strictly the biggest — no ties for first place. That single champion is the dominant eigenvalue, and $v_{1}$ the dominant eigenvector. In Step 5 we'll see exactly why a tie breaks the method.

PICTURE. A "stretch-strength" bar chart: the tallest bar is $∣ λ_{1} ∣$ , standing alone above the rest. Each shorter bar is a weaker direction that will lose the race.

Step 3 — Feed the blend through the machine ONCE

WHAT. Apply $A$ to the whole mix. Matrix-times-a-sum splits across the sum, and each eigenvector obeys $A v_{i} = λ_{i} v_{i}$ : $A x_{0} = c_{1} v_{1} scaled by λ_{1} (λ_{1} v_{1}) + c_{2} v_{2} scaled by λ_{2} (λ_{2} v_{2}) + \dots + c_{n} (λ_{n} v_{n}) .$

WHY this is the key simplification. We never had to actually turn anything. Because each ingredient is an eigenvector, the machine just rescales each ingredient independently by its own $λ_{i}$ . The hard matrix multiply becomes $n$ easy number multiplies.

PICTURE. Two ingredients go in (a long $v_{1}$ -part, a short $v_{2}$ -part). After one pass, the $v_{1}$ -part has grown by factor $λ_{1}$ , the $v_{2}$ -part by the smaller $λ_{2}$ . The blended arrow already leans toward $v_{1}$ .

Step 4 — Feed it through $k$ times: the ratios appear

WHAT. Do it again and again. Each pass multiplies ingredient $i$ by $λ_{i}$ once more, so after $k$ passes each has been hit $k$ times: $A^{k} x_{0} = c_{1} λ_{1}^{k} v_{1} + c_{2} λ_{2}^{k} v_{2} + \dots + c_{n} λ_{n}^{k} v_{n} .$

$A^{k}$ means "apply the machine $k$ times".
$λ_{i}^{k}$ is the stretch factor raised to the $k$ -th power — repeated stretching compounds like interest.

Now the crucial move: pull the champion's factor $λ_{1}^{k}$ out front. $A^{k} x_{0} = λ_{1}^{k} [c_{1} v_{1} + c_{2} (\frac{λ _{2}}{λ _{1}})^{k} v_{2} + \dots + c_{n} (\frac{λ _{n}}{λ _{1}})^{k} v_{n}] .$

Outside the bracket: $λ_{1}^{k}$ , a giant overall scaling we'll cancel later by normalizing.
Inside: $c_{1} v_{1}$ sits untouched, but every other term now carries a ratio $(\frac{λ _{i}}{λ _{1}})^{k}$ .

WHY factor out $λ_{1}^{k}$ and not $λ_{2}^{k}$ or nothing? Because we want to compare every direction against the champion. Dividing each stretch by the biggest stretch turns absolute sizes into a fairness ratio: "how does runner-up $i$ measure up to the winner?" That ratio is what decides the race.

PICTURE. The equation redrawn as a stack of terms; the $c_{1} v_{1}$ term is solid and full-height, every other term is tagged with its shrinking ratio label.

Step 5 — Why every loser fades: the ratio powers die

WHAT. For every $i \geq 2$ we sorted so that $∣ λ_{i} ∣ < ∣ λ_{1} ∣$ . Therefore $\frac{λ _{i}}{λ _{1}} < 1 ⟹ \frac{λ _{i}}{λ _{1}}^{k} k \to \infty 0.$

WHY. A number smaller than 1 in size, multiplied by itself over and over, collapses to zero — like folding a paper in half again and again, its thickness fraction of the original vanishes. So inside the bracket every term except $c_{1} v_{1}$ melts away: $\frac{A ^{k} x _{0}}{λ _{1}^{k}} ⟶ c_{1} v_{1} .$ The whole iterated arrow points in the $v_{1}$ direction. The most-stretched direction wins by a landslide.

PICTURE. Ratios $r_{i} = ∣ λ_{i} / λ_{1} ∣$ plotted as decaying curves $r_{i}^{k}$ versus step $k$ . All curves dive toward the floor; the closest-to-1 curve dives slowest — that's the runner-up $r_{2}$ , and it sets the pace.

Step 6 — The degenerate sign: what if $λ_{1}$ is negative?

WHAT. Suppose the champion is negative, e.g. $λ_{1} = - 4$ . Then $λ_{1}^{k} = (- 4)^{k}$ flips sign every step: $- 4, + 16, - 64, \dots$

WHY it still works. We only ever cared about direction, and a flip $v_{1} \to - v_{1}$ is the same line, just pointing the other way. So the normalized arrow alternates between $+ v_{1}$ and $- v_{1}$ — it still locks onto the $v_{1}$ axis, it just ping-pongs across it.

PICTURE. The seed arrow shown at steps $k = 1, 2, 3, 4$ : it snaps to the $v_{1}$ line but alternates head-forward / head-backward. The line is found; only the arrowhead's side oscillates.

Step 7 — The convergence speed is a two-horse race

WHAT. After the champion, the slowest-dying term is the runner-up $v_{2}$ , because $r_{2} = ∣ λ_{2} / λ_{1} ∣$ is the ratio closest to 1. The error in direction shrinks like $error_{k} \propto \frac{λ _{2}}{λ _{1}}^{k} .$ This is linear convergence: each step multiplies the error by the same fixed factor $r_{2}$ .

WHY the gap matters. If $λ_{2}$ is far below $λ_{1}$ (small $r_{2}$ ), the error collapses fast — few steps. If $λ_{2}$ nearly ties $λ_{1}$ (r_2 close to 1), each step barely helps — painfully slow. The whole speed hinges on the gap between the top two eigenvalues.

PICTURE. Two seeds run to convergence: one matrix with a big gap ( $r_{2} = 0.2$ , error crashes down), one with a small gap ( $r_{2} = 0.9$ , error crawls). Same method, wildly different pace.

Recall More on this

The linear rate here is why shifting and inverse iteration exist — they manufacture a huge gap on purpose. See the Rayleigh Quotient Iteration and QR Algorithm notes for methods that beat linear speed. The clean split into eigen-ingredients used throughout is exactly a Spectral Decomposition; the sorting of $λ_{i}$ comes from the Characteristic Polynomial whose roots they are.

The one-picture summary

The whole story in one frame: a seed arrow $x_{0}$ is a mix of eigen-ingredients; each pass through $A$ scales the champion $v_{1}$ hardest, so after a few passes the (normalized) arrow swings onto the $v_{1}$ line — while the runner-up ratio $r_{2} = ∣ λ_{2} / λ_{1} ∣$ quietly sets how fast the swing happens.

Recall Feynman retelling — the whole walkthrough in plain words

Picture a stretchy rubber sheet with a few secret "stretch lines". Along most directions, pushing a dot both drags it and twists its heading. But along the secret lines it only stretches — no twist. Those are the eigenvectors, and how hard each stretches is its eigenvalue.

Take any starting dot. Split its arrow into how-much-of-each secret line it contains. Now push it through the sheet again and again. Every push multiplies each ingredient by its own stretch. The strongest stretch line pulls hardest, so after a handful of pushes the dot is sliding almost exactly along that one line — every other ingredient has faded to nothing because a fraction-under-one, multiplied by itself many times, disappears.

Two things can spoil it: if two lines stretch equally hard there's no clear winner and the dot never settles; and if your starting dot has zero of the strongest line, there's nothing to amplify (though a speck of noise usually saves you). If the strongest stretch is negative, the dot still finds the line — it just flips side to side each push. And the whole thing is slow or fast depending on one number: how close the runner-up's stretch is to the champion's. Big gap, instant answer; near tie, glacial. That single race between the top two stretches is the beating heart of the power method.