Eigenvalues, eigenvectors, power iteration, diagonalization and Jordan form

Before this lesson: lesson 03 (determinants, singular matrices) and lesson 04 (similarity $B = M^{-1}AM$). Time: about 80 minutes, plus the notebook.

---

Why this matters #

Most vectors change direction when you apply a matrix. An eigenvector does not: $A$ only scales it. In a basis of eigenvectors the map becomes $n$ independent scalings, and $A^k$ scales each eigen-direction by $\lambda^k$. So eigenvalues decide the long-run behaviour of every linear dynamical system: a Markov chain (PageRank), gradient descent on a quadratic, a linear RNN, a time-stepper for a PDE, a climate model linearized near an equilibrium. Power iteration, the simplest eigenvalue algorithm, still estimates Hessian sharpness and the spectral norm in spectral normalization. Matrices without enough eigenvectors (defective ones) explain the $t e^{\lambda t}$ terms of critically damped systems.

1. Predict first #

2. The picture #

Start with $D = \operatorname{diag}(3, 0.5)$. It stretches $e_1$ by 3 and shrinks $e_2$ by half. These two axes keep their direction. Every other vector turns toward $e_1$, because its $e_1$ part grows faster.

Hunting for eigenvectors. Take a unit vector $x$ and split $Ax$ into a part along $x$ and a sideways part. $x$ is an eigenvector exactly when the sideways part is zero; then $Ax = \lambda x$, and the part along $x$ is $\lambda = x \cdot Ax$.

Interactive figure: loading…

Now take $A = \begin{pmatrix} 1 & 4 \\ 2 & 3 \end{pmatrix}$. Two lines are kept: $v_1 = (1, 1) \mapsto (5, 5) = 5v_1$ and $v_2 = (2, -1) \mapsto (-2, 1) = -v_2$. In the basis $(v_1, v_2)$, $A$ acts like $\operatorname{diag}(5, -1)$. For any $x = c_1 v_1 + c_2 v_2$,

so the $v_1$ part wins and $A^k x$ soon points almost along $v_1$. This is power iteration.

Two things can go wrong. The $90°$ rotation $\begin{pmatrix} 0 & -1 \\ 1 & 0 \end{pmatrix}$ keeps no real line: it turns every vector by $90°$. The shear keeps too few lines (only the horizontal axis): it is defective, and no basis of eigenvectors exists.

3. Definitions and main results #

Eigenpairs and the characteristic polynomial #

For a square $n \times n$ matrix $A$, a number $\lambda$ and a vector $v \ne 0$ with $Av = \lambda v$ are an eigenvalue and an eigenvector; together they are an eigenpair. The eigenspace $E_\lambda = N(A - \lambda I)$ holds all eigenvectors for $\lambda$, plus $0$.

From $Av = \lambda v$ to a polynomial, step by step.

1. Write $\lambda v = \lambda I v$. Then $Av = \lambda v$ is the same as $(A - \lambda I)v = 0$.
2. So an eigenvector is a nonzero vector in the null space of $A - \lambda I$.
3. A square matrix has a nonzero null vector exactly when it is singular, and a matrix is singular exactly when its determinant is 0 (lesson 03).
4. So $\lambda$ is an eigenvalue $\iff$ $\det(A - \lambda I) = 0$.

The characteristic polynomial $p(\lambda) = \det(A - \lambda I)$ has degree $n$, so over $\mathbb{C}$ it has exactly $n$ roots, counted with multiplicity. First find the roots, then find each eigenvector by solving $(A - \lambda I)v = 0$.

$2 \times 2$ case. With $\tau = \operatorname{tr} A$ (sum of the diagonal) and $\delta = \det A$:

In every size, $\sum_i \lambda_i = \operatorname{tr} A$ and $\prod_i \lambda_i = \det A$ (complex eigenvalues and repeats included).

Interactive figure: loading…

Complex eigenvalues of a real matrix #

The rotation $R = \begin{pmatrix} 0 & -1 \\ 1 & 0 \end{pmatrix}$ has $\tau = 0$ and $\delta = 1$, so $p(\lambda) = \lambda^2 + 1$. The parabola never touches the axis, and the roots are $\pm i$. With complex vectors there are eigenvectors: $R(1, -i) = (i, 1) = i\,(1, -i)$. But no real vector is an eigenvector.

What a complex pair means. Let $A$ be a real $2 \times 2$ matrix with $\tau^2 < 4\delta$.

1. The polynomial has real coefficients, so the roots are a conjugate pair $\lambda = a \pm bi$ with $b \ne 0$: $a = \tau/2$ and $b = \sqrt{\delta - \tau^2/4}$.
2. Write $\lambda = r(\cos\theta + i\sin\theta)$ with $r = |\lambda| = \sqrt{a^2 + b^2} = \sqrt{\delta}$ and the angle $\theta$.
3. There is a real basis in which $A$ has the matrix $\begin{pmatrix} a & -b \\ b & a \end{pmatrix} = r\begin{pmatrix} \cos\theta & -\sin\theta \\ \sin\theta & \cos\theta \end{pmatrix}$: a rotation by $\theta$ and a scaling by $r$ (proof in the box below).
4. So, in the coordinates of that basis, each application of $A$ turns every vector by $\theta$ and multiplies its length by $r$. No real line is kept.

Example. $A = \begin{pmatrix} 1 & -1 \\ 1 & 1 \end{pmatrix}$ has $\tau = 2$, $\delta = 2$ and $\lambda = 1 \pm i$. Here $r = \sqrt2$ and $\theta = 45°$, and indeed $A = \sqrt2\, R_{45°}$ already in the standard basis. Then $A^2 = \begin{pmatrix} 0 & -2 \\ 2 & 0 \end{pmatrix}$ (rotate by $90°$, scale by 2) and $A^8 = 16I$ (rotate by $360°$, scale by $(\sqrt2)^8 = 16$). In a linear dynamical system $x_{k+1} = Ax_k$, a complex pair gives a spiral: inward if $r < 1$, outward if $r > 1$.

The real form of a complex pair

Let $v = u + iw$ (with $u, w$ real) be an eigenvector for $\lambda = a + bi$, $b \ne 0$. Then $A(u + iw) = (a + bi)(u + iw)$, and the right side is $(au - bw) + i(bu + aw)$. $A$ is real, so the real and imaginary parts must match: $Au = au - bw$ and $Aw = bu + aw$. In the basis $(w, u)$ the first column of the matrix holds the coordinates of $Aw$, which are $(a, b)$, and the second column holds the coordinates of $Au$, which are $(-b, a)$. So $A$ has the matrix $\begin{pmatrix} a & -b \\ b & a \end{pmatrix}$ in this basis. It remains to check that $w$ and $u$ are independent, so that they form a basis. If they were dependent, both would be multiples of one real vector $z \ne 0$, so $v = \alpha z$ for a complex $\alpha \ne 0$. Then $Az = \lambda z$. But $Az$ is real and $\lambda z$ is not (because $b \ne 0$): a contradiction.

Similarity keeps eigenvalues: $\det(M^{-1}AM - \lambda I) = \det\big(M^{-1}(A - \lambda I)M\big)$, which is $\det(A - \lambda I)$, and an eigenvector $v$ of $A$ becomes $M^{-1}v$ (lesson 04). Row operations are not a similarity, so elimination changes eigenvalues.

Diagonalization #

Theorem. $A = X\Lambda X^{-1}$ with $\Lambda$ diagonal $\iff$ $A$ has $n$ independent eigenvectors. The columns of $X$ are the eigenvectors; $\Lambda$ holds their eigenvalues in the same order.

Proof.

1. $AX = X\Lambda$, read column by column, says $Ax_i = \lambda_i x_i$.
2. $X$ is invertible $\iff$ its columns are independent. Then $AX = X\Lambda$ is the same as $A = X\Lambda X^{-1}$. $\blacksquare$

Diagonalization is a change of basis. Compare with lesson 04: $A = MBM^{-1}$ with $M = X$ and $B = \Lambda$. So $\Lambda = X^{-1}AX$ is the matrix of the same map in the basis of eigenvectors. In that basis the map only stretches each coordinate.

Powers, step by step.

1. $A^2 = (X\Lambda X^{-1})(X\Lambda X^{-1})$, which is $X\Lambda (X^{-1}X) \Lambda X^{-1}$. The middle $X^{-1}X$ is $I$, so $A^2 = X\Lambda^2X^{-1}$.
2. Repeat: $A^k = X\Lambda^kX^{-1}$, and $\Lambda^k = \operatorname{diag}(\lambda_1^k, \dots, \lambda_n^k)$.
3. In words: go to eigen-coordinates ($X^{-1}$), stretch coordinate $i$ by $\lambda_i$, $k$ times ($\Lambda^k$), and go back ($X$).

Example. $A = \begin{pmatrix} 4 & -2 \\ 1 & 1 \end{pmatrix}$ (the map of lesson 04) has eigenvalues 3 and 2 (quiz above).

• $A - 3I = \begin{pmatrix} 1 & -2 \\ 1 & -2 \end{pmatrix}$, so $v_1 = (2, 1)$. $A - 2I = \begin{pmatrix} 2 & -2 \\ 1 & -1 \end{pmatrix}$, so $v_2 = (1, 1)$.
• $X = \begin{pmatrix} 2 & 1 \\ 1 & 1 \end{pmatrix}$, $\det X = 1$, $X^{-1} = \begin{pmatrix} 1 & -1 \\ -1 & 2 \end{pmatrix}$, $\Lambda^k = \operatorname{diag}(3^k, 2^k)$.
• $X\Lambda^k = \begin{pmatrix} 2 \cdot 3^k & 2^k \\ 3^k & 2^k \end{pmatrix}$ (column $i$ times $\lambda_i^k$).
• Multiply by $X^{-1}$:

Check with $k = 1$: $\begin{pmatrix} 6 - 2 & -6 + 4 \\ 3 - 2 & -3 + 4 \end{pmatrix} = A$ ✓. For $k = 3$: $A^3 = \begin{pmatrix} 46 & -38 \\ 19 & -11 \end{pmatrix}$. For large $k$ the $3^k$ terms win: $A^k \approx 3^k \begin{pmatrix} 2 & -2 \\ 1 & -1 \end{pmatrix}$, and every column points along $v_1 = (2, 1)$. That is power iteration again.

Consequences: $A^k = X\Lambda^k X^{-1}$, $A^{-1} = X\Lambda^{-1}X^{-1}$ when no $\lambda_i = 0$, and $x' = Ax$ is solved by $x(t) = X e^{\Lambda t} X^{-1} x(0)$.

Theorem. Eigenvectors for distinct eigenvalues are independent. So $n$ distinct eigenvalues imply diagonalizable.

Proof.

1. Suppose not. Take a dependence $\sum_{i \in I} c_i v_i = 0$ with all $c_i \ne 0$ and the fewest terms. It has at least two terms, because each $v_i \ne 0$.
2. Pick $j \in I$ and apply $A - \lambda_j I$: $\sum_{i \in I} c_i(\lambda_i - \lambda_j)v_i = 0$.
3. The $j$ term is gone and the other coefficients stay nonzero: a shorter dependence. Contradiction. $\blacksquare$

Power iteration #

Repeat $x_{k+1} = Ax_k / \|Ax_k\|$, and estimate the eigenvalue with the Rayleigh quotient $x_k^\top A x_k$ (here $\|x_k\| = 1$).

Theorem. Let $A$ be diagonalizable with eigenpairs $(\lambda_i, v_i)$, $|\lambda_1| > |\lambda_2| \ge \dots \ge |\lambda_n|$, and $x_0 = \sum_i c_i v_i$ with $c_1 \ne 0$. Then the line of $x_k$ converges to the line of $v_1$, with error of order $|\lambda_2/\lambda_1|^k$.

Proof.

1. Normalizing only rescales, so $x_k$ is a multiple of $A^k x_0$.
2. $A^k x_0 = \sum_i c_i \lambda_i^k v_i$. Take out the factor $c_1 \lambda_1^k$:

3. Every $|\lambda_i / \lambda_1| \le |\lambda_2/\lambda_1| < 1$, so the sum has norm at most $C\,|\lambda_2/\lambda_1|^k$, with $C = \sum_{i\ge2} |c_i/c_1|\,\|v_i\|$.
4. The scalar $c_1\lambda_1^k$ changes only length and sign (the sign alternates when $\lambda_1 < 0$), so the line of $x_k$ tends to the line of $v_1$. $\blacksquare$

Interactive figure: loading…

In practice:

• Linear convergence. Each step gains about $\log_{10}|\lambda_1/\lambda_2|$ digits and costs one product $x \mapsto Ax$, so it works for huge sparse matrices and for Hessian-vector products.
• Eigenvalue estimate. For symmetric $A$ the Rayleigh-quotient error is $O(|\lambda_2/\lambda_1|^{2k})$ (lesson 06 shows why); for non-symmetric $A$ only $O(|\lambda_2/\lambda_1|^k)$.
• Failure. $|\lambda_1| = |\lambda_2|$ with $\lambda_1 \ne \lambda_2$ (eigenvalues $1$ and $-1$, or a complex-conjugate pair): no convergence. Ratio near 1: very slow. $c_1 = 0$: in exact arithmetic $v_1$ never appears; in floating point, rounding usually adds a little of it.
• Stopping. Use the residual $\|Ax_k - \lambda x_k\|$; the test $\|x_k - x_{k-1}\|$ fails when $\lambda_1 < 0$. Shifts and inverse iteration change the ratio (lesson 14, eigenvalue algorithms).

Algebraic and geometric multiplicity #

The algebraic multiplicity $a(\lambda)$ is the multiplicity of $\lambda$ as a root of $p$. The geometric multiplicity $g(\lambda) = \dim N(A - \lambda I) = n - \operatorname{rank}(A - \lambda I)$ is the number of independent eigenvectors for $\lambda$.

Theorem. $1 \le g(\lambda) \le a(\lambda)$, and $A$ is diagonalizable (over $\mathbb{C}$) $\iff$ $g(\lambda) = a(\lambda)$ for every eigenvalue. If $g(\lambda) < a(\lambda)$ for some $\lambda$, $A$ is defective.

In words: a root that appears twice in $p$ may give two independent eigenvectors (like $I$) or only one (like the shear). Diagonalization needs the full number for every eigenvalue.

Proof of the multiplicity theorem

1. Let $g = g(\lambda_0)$. Extend a basis $v_1, \dots, v_g$ of $N(A - \lambda_0 I)$ to a basis of $\mathbb{C}^n$, the columns of $M$.
2. The first $g$ columns of $AM$ are $\lambda_0 v_i$, so $M^{-1}AM = \begin{pmatrix} \lambda_0 I_g & B \\ 0 & C \end{pmatrix}$, with characteristic polynomial $(\lambda_0 - \lambda)^g \det(C - \lambda I)$. Similarity keeps $p$, so $a(\lambda_0) \ge g$.
3. Bases of different eigenspaces together stay independent (apply the previous theorem to the parts of a dependence that lie in each eigenspace). So there are $\sum_\lambda g(\lambda)$ independent eigenvectors, and no more: every eigenvector lies in one eigenspace, so all eigenvectors span a space of dimension $\sum_\lambda g(\lambda)$. Also $\sum_\lambda a(\lambda) = n$. With each $g \le a$, the count reaches $n$ exactly when $g = a$ for every $\lambda$. $\blacksquare$

Defective example. $\begin{pmatrix} 2 & 1 \\ 0 & 2 \end{pmatrix}$: $p = (\lambda - 2)^2$, so $a(2) = 2$, but $A - 2I = \begin{pmatrix} 0 & 1 \\ 0 & 0 \end{pmatrix}$ has rank 1, so $g(2) = 1$. A repeated eigenvalue alone is not defective: $I$ has $a(1) = g(1) = n$.

Jordan form #

A defective matrix cannot be made diagonal. The best it can do is the Jordan form: diagonal blocks with ones just above the diagonal. A Jordan block is $J_m(\lambda) = \lambda I_m + N$, where $N$ has ones on the superdiagonal:

$N$ is nilpotent: $Ne_1 = 0$, $Ne_j = e_{j-1}$, $N^m = 0$. So the block has $a = m$ and $g = 1$ ($J - \lambda I = N$ has rank $m - 1$). Its basis is a chain: $e_1$ is an eigenvector, and $(J - \lambda I)e_j = e_{j-1}$ makes $e_2, \dots, e_m$ generalized eigenvectors. The shear is $J_2(1)$: $e_1$ is its only eigenvector line, and $e_2$ completes the chain.

Powers and exponentials. For a $2\times 2$ block, $N^2 = 0$ and $N$ commutes with $\lambda I$, so the binomial formula has two terms:

The extra $k$ (or $t$) comes from the nilpotent part: it is the $t e^{\lambda t}$ of ODEs with a repeated root. Even with $|\lambda| < 1$, the entry $k\lambda^{k-1}$ can grow before it decays.

The Jordan normal form theorem

Theorem (Jordan normal form). Every $A \in \mathbb{C}^{n\times n}$ can be written $A = XJX^{-1}$ with $J = \operatorname{diag}\big(J_{m_1}(\mu_1), \dots, J_{m_s}(\mu_s)\big)$, unique up to the order of the blocks. For each eigenvalue $\lambda$, the number of its blocks is $g(\lambda)$ and their total size is $a(\lambda)$. The columns of $X$ are chains: $(A - \lambda I)v = 0$, $(A - \lambda I)w_1 = v$, $(A - \lambda I)w_2 = w_1$, … . $A$ is diagonalizable $\iff$ every block is $1\times1$.

Why $J$ is the closest to diagonal.

1. Similarity keeps every number $d_j(\lambda) = \dim N\big((A - \lambda I)^j\big)$, because $M^{-1}(A - \lambda I)^j M = (M^{-1}AM - \lambda I)^j$.
2. In $J$, $d_j - d_{j-1}$ = number of blocks for $\lambda$ of size $\ge j$. So the block sizes are fixed by $A$.
3. If a block has size $\ge 2$, then $d_1 = g(\lambda) < a(\lambda)$, and no similar matrix is diagonal: the off-diagonal entries cannot be removed.
4. They can be made small, not zero: with $D = \operatorname{diag}(1, \varepsilon, \varepsilon^2, \dots)$, $D^{-1}J_m(\lambda)D$ has $\varepsilon$ on the superdiagonal. Only the pattern of nonzeros is fixed.

So two matrices are similar exactly when they have the same Jordan form. This answers the question of lesson 04: the shear $J_2(1)$ and $I = J_1(1) \oplus J_1(1)$ have the same eigenvalues but different blocks.

Numerics. The Jordan form is not continuous in $A$. $\begin{pmatrix} 2 & 1 \\ \varepsilon & 2 \end{pmatrix}$ has eigenvalues $2 \pm \sqrt{\varepsilon}$: diagonalizable for every $\varepsilon > 0$, one Jordan block at $\varepsilon = 0$. A change of size $\varepsilon$ moves the eigenvalues by $\sqrt{\varepsilon}$, and the eigenvector matrix has $\kappa(X) \approx 1/\sqrt{\varepsilon}$. Libraries use the Schur form $A = QTQ^*$ ($Q$ unitary, $T$ upper triangular) instead: it always exists and is computed stably.

Interactive figure: loading…

"Near-defective" means that the eigenvector matrix $X$ is ill-conditioned (nearly parallel eigenvectors), not that $A$ is: $\begin{pmatrix} 2 & 1 \\ \varepsilon & 2 \end{pmatrix}$ has $\kappa(A) \approx 1.64$ but $\kappa(X) \approx 1/\sqrt{\varepsilon}$.

Where are the eigenvalues? Gershgorin discs

Theorem (Gershgorin). Let $A$ be $n \times n$ (real or complex), and let $R_i = \sum_{j \ne i} |a_{ij}|$ be the sum of the absolute values of row $i$ without the diagonal entry. Every eigenvalue of $A$ lies in at least one disc $D_i = \{z \in \mathbb{C} : |z - a_{ii}| \le R_i\}$.

Proof. Let $Av = \lambda v$, $v \ne 0$, and pick $i$ with the largest $|v_i|$. Row $i$ of $Av = \lambda v$ gives $(\lambda - a_{ii})v_i = \sum_{j \ne i} a_{ij}v_j$. Divide by $v_i$ and use $|v_j / v_i| \le 1$: $|\lambda - a_{ii}| \le \sum_{j \ne i} |a_{ij}| = R_i$. $\blacksquare$

A stronger form (by continuity in the off-diagonal entries): if $k$ discs form a connected group that does not touch the other discs, the group contains exactly $k$ eigenvalues.

Example. $G = \begin{pmatrix} 5 & 1 & 0.5 \\ 0.5 & 1 & 0.5 \\ 0 & 1 & -3 \end{pmatrix}$ has the discs $D(5, 1.5)$, $D(1, 1)$ and $D(-3, 1)$. They do not touch, so each holds exactly one eigenvalue. Complex eigenvalues of a real matrix come in conjugate pairs, and each disc is symmetric about the real axis, so the single eigenvalue in each disc is real. NumPy gives $5.130$, $0.985$ and $-3.116$.

The three discs of $G$ (coloured) with their centres $a_{ii}$ on the real axis, and the three eigenvalues (black dots). One use: if every disc misses 0, then 0 is not an eigenvalue and $A$ is invertible. This is the case for a strictly diagonally dominant matrix ($|a_{ii}| > R_i$ for every row). For a graph Laplacian $L = D - W$, disc $i$ has centre and radius equal to the degree $d_i$, so every eigenvalue lies in $[0, 2d_{\max}]$.

Perron–Frobenius in two sentences

If all entries of a square matrix are positive, then the eigenvalue of largest absolute value is real, positive and simple, and its eigenvector can be chosen with all entries positive (the Perron–Frobenius theorem; it extends to nonnegative irreducible matrices). This is why a Markov chain with a positive transition matrix (and the damped PageRank matrix) has a unique stationary distribution, which power iteration finds. A softmax attention matrix is positive and row-stochastic, so $A\mathbf{1} = \mathbf{1}$, and the theorem says that this eigenvalue 1 is simple and larger in absolute value than all the others.

Answers to section 1. (1) One. The shear has $\lambda = 1$ twice ($a = 2$), but $A - I = \begin{pmatrix} 0 & 1 \\ 0 & 0 \end{pmatrix}$ has rank 1, so $g = 1$: defective. (2) The error after $k$ steps is about $r^k$ with $r = |\lambda_2/\lambda_1|$, so $k \approx 10 / \log_{10}(1/r)$: about 33 steps for $P$ ($r = 0.5$) and about 2,300 for $Q$ ($r = 0.99$).

4. Worked example #

Eigenpairs. $A = \begin{pmatrix} 1 & 4 \\ 2 & 3 \end{pmatrix}$: $\tau = 1 + 3 = 4$, $\delta = 1 \cdot 3 - 4 \cdot 2 = -5$, and $p(\lambda) = \lambda^2 - 4\lambda - 5 = (\lambda - 5)(\lambda + 1)$. Check: $5 + (-1) = \tau$, $5 \cdot (-1) = \delta$.

• $\lambda = 5$: $A - 5I = \begin{pmatrix} -4 & 4 \\ 2 & -2 \end{pmatrix}$. Row 1 says $-4v_1 + 4v_2 = 0$, so $v_1 = (1, 1)$.
• $\lambda = -1$: $A + I = \begin{pmatrix} 2 & 4 \\ 2 & 4 \end{pmatrix}$. Row 1 says $2x + 4y = 0$, so $v_2 = (2, -1)$.

$v_1 \cdot v_2 = 1 \ne 0$: $A$ is not symmetric, and its eigenvectors are not orthogonal.

Diagonalize. $X = \begin{pmatrix} 1 & 2 \\ 1 & -1 \end{pmatrix}$, $\Lambda = \operatorname{diag}(5, -1)$, $\det X = -1 - 2 = -3$, $X^{-1} = \tfrac{1}{-3}\begin{pmatrix} -1 & -2 \\ -1 & 1 \end{pmatrix} = \tfrac13 \begin{pmatrix} 1 & 2 \\ 1 & -1 \end{pmatrix}$, and

Power iteration by hand from $x_0 = (1, 0)$, without normalizing (it does not change directions): $(1, 2)$, $(9, 8)$, $(41, 42)$, $(209, 208)$. Since $x_0 = \tfrac13 (v_1 + v_2)$, $A^k x_0 = \tfrac13\big(5^k v_1 + (-1)^k v_2\big)$: the $v_2$ coefficient relative to the $v_1$ coefficient is $(-1/5)^k$. The sine of the angle to $v_1$ is $0.32, 0.059, 0.012, 0.0024$: about $\times 0.2$ per step. The Rayleigh quotient at $(209, 208)$ is $4.9952$; its error $0.0048$ is of order $0.2^4$, not $0.2^8$, because $A$ is not symmetric. (The figure in section 3 starts with these numbers.)

A defective matrix. $B = \begin{pmatrix} 1 & 1 \\ -1 & 3 \end{pmatrix}$: $\tau = 4$, $\delta = 3 + 1 = 4$, $p(\lambda) = \lambda^2 - 4\lambda + 4 = (\lambda - 2)^2$, so $a(2) = 2$. $B - 2I = \begin{pmatrix} -1 & 1 \\ -1 & 1 \end{pmatrix}$ has rank 1, so $g(2) = 1$.

• Eigenvector $v = (1, 1)$. Generalized eigenvector: $(B - 2I)w = v$ means $-w_1 + w_2 = 1$; take $w = (0, 1)$.
• $X = [v\ w] = \begin{pmatrix} 1 & 0 \\ 1 & 1 \end{pmatrix}$, $X^{-1} = \begin{pmatrix} 1 & 0 \\ -1 & 1 \end{pmatrix}$, $J = \begin{pmatrix} 2 & 1 \\ 0 & 2 \end{pmatrix}$, and $XJX^{-1} = B$.
• $J^3 = \begin{pmatrix} 8 & 12 \\ 0 & 8 \end{pmatrix}$ ($12 = 3 \cdot 2^2$), so $B^3 = XJ^3X^{-1} = \begin{pmatrix} -4 & 12 \\ -12 & 20 \end{pmatrix}$.

5. In code #

NumPy checks the hand computations above. The notebook for this lesson has these cells and the exercises.

import numpy as np

A = np.array([[1., 4.], [2., 3.]])
lam, X = np.linalg.eig(A)                        # columns of X: unit eigenvectors
lam, X = lam.real, X.real    # real here; np.linalg.eig may return complex dtype
print(lam)                                       # [-1.  5.]  (no fixed order)
print(np.allclose(X @ np.diag(lam) @ np.linalg.inv(X), A))   # True
print(round(lam.sum(), 10), round(lam.prod(), 10))           # 4.0 -5.0  (= trace, det)

# Powers through the eigenbasis: A4 = [[4,-2],[1,1]], eigenvalues 3 and 2
A4 = np.array([[4., -2.], [1., 1.]])
X4 = np.array([[2., 1.], [1., 1.]])              # v1 = (2, 1), v2 = (1, 1)
A4_3 = X4 @ np.diag([3.**3, 2.**3]) @ np.linalg.inv(X4)
print(np.round(A4_3, 10), np.allclose(A4_3, np.linalg.matrix_power(A4, 3)))
# [[ 46. -38.] [ 19. -11.]] True

# A complex pair: [[1,-1],[1,1]] = sqrt(2) times a rotation by 45 degrees
R = np.array([[1., -1.], [1., 1.]])
w = np.linalg.eigvals(R)
print(w, np.abs(w), np.degrees(np.angle(w)))
# [1.+1.j 1.-1.j] [1.41421356 1.41421356] [ 45. -45.]
print(np.linalg.matrix_power(R, 8))              # [[16. 0.] [0. 16.]]

# The theory behind power iteration: coordinates of A^k x0 in the basis (v1, v2)
V = np.array([[1., 2.], [1., -1.]])              # v1 = (1, 1), v2 = (2, -1)
x0 = np.array([1., 0.])
for k in (1, 2, 3, 4):
    c = np.linalg.solve(V, np.linalg.matrix_power(A, k) @ x0)
    print(k, round(c[1] / c[0], 4))              # (-0.2)^k: -0.2, 0.04, -0.008, 0.0016

# Multiplicities and the Jordan form of the defective example
B = np.array([[1., 1.], [-1., 3.]])
print(np.poly(B))                                # [ 1. -4.  4.]: p = (λ - 2)^2, a(2) = 2
print(2 - np.linalg.matrix_rank(B - 2 * np.eye(2)))   # 1 = g(2): defective
Xj = np.array([[1., 0.], [1., 1.]])              # columns: v = (1, 1), w = (0, 1)
J = np.array([[2., 1.], [0., 2.]])
print(np.allclose(Xj @ J @ np.linalg.inv(Xj), B))     # True
print(Xj @ np.linalg.matrix_power(J, 3) @ np.linalg.inv(Xj))   # [[-4. 12.] [-12. 20.]]

# Near-defective: eigenvalues move like sqrt(eps), the eigenvector matrix degrades
for eps in (1e-6, 1e-10):
    w, Xe = np.linalg.eig(np.array([[2., 1.], [eps, 2.]]))
    print(eps, np.round(w.real, 6), f"{np.linalg.cond(Xe):.0f}")
    # 1e-06 [2.001 1.999] 1000      then      1e-10 [2.00001 1.99999] 100000

np.poly gives the coefficients of the characteristic polynomial, and matrix_rank uses a tolerance on the singular values. The exact Jordan form needs exact arithmetic (for example SymPy's Matrix.jordan_form); in floating point it is ill-posed, as the last loop shows.

6. Where it shows up #

• PageRank and Markov chains. The stationary distribution is the eigenvector for the eigenvalue $1$ of the column-stochastic Google matrix. With damping $d = 0.85$, every other eigenvalue has $|\lambda| \le d$, so power iteration converges like $0.85^k$, whatever the size of the graph.
• Sharpness and spectral normalization. Power iteration needs only products: $v \mapsto Hv$ (Hessian-vector products by autodiff) or $v \mapsto W^\top W v$. Spectral normalization runs one power-iteration step per training step to track $\sigma_{\max}(W)$.
• RNNs and linear recurrences. $h_k = W^k h_0$ grows or shrinks like $|\lambda_i|^k$: exploding or vanishing signals and gradients. A complex pair makes the state rotate (oscillate) while it grows or decays. A defective or non-normal $W$ can still grow first.
• ML for science: stability and modes. Near an equilibrium, $\dot x \approx J_f x$ ($J_f$ the Jacobian) is stable when every $\operatorname{Re}\lambda < 0$; a time-stepper $u_{k+1} = Gu_k$ needs spectral radius $\rho(G) \le 1$. Dynamic mode decomposition fits a linear operator to snapshots of a flow or climate field; its eigenvalues are the growth rates and frequencies of the modes. The critically damped oscillator $\ddot x + 2\omega\dot x + \omega^2 x = 0$ has the matrix $\begin{pmatrix} 0 & 1 \\ -\omega^2 & -2\omega \end{pmatrix}$, a double eigenvalue $-\omega$ with one eigenvector, and the solution $(c_1 + c_2 t)e^{-\omega t}$.

7. Common mistakes #

• Row reducing before finding eigenvalues. Elimination is not a similarity; it changes them.
• Reading eigenvalues from the diagonal of a full matrix. This works only for triangular (or diagonal) matrices: $\begin{pmatrix} 4 & -2 \\ 1 & 1 \end{pmatrix}$ has eigenvalues 3 and 2, not 4 and 1.
• "Repeated eigenvalue ⇒ not diagonalizable." False: $I$ is diagonal. Defective means $g < a$. Distinct eigenvalues imply diagonalizable, not the other way round.
• Mixing up diagonalizable and invertible. $\operatorname{diag}(1, 0)$ is diagonalizable and singular; the shear is invertible and defective.
• Expecting real eigenvalues and orthogonal eigenvectors from any real matrix. Only symmetric matrices guarantee that (lesson 06). A rotation has complex eigenvalues.
• Power iteration details. Not normalizing (overflow or underflow); stopping on $\|x_k - x_{k-1}\|$ when $\lambda_1 < 0$; running it when $|\lambda_1| = |\lambda_2|$.
• Comparing eigenvectors with a library without fixing scale and sign. Eigenvectors are defined only up to a nonzero factor (and up to a basis choice in an eigenspace of dimension $> 1$).
• Computing a Jordan form in floating point. It is ill-posed; use the Schur form or the SVD.

8. Check yourself #

1. Find the eigenpairs of $\begin{pmatrix} 0 & 1 \\ -2 & -3 \end{pmatrix}$ and check them.
   Answer

   $p(\lambda) = \lambda^2 + 3\lambda + 2 = (\lambda + 1)(\lambda + 2)$. $\lambda = -1$ with $(1, -1)$; $\lambda = -2$ with $(1, -2)$. Sum $-3$ = trace, product $2$ = det.
2. $A$ has eigenvalues $1, -1, 0.5$. Does power iteration converge? How can you fix it?
   Answer

   No: $|\lambda_1| = |\lambda_2| = 1$, so the iterate keeps a part $(-1)^k c_2 v_2$ and alternates between two directions. Shift: $A + I$ has the same eigenvectors and eigenvalues $2, 0, 1.5$, so $2$ is strictly dominant with ratio $0.75$.
3. $|\lambda_2/\lambda_1| = 0.9$. About how many iterations shrink the eigenvector error by $10^6$? And the Rayleigh-quotient error of a symmetric matrix?
   Answer

   $k \approx 6/\log_{10}(1/0.9) \approx 131$. The symmetric Rayleigh-quotient error behaves like $0.81^k$, so about 66 iterations.
4. A $3\times3$ matrix has the single eigenvalue 2 and $\operatorname{rank}(A - 2I) = 1$. What is its Jordan form?
   Answer

   $g(2) = 3 - 1 = 2$ blocks with total size 3: $J_2(2) \oplus J_1(2)$. (Rank 0 would give $2I$; rank 2 would give one block $J_3(2)$.)
5. Why is $\begin{pmatrix} 2 & 7 \\ 0 & 3 \end{pmatrix}$ diagonalizable, without computing eigenvectors?
   Answer

   It is triangular, so its eigenvalues are the diagonal entries 2 and 3. They are distinct, so the eigenvectors are independent.
6. $J = \begin{pmatrix} 0.9 & 1 \\ 0 & 0.9 \end{pmatrix}$. What happens to the (1,2) entry of $J^k$?
   Answer

   It is $k \cdot 0.9^{k-1}$. It grows to about $3.87$ at $k = 9$ and $10$, then decays to 0. $|\lambda| < 1$ guarantees decay only in the long run.
7. The real matrix $\begin{pmatrix} 0 & -2 \\ 2 & 0 \end{pmatrix}$ has which eigenvalues? What does it do to the plane?
   Answer

   $\tau = 0$, $\delta = 4$, so $\lambda^2 + 4 = 0$ and $\lambda = \pm 2i$. $|\lambda| = 2$ and $\theta = 90°$: it rotates every vector by $90°$ and doubles its length. It is $2R_{90°}$.

Recall cardsAnswer in your head first, then reveal. Add the cards to your review deck to see them again just before you would forget.

1. Define an eigenvalue and an eigenvector of $A$.

   Show answer

2. Why is $\lambda$ an eigenvalue exactly when $\det(A - \lambda I) = 0$?

   Show answer

3. Write the characteristic polynomial of a $2 \times 2$ matrix with trace $\tau$ and determinant $\delta$.

   Show answer

4. How are the eigenvalues related to the trace and the determinant?

   Show answer

5. What does a complex pair $a \pm bi$ mean for a real $2 \times 2$ matrix?

   Show answer

6. When is $A$ diagonalizable, and what is $A^k$ then?

   Show answer

7. Compute the eigenvalues of $\begin{pmatrix} 4 & -2 \\ 1 & 1 \end{pmatrix}$.

   Show answer

8. At what rate does power iteration converge?

   Show answer

9. Define algebraic and geometric multiplicity.

   Show answer

10. Give a defective $2 \times 2$ matrix and its multiplicities.

    Show answer

Add these cards to my reviewOpen the review →

9. Interview angle #

• "Top eigenvalue of a $10^9 \times 10^9$ sparse matrix?" — power iteration (or Lanczos/Arnoldi) with matrix-vector products only; rate $|\lambda_2/\lambda_1|$; one sparse product per step.
• "Why does PageRank converge, and how fast?" — damping makes the eigenvalue 1 dominant, with $|\lambda_2| \le d = 0.85$.
• "Is every matrix diagonalizable?" — no, $\begin{pmatrix} 1 & 1 \\ 0 & 1 \end{pmatrix}$. Sufficient: $n$ distinct eigenvalues, or a symmetric matrix.
• "Where does $t e^{\lambda t}$ come from?" — a Jordan block: $e^{Jt} = e^{\lambda t}(I + tN)$.
• "Why don't libraries return the Jordan form?" — it jumps under tiny perturbations; they use the Schur form.

10. Practice #

The notebook for this lesson runs in Colab. It has five exercises, each with a check cell and a folded solution:

1. Eigenvalues of a $2 \times 2$ matrix from the trace and the determinant, real or complex.
2. Write power_iteration with normalization and a residual stopping test (a demo before it plots the error against $|\lambda_2/\lambda_1|^k$).
3. PageRank: build the damped Google matrix of a small link graph and rank the pages with your power iteration.
4. Algebraic and geometric multiplicity, and an is_diagonalizable test, on diagonalizable and defective examples.
5. Powers of a Jordan block: the closed form $J^k = \lambda^k I + k\lambda^{k-1}N$ and the transient growth of $k\lambda^{k-1}$.

11. Watch and read #

Eigenvectors and eigenvalues3Blue1Brown · Essence of linear algebra, chapter 14 · 17 min

Watch for the vectors that stay on their own line, and for the rotation that has none.

A quick trick for computing eigenvalues3Blue1Brown · Essence of linear algebra, chapter 15 · 13 min

Diagonalization and Powers of AGilbert Strang · MIT 18.06 (2010), lecture 22 · 52 min

Similar Matrices and Jordan FormGilbert Strang · MIT 18.06 (2010), lecture 28 · 46 min

Eigenvalue Power MethodJeffrey Chasnov · Numerical Methods for Engineers, lecture 30 · 11 min

• 3Blue1Brown, Eigenvectors and eigenvalues: the text version of chapter 14, with the picture of the kept lines.
• Gilbert Strang, MIT 18.06 (2010), lecture 21: Eigenvalues and eigenvectors and lecture 22: Diagonalization and powers of A.
• Driscoll and Braun, Fundamentals of Numerical Computation, §8.2 Power iteration (free online book).
• Sheldon Axler, Linear Algebra Done Right, 4th edition, free PDF: §5D "Diagonalizable operators", §8A "Generalized eigenvectors and nilpotent operators", §8C (subsection "Jordan form").