ml.lab
Python sleeps until you run code
04 Eigenvectors and eigenvalues

Lesson 2 of 4

Powers, stability and explosion

Apply a matrix again and again and every vector splits into eigen-directions, each multiplied by its own eigenvalue at every step. That one fact explains diagonalization, power iteration, stability, and why recurrent networks struggle to learn from the distant past.

About 80 minutes
By the end you can
  • Compute Akx\mathbf{A}^k\mathbf{x} by writing x\mathbf{x} in the basis of eigenvectors.

  • Derive A=PDP−1\mathbf{A} = \mathbf{P}\mathbf{D}\mathbf{P}^{-1} and Ak=PDkP−1\mathbf{A}^k = \mathbf{P}\mathbf{D}^k\mathbf{P}^{-1}, and read them as a change of basis.

  • Predict from the spectral radius whether repeated multiplication decays, explodes or sits on the edge, and know when that prediction needs care.

  • Implement power iteration and explain why it finds the dominant eigenvector, and how fast.

  • Explain why the eigenvalues of a recurrent weight matrix decide whether gradients vanish or explode.

Here are two matrices that look almost the same:

W1=[0.60.50.50.6],W2=[0.50.40.40.5].\mathbf{W}_1 = \begin{bmatrix} 0.6 & 0.5 \\ 0.5 & 0.6 \end{bmatrix}, \qquad \mathbf{W}_2 = \begin{bmatrix} 0.5 & 0.4 \\ 0.4 & 0.5 \end{bmatrix}.

Every entry of W2\mathbf{W}_2 is 0.1 smaller. Start both at x=(1,0)\mathbf{x} = (1,\allowbreak 0) and multiply by the matrix 50 times. W150x≈(58.7,58.7)\mathbf{W}_1^{50}\mathbf{x} \approx (58.7,\allowbreak 58.7), a vector of length about 83. W250x≈(0.0026,0.0026)\mathbf{W}_2^{50}\mathbf{x} \approx (0.0026,\allowbreak 0.0026), a vector of length about 0.0036. After 50 steps one result is roughly 23,000 times longer than the other.

The explanation is in the eigenvalues. Both matrices have the eigenvectors (1,1)(1,\allowbreak 1) and (1,−1)(1,\allowbreak -1):

  • W1(1,1)=(1.1,1.1)\mathbf{W}_1(1,\allowbreak 1) = (1.1,\allowbreak 1.1) and W2(1,1)=(0.9,0.9)\mathbf{W}_2(1,\allowbreak 1) = (0.9,\allowbreak 0.9), so along (1,1)(1,\allowbreak 1) the eigenvalues are 1.1 and 0.9.
  • Both send (1,−1)(1,\allowbreak -1) to (0.1,−0.1)(0.1,\allowbreak -0.1), so along (1,−1)(1,\allowbreak -1) both multiply by 0.1, and that part of x\mathbf{x} is gone after a few steps.

And 1.150≈1171.1^{50} \approx 117 while 0.950≈0.00520.9^{50} \approx 0.0052. (The start (1,0)(1,\allowbreak 0) is half of (1,1)(1,\allowbreak 1) plus half of (1,−1)(1,\allowbreak -1), which is where 58.7≈117/258.7 \approx 117/2 and 0.0026≈0.0052/20.0026 \approx 0.0052/2 come from; the first section below shows that move.) A small difference in an eigenvalue becomes an enormous difference after many steps.

A recurrent network does this kind of repeated multiplication, both when it carries information forward through a sentence and when its training signal travels backward. This lesson makes the idea precise, and it is the most important link in Part 1: the eigenvalues you meet here return as vanishing and exploding gradients in module 7 and as the reason the LSTM's cell state works in module 8.

The plan: first watch what a matrix does to each eigen-direction on its own; then write that as a formula for every power (diagonalization); then ask which direction wins in the long run; and finally connect it to recurrent networks.

Each eigen-direction on its own

The whole lesson rests on one move: split the starting vector into eigenvectors, because the matrix treats each piece separately. Let us see that with numbers.

Take B=[0.80.20.40.6]\mathbf{B} = \begin{bmatrix} 0.8 & 0.2 \\ 0.4 & 0.6 \end{bmatrix}. It is the matrix A=[4123]\mathbf{A} = \begin{bmatrix} 4 & 1 \\ 2 & 3 \end{bmatrix} from the previous lesson divided by 5. Dividing a matrix by 5 divides every output by 5: if Av=λv\mathbf{A}\mathbf{v} = \lambda\mathbf{v}, then 15Av=λ5v\tfrac15\mathbf{A}\mathbf{v} = \tfrac{\lambda}{5}\mathbf{v}. So B\mathbf{B} has the same eigenvectors, v1=(1,1)\mathbf{v}_1 = (1,\allowbreak 1) and v2=(1,−2)\mathbf{v}_2 = (1,\allowbreak -2), with eigenvalues 5/5=15/5 = 1 and 2/5=0.42/5 = 0.4. Start from x=(3,0)\mathbf{x} = (3,\allowbreak 0).

Step 1: write x\mathbf{x} in eigenvectors. We want numbers c1,c2c_1,\allowbreak c_2 with c1(1,1)+c2(1,−2)=(3,0)c_1(1,\allowbreak 1) + c_2(1,\allowbreak -2) = (3,\allowbreak 0). The left side is (c1+c2, c1−2c2)(c_1 + c_2,\allowbreak \ c_1 - 2c_2), so matching entries gives two equations:

c1+c2=3,c1−2c2=0.c_1 + c_2 = 3, \qquad c_1 - 2c_2 = 0.

The second says c1=2c2c_1 = 2c_2. Put that into the first: 2c2+c2=32c_2 + c_2 = 3, so 3c2=33c_2 = 3 and c2=1c_2 = 1. Then c1=2c2=2c_1 = 2c_2 = 2. Check: 2(1,1)+1(1,−2)=(2+1, 2−2)=(3,0)2(1,\allowbreak 1) + 1(1,\allowbreak -2) = (2 + 1,\allowbreak \ 2 - 2) = (3,\allowbreak 0).

Step 2: apply B\mathbf{B} once, using linearity. B\mathbf{B} acts on each piece separately, and each piece is an eigenvector, so each piece is only multiplied by its eigenvalue:

Bx=2 Bv1+1 Bv2linearity=2(1) v1+1(0.4) v2Bvi=λivi=(2,2)+(0.4,−0.8)write out the vectors=(2.4, 1.2).\begin{aligned} \mathbf{B}\mathbf{x} &= 2\,\mathbf{B}\mathbf{v}_1 + 1\,\mathbf{B}\mathbf{v}_2 && \text{linearity} \\ &= 2(1)\,\mathbf{v}_1 + 1(0.4)\,\mathbf{v}_2 && \mathbf{B}\mathbf{v}_i = \lambda_i\mathbf{v}_i \\ &= (2, 2) + (0.4, -0.8) && \text{write out the vectors} \\ &= (2.4,\ 1.2). \end{aligned}

Direct check: B(3,0)\mathbf{B}(3,\allowbreak 0) is 3 times the first column, 3(0.8,0.4)=(2.4,1.2)3(0.8,\allowbreak 0.4) = (2.4,\allowbreak 1.2).

Step 3: repeat. The result is again 2 of v1\mathbf{v}_1 plus some amount of v2\mathbf{v}_2, so the next application does the same thing: the first coefficient is multiplied by 1 again and the second by 0.4 again. After kk steps,

Bkx=2(1)k(1,1)+(0.4)k(1,−2)=(2+0.4k, 2−2⋅0.4k).\mathbf{B}^k\mathbf{x} = 2(1)^k(1, 1) + (0.4)^k(1, -2) = \big(2 + 0.4^k,\ 2 - 2 \cdot 0.4^k\big).
kk0.4k0.4^kBkx\mathbf{B}^k\mathbf{x}
01(3,0)(3,\allowbreak 0)
10.4(2.4,1.2)(2.4,\allowbreak 1.2)
20.16(2.16,1.68)(2.16,\allowbreak 1.68)
30.064(2.064,1.872)(2.064,\allowbreak 1.872)
large→0\to 0→(2,2)\to (2,\allowbreak 2)

The component along (1,−2)(1,\allowbreak -2) fades away. The component along (1,1)(1,\allowbreak 1) stays exactly as it was. No matrix multiplication was needed after the first step: once you know the eigen-coordinates, you know every power.

Go slower: Why the formula holds for every k

For one step, use linearity and then the definition of an eigenvector:

Ax=A(c1v1+⋯+cnvn)=c1Av1+⋯+cnAvn=c1λ1v1+⋯+cnλnvn.\mathbf{A}\mathbf{x} = \mathbf{A}(c_1\mathbf{v}_1 + \cdots + c_n\mathbf{v}_n) = c_1\mathbf{A}\mathbf{v}_1 + \cdots + c_n\mathbf{A}\mathbf{v}_n = c_1\lambda_1\mathbf{v}_1 + \cdots + c_n\lambda_n\mathbf{v}_n.

The result is again a combination of the same eigenvectors, with new coefficients ciλic_i\lambda_i. So suppose the formula holds after kk steps, Akx=∑iciλikvi\mathbf{A}^k\mathbf{x} = \sum_i c_i\lambda_i^k\mathbf{v}_i. Apply A\mathbf{A} once more with the same reasoning, now with coefficients ciλikc_i\lambda_i^k:

Ak+1x=∑iciλik Avi=∑iciλikλi vi=∑iciλik+1 vi.\mathbf{A}^{k+1}\mathbf{x} = \sum_i c_i\lambda_i^k\,\mathbf{A}\mathbf{v}_i = \sum_i c_i\lambda_i^k\lambda_i\,\mathbf{v}_i = \sum_i c_i\lambda_i^{k+1}\,\mathbf{v}_i.

It holds for k=1k = 1, and each step carries it to the next, so it holds for every kk.

Read the formula for what it says about the long run. Each term is multiplied by λi\lambda_i at every step, so:

  • A component with ∣λ∣<1|\lambda| < 1 dies: λk→0\lambda^k \to 0.
  • A component with ∣λ∣>1|\lambda| > 1 explodes: ∣λ∣k→∞|\lambda|^k \to \infty.
  • A component with ∣λ∣=1|\lambda| = 1 keeps its size. With λ=1\lambda = 1 it stays put; with λ=−1\lambda = -1 it flips sign every step.
  • The largest ∣λ∣|\lambda| wins. After enough steps the term with the biggest ∣λi∣|\lambda_i| dwarfs the others, so Akx\mathbf{A}^k\mathbf{x} points along that eigenvector, provided x\mathbf{x} had some component along it to begin with.

The instrument below runs this experiment and draws it. It multiplies a start x0\mathbf{x}_0 by the matrix again and again. On the plane, each xk\mathbf{x}_k is drawn at length 1 on the circle, so it stays on screen however long it gets, with a fading trail of earlier steps; the two lime lines are the eigen-directions, and the brighter one has the larger ∣λ∣|\lambda|. The readouts and the chart under the plane keep the true length ∣xk∣|\mathbf{x}_k|, on a log scale.

It starts from x0=(0,1)\mathbf{x}_0 = (0,\allowbreak 1), which is 13(1,1)−13(1,−2)\tfrac13(1,\allowbreak 1) - \tfrac13(1,\allowbreak -2) (check: (13−13, 13+23)=(0,1)\big(\tfrac13 - \tfrac13,\allowbreak \ \tfrac13 + \tfrac23\big) = (0,\allowbreak 1)). The instrument scales v1\mathbf{v}_1 and v2\mathbf{v}_2 to length 1, so its formula shows c1=2/3≈0.47c_1 = \sqrt{2}/3 \approx 0.47 and c2=−5/3≈−0.75c_2 = -\sqrt{5}/3 \approx -0.75: the same split, measured against unit-length eigenvectors.

The edits in steps 4 and 5 use a handy fact: adding c Ic\,\mathbf{I} to a matrix adds cc to every eigenvalue and keeps the eigenvectors, because (A+cI)v=Av+cv=λv+cv=(λ+c)v(\mathbf{A} + c\mathbf{I})\mathbf{v} = \mathbf{A}\mathbf{v} + c\mathbf{v} = \lambda\mathbf{v} + c\mathbf{v} = (\lambda + c)\mathbf{v}.

The widget always started from a vector with some of each eigenvector in it. Which starting vectors lose everything instead? Decide from their eigen-coordinates.

Quick checkWhich starting vectors fade

Let B=[0.80.20.40.6]\mathbf{B} = \begin{bmatrix} 0.8 & 0.2 \\ 0.4 & 0.6 \end{bmatrix}, with eigenvector (1,1)(1,\allowbreak 1) for λ=1\lambda = 1 and (1,−2)(1,\allowbreak -2) for λ=0.4\lambda = 0.4. Starting from which vectors does Bkx\mathbf{B}^k\mathbf{x} shrink all the way to 0\mathbf{0} as kk grows? Select every one.

Choose every option that applies, then check.

Diagonalization: the same idea as matrices

The three steps above work, but they are a recipe in words. Written as three matrices they become a formula, and the formula turns every power of a matrix into powers of plain numbers.

Put the eigenvectors side by side as the columns of a matrix P\mathbf{P}, and the eigenvalues, in the same order, on the diagonal of a matrix D\mathbf{D} (zeros everywhere else). For our B\mathbf{B}:

P=[111−2],D=[1000.4].\mathbf{P} = \begin{bmatrix} 1 & 1 \\ 1 & -2 \end{bmatrix}, \qquad \mathbf{D} = \begin{bmatrix} 1 & 0 \\ 0 & 0.4 \end{bmatrix}.

The definition Avi=λivi\mathbf{A}\mathbf{v}_i = \lambda_i\mathbf{v}_i, written for all columns at once, is AP=PD\mathbf{A}\mathbf{P} = \mathbf{P}\mathbf{D} (the box below checks this column by column). If the eigenvectors are independent, P\mathbf{P} has an inverse (a square matrix with independent columns is invertible, from rank and low-rank updates), and multiplying both sides on the right by P−1\mathbf{P}^{-1} gives

A=PDP−1.\mathbf{A} = \mathbf{P}\mathbf{D}\mathbf{P}^{-1}.

This is diagonalization.

Go slower: Why A P = P D, column by column

The column view of matrix multiplication says that column ii of AP\mathbf{A}\mathbf{P} is A\mathbf{A} times column ii of P\mathbf{P}, which is Avi\mathbf{A}\mathbf{v}_i.

Column ii of PD\mathbf{P}\mathbf{D} is P\mathbf{P} times column ii of D\mathbf{D}. That column of D\mathbf{D} is all zeros except λi\lambda_i in position ii, so P\mathbf{P} times it picks out λi\lambda_i times column ii of P\mathbf{P}, which is λivi\lambda_i\mathbf{v}_i.

So "AP=PD\mathbf{A}\mathbf{P} = \mathbf{P}\mathbf{D}" says "Avi=λivi\mathbf{A}\mathbf{v}_i = \lambda_i\mathbf{v}_i for every ii". Now multiply both sides on the right by P−1\mathbf{P}^{-1}: APP−1=PDP−1\mathbf{A}\mathbf{P}\mathbf{P}^{-1} = \mathbf{P}\mathbf{D}\mathbf{P}^{-1}. Since PP−1=I\mathbf{P}\mathbf{P}^{-1} = \mathbf{I}, the left side is AI=A\mathbf{A}\mathbf{I} = \mathbf{A}, so A=PDP−1\mathbf{A} = \mathbf{P}\mathbf{D}\mathbf{P}^{-1}.

Read it right to left, as a change of basis. In span, basis and coordinates you saw that the coordinates of a vector depend on the basis you measure it in. Applying A=PDP−1\mathbf{A} = \mathbf{P}\mathbf{D}\mathbf{P}^{-1} to x\mathbf{x} means applying P−1\mathbf{P}^{-1} first, then D\mathbf{D}, then P\mathbf{P}:

  1. P−1x\mathbf{P}^{-1}\mathbf{x} gives the coordinates c=(c1,c2)\mathbf{c} = (c_1,\allowbreak c_2) of x\mathbf{x} in the eigenvector basis. The reason: c1v1+c2v2c_1\mathbf{v}_1 + c_2\mathbf{v}_2 is Pc\mathbf{P}\mathbf{c} (the columns of P\mathbf{P} added up in the amounts c\mathbf{c}), so x=Pc\mathbf{x} = \mathbf{P}\mathbf{c} and c=P−1x\mathbf{c} = \mathbf{P}^{-1}\mathbf{x}.
  2. Dc\mathbf{D}\mathbf{c} scales each coordinate by its eigenvalue. In this basis the matrix is just a list of independent stretches.
  3. P\mathbf{P} turns the scaled coordinates back into an ordinary vector.

These are Steps 1 to 3 of the previous section, written as matrices. The diagram below makes the three moves with B\mathbf{B} and x=(3,0)\mathbf{x} = (3,\allowbreak 0), the same numbers as before. It shows the plane, with the v1\mathbf{v}_1 family in lime and the v2\mathbf{v}_2 family in teal, and beside it (below it on a phone) the vectors and the matrices P\mathbf{P}, D\mathbf{D} and P−1\mathbf{P}^{-1}, colored to match. Each step lights up what is new in lime, and the text under the figure writes out that step's arithmetic.

Powers only touch the middle. Step 5 of the diagram used a cancellation. Here it is one move per line:

A2=(PDP−1)(PDP−1)two copies=PD (P−1P) DP−1regroup (matrix products are associative)=PD I DP−1P−1P=I=PD2P−1I changes nothing, and DD=D2\begin{aligned} \mathbf{A}^2 &= (\mathbf{P}\mathbf{D}\mathbf{P}^{-1})(\mathbf{P}\mathbf{D}\mathbf{P}^{-1}) && \text{two copies} \\ &= \mathbf{P}\mathbf{D}\,(\mathbf{P}^{-1}\mathbf{P})\,\mathbf{D}\mathbf{P}^{-1} && \text{regroup (matrix products are associative)} \\ &= \mathbf{P}\mathbf{D}\,\mathbf{I}\,\mathbf{D}\mathbf{P}^{-1} && \mathbf{P}^{-1}\mathbf{P} = \mathbf{I} \\ &= \mathbf{P}\mathbf{D}^2\mathbf{P}^{-1} && \mathbf{I} \text{ changes nothing, and } \mathbf{D}\mathbf{D} = \mathbf{D}^2 \end{aligned}
Go slower: The general power

Write Ak\mathbf{A}^k as kk copies of PDP−1\mathbf{P}\mathbf{D}\mathbf{P}^{-1} side by side:

Ak=(PDP−1)(PDP−1)⋯(PDP−1).\mathbf{A}^k = (\mathbf{P}\mathbf{D}\mathbf{P}^{-1})(\mathbf{P}\mathbf{D}\mathbf{P}^{-1})\cdots(\mathbf{P}\mathbf{D}\mathbf{P}^{-1}).

Matrix multiplication is associative, so we may regroup freely. Every P−1\mathbf{P}^{-1} that sits against the next P\mathbf{P} becomes I\mathbf{I} and disappears. There are k−1k - 1 such meeting points, and what remains is the first P\mathbf{P}, the kk copies of D\mathbf{D}, and the last P−1\mathbf{P}^{-1}:

Ak=PDkP−1.\mathbf{A}^k = \mathbf{P}\mathbf{D}^k\mathbf{P}^{-1}.

Powers of a diagonal matrix are easy, because multiplying two diagonal matrices multiplies matching diagonal entries and leaves zeros elsewhere. For example

D2=[λ100λ2][λ100λ2]=[λ1200λ22],\mathbf{D}^2 = \begin{bmatrix} \lambda_1 & 0 \\ 0 & \lambda_2 \end{bmatrix}\begin{bmatrix} \lambda_1 & 0 \\ 0 & \lambda_2 \end{bmatrix} = \begin{bmatrix} \lambda_1^2 & 0 \\ 0 & \lambda_2^2 \end{bmatrix},

and in general Dk\mathbf{D}^k has λ1k,…,λnk\lambda_1^k,\allowbreak \ldots,\allowbreak \lambda_n^k on its diagonal.

A worked example

For A=[4123]\mathbf{A} = \begin{bmatrix} 4 & 1 \\ 2 & 3 \end{bmatrix} with eigenvalues 5 and 2, the eigenvectors (1,1)(1,\allowbreak 1) and (1,−2)(1,\allowbreak -2) give

P=[111−2],D=[5002].\mathbf{P} = \begin{bmatrix} 1 & 1 \\ 1 & -2 \end{bmatrix}, \qquad \mathbf{D} = \begin{bmatrix} 5 & 0 \\ 0 & 2 \end{bmatrix}.

Invert P\mathbf{P}. The 2x2 inverse formula from module 3 swaps the diagonal entries, negates the other two, and divides by the determinant. Here det⁡P=(1)(−2)−(1)(1)=−3\det\mathbf{P} = (1)(-2) - (1)(1) = -3, so

P−1=1−3[−2−1−11]=[2/31/31/3−1/3].\mathbf{P}^{-1} = \frac{1}{-3}\begin{bmatrix} -2 & -1 \\ -1 & 1 \end{bmatrix} = \begin{bmatrix} 2/3 & 1/3 \\ 1/3 & -1/3 \end{bmatrix}.

Raise D\mathbf{D} to the power. D3\mathbf{D}^3 has 53=1255^3 = 125 and 23=82^3 = 8 on its diagonal. Multiplying P\mathbf{P} on the right by a diagonal matrix scales its columns, so PD3\mathbf{P}\mathbf{D}^3 is the first column times 125 and the second times 8:

PD3=[1258125−16].\mathbf{P}\mathbf{D}^3 = \begin{bmatrix} 125 & 8 \\ 125 & -16 \end{bmatrix}.

Multiply by P−1\mathbf{P}^{-1}. Each entry of A3=(PD3)P−1\mathbf{A}^3 = (\mathbf{P}\mathbf{D}^3)\mathbf{P}^{-1} is a row of the left matrix dotted with a column of the right one:

row 1, column 1:125⋅23+8⋅13=250+83=2583=86row 1, column 2:125⋅13+8⋅(−13)=125−83=1173=39row 2, column 1:125⋅23+(−16)⋅13=250−163=2343=78row 2, column 2:125⋅13+(−16)⋅(−13)=125+163=1413=47\begin{aligned} \text{row 1, column 1:}&\quad 125 \cdot \tfrac23 + 8 \cdot \tfrac13 = \tfrac{250 + 8}{3} = \tfrac{258}{3} = 86 \\ \text{row 1, column 2:}&\quad 125 \cdot \tfrac13 + 8 \cdot \big(-\tfrac13\big) = \tfrac{125 - 8}{3} = \tfrac{117}{3} = 39 \\ \text{row 2, column 1:}&\quad 125 \cdot \tfrac23 + (-16) \cdot \tfrac13 = \tfrac{250 - 16}{3} = \tfrac{234}{3} = 78 \\ \text{row 2, column 2:}&\quad 125 \cdot \tfrac13 + (-16) \cdot \big(-\tfrac13\big) = \tfrac{125 + 16}{3} = \tfrac{141}{3} = 47 \end{aligned}

So A3=[86397847]\mathbf{A}^3 = \begin{bmatrix} 86 & 39 \\ 78 & 47 \end{bmatrix}. Check by brute force: A2=[16+24+38+62+9]=[1871411]\mathbf{A}^2 = \begin{bmatrix} 16 + 2 & 4 + 3 \\ 8 + 6 & 2 + 9 \end{bmatrix} = \begin{bmatrix} 18 & 7 \\ 14 & 11 \end{bmatrix}, and then

A3=A2A=[72+1418+2156+2214+33]=[86397847].\mathbf{A}^3 = \mathbf{A}^2\mathbf{A} = \begin{bmatrix} 72 + 14 & 18 + 21 \\ 56 + 22 & 14 + 33 \end{bmatrix} = \begin{bmatrix} 86 & 39 \\ 78 & 47 \end{bmatrix}.

For A100\mathbf{A}^{100} the eigen route is the same work as for A3\mathbf{A}^3, apart from raising two plain numbers to the 100th power, while multiplying one factor at a time costs 99 matrix products.

To recap: writing x\mathbf{x} in the eigenvector basis turns Akx\mathbf{A}^k\mathbf{x} into c1λ1kv1+c2λ2kv2c_1\lambda_1^k\mathbf{v}_1 + c_2\lambda_2^k\mathbf{v}_2, and the same fact for the whole matrix is Ak=PDkP−1\mathbf{A}^k = \mathbf{P}\mathbf{D}^k\mathbf{P}^{-1}. Either way, a power costs one change of basis and a few powers of plain numbers.

Diagonalization also runs in reverse: choose the eigenvectors and eigenvalues you want, and PDP−1\mathbf{P}\mathbf{D}\mathbf{P}^{-1} builds the matrix that has them.

Work it outBuild a matrix from its eigenvectors

A 2x2 matrix has eigenvector (1,0)(1,\allowbreak 0) with eigenvalue 2 and eigenvector (1,1)(1,\allowbreak 1) with eigenvalue 3. Build it as PDP−1\mathbf{P}\mathbf{D}\mathbf{P}^{-1} and enter the four entries of the matrix. They are whole numbers.

A

One entry per box, row by row (Tab moves along a row). 0.25, -2, 3/4 and sqrt(2) all work. Enter moves to the next empty box and checks once all are filled.

Now use the eigen route for a power you would not want to compute by brute force.

On paperThe tenth power by hand

Let A=[0121]\mathbf{A} = \begin{bmatrix} 0 & 1 \\ 2 & 1 \end{bmatrix} and v=(1,5)\mathbf{v} = (1,\allowbreak 5). Compute A10v\mathbf{A}^{10}\mathbf{v} by hand, without multiplying ten matrices.

  1. Find the eigenvalues and eigenvectors of A\mathbf{A}.
  2. Write v\mathbf{v} as a combination of the eigenvectors.
  3. Use the powers formula.

Enter the result below as a column. Both entries are whole numbers.

Work it on real paper: writing each step is the point. Then check your final answer here and compare your working with the walk-through.

A^10 v, as a column

One entry per box, top to bottom. 0.25, -2, 3/4 and sqrt(2) all work. Enter moves to the next empty box and checks once all are filled.

When there is no eigenbasis

Diagonalization needed nn independent eigenvectors. Two cases from the previous lesson do not have them in real numbers.

Defective matrices. The shear S=[1101]\mathbf{S} = \begin{bmatrix} 1 & 1 \\ 0 & 1 \end{bmatrix} has only one eigen-direction, so there is no invertible P\mathbf{P} and no diagonalization. Its powers are easy to find directly:

S2=[1101][1101]=[11+101]=[1201],\mathbf{S}^2 = \begin{bmatrix} 1 & 1 \\ 0 & 1 \end{bmatrix}\begin{bmatrix} 1 & 1 \\ 0 & 1 \end{bmatrix} = \begin{bmatrix} 1 & 1 + 1 \\ 0 & 1 \end{bmatrix} = \begin{bmatrix} 1 & 2 \\ 0 & 1 \end{bmatrix},

and each further factor adds 1 to the corner, so Sk=[1k01]\mathbf{S}^k = \begin{bmatrix} 1 & k \\ 0 & 1 \end{bmatrix}. The eigenvalue is 1, yet Sk(0,1)=(k,1)\mathbf{S}^k(0,\allowbreak 1) = (k,\allowbreak 1) grows without bound, linearly in kk. Defective matrices are rare in practice (nudge the entries by tiny random amounts and the result is almost surely diagonalizable), but they show that eigenvalues of size exactly 1 do not settle the question.

Complex eigenvalues. Diagonalization still works if P\mathbf{P} and D\mathbf{D} are allowed complex entries, and λk\lambda^k still has modulus ∣λ∣k|\lambda|^k. For a scaled rotation (rotate by an angle θ\theta and scale by rr), kk applications rotate by kθk\theta and scale by rkr^k. The direction keeps turning, and the length is governed by ∣λ∣=r|\lambda| = r.

In every case, the sizes ∣λi∣|\lambda_i| decide growth. That leads to one number.

Who wins: the spectral radius and power iteration

Every component is multiplied by its own λ\lambda at every step, so in the long run the only question is which ∣λ∣|\lambda| is largest. That size gets a name, and the same "largest wins" fact becomes an algorithm.

The spectral radius of a square matrix is the largest eigenvalue size:

ρ(A)=max⁡i ∣λi∣,\rho(\mathbf{A}) = \max_i\,|\lambda_i|,

where ∣λ∣|\lambda| is the absolute value for a real eigenvalue and the modulus for a complex one. It sorts the long run into three cases:

  • ρ(A)<1\rho(\mathbf{A}) < 1: Akx→0\mathbf{A}^k\mathbf{x} \to \mathbf{0} for every x\mathbf{x}. (This holds even for defective matrices, where the argument needs more machinery than we have built.)
  • ρ(A)>1\rho(\mathbf{A}) > 1: ∣Akx∣|\mathbf{A}^k\mathbf{x}| grows without bound for almost every x\mathbf{x}. The exceptions are the vectors with no component at all along any eigen-direction whose ∣λ∣|\lambda| is above 1, and a randomly chosen vector essentially never is one.
  • ρ(A)=1\rho(\mathbf{A}) = 1: the eigenvalues alone do not decide. A rotation keeps every length, the shear grows linearly, and B\mathbf{B} above settles down to a fixed vector.
Go slower: The powers of C, line by line

Split C\mathbf{C} into a multiple of I\mathbf{I} plus the rest: C=0.5 I+N\mathbf{C} = 0.5\,\mathbf{I} + \mathbf{N} with N=[0300]\mathbf{N} = \begin{bmatrix} 0 & 3 \\ 0 & 0 \end{bmatrix}. Two facts make the powers easy. First, N2=[0300][0300]=0\mathbf{N}^2 = \begin{bmatrix} 0 & 3 \\ 0 & 0 \end{bmatrix}\begin{bmatrix} 0 & 3 \\ 0 & 0 \end{bmatrix} = \mathbf{0}. Second, I\mathbf{I} commutes with everything, so IN=NI=N\mathbf{I}\mathbf{N} = \mathbf{N}\mathbf{I} = \mathbf{N}.

Claim: Ck=0.5k I+k⋅0.5k−1 N\mathbf{C}^k = 0.5^k\,\mathbf{I} + k \cdot 0.5^{k-1}\,\mathbf{N}. At k=1k = 1 it reads 0.5 I+N0.5\,\mathbf{I} + \mathbf{N}, which is C\mathbf{C}.

One more factor. Suppose the claim holds for kk and multiply by C=0.5 I+N\mathbf{C} = 0.5\,\mathbf{I} + \mathbf{N}, expanding the four products:

(0.5k I+k 0.5k−1 N)(0.5 I+N)=0.5k+1 I+0.5k N+k 0.5k N+k 0.5k−1 N2.\big(0.5^k\,\mathbf{I} + k\,0.5^{k-1}\,\mathbf{N}\big)\big(0.5\,\mathbf{I} + \mathbf{N}\big) = 0.5^{k+1}\,\mathbf{I} + 0.5^k\,\mathbf{N} + k\,0.5^k\,\mathbf{N} + k\,0.5^{k-1}\,\mathbf{N}^2.

The last term is zero because N2=0\mathbf{N}^2 = \mathbf{0}. The two middle terms add to (k+1) 0.5k N(k + 1)\,0.5^k\,\mathbf{N}. So Ck+1=0.5k+1 I+(k+1) 0.5k N\mathbf{C}^{k+1} = 0.5^{k+1}\,\mathbf{I} + (k + 1)\,0.5^{k}\,\mathbf{N}, which is the claim for k+1k + 1.

Apply it to (0, 1). I(0,1)=(0,1)\mathbf{I}(0,\allowbreak 1) = (0,\allowbreak 1) and N(0,1)=(3,0)\mathbf{N}(0,\allowbreak 1) = (3,\allowbreak 0), so Ck(0,1)=0.5k(0,1)+k 0.5k−1(3,0)=(3k⋅0.5k−1, 0.5k)\mathbf{C}^k(0,\allowbreak 1) = 0.5^k(0,\allowbreak 1) + k\,0.5^{k-1}(3,\allowbreak 0) = (3k \cdot 0.5^{k-1},\allowbreak \ 0.5^k). At k=10k = 10 that is (30/512, 1/1024)≈(0.059,0.001)(30/512,\allowbreak \ 1/1024) \approx (0.059,\allowbreak 0.001), of length about 0.06.

Power iteration

The "largest wins" rule is also an algorithm. To find the dominant eigenvector (the one whose eigenvalue has the largest size), start from almost any vector and keep multiplying by A\mathbf{A}, rescaling to length 1 after every step. This is power iteration:

xk+1=Axk∣Axk∣.\mathbf{x}_{k+1} = \frac{\mathbf{A}\mathbf{x}_k}{|\mathbf{A}\mathbf{x}_k|}.

Why it works: factor λ1k\lambda_1^k out of the powers formula, where λ1\lambda_1 is the dominant eigenvalue (we assume it is strictly larger in size than every other eigenvalue),

Akx=λ1k(c1v1+c2(λ2λ1)kv2+⋯ ).\mathbf{A}^k\mathbf{x} = \lambda_1^k\left(c_1\mathbf{v}_1 + c_2\left(\frac{\lambda_2}{\lambda_1}\right)^{k}\mathbf{v}_2 + \cdots\right).

Every ratio ∣λi/λ1∣|\lambda_i/\lambda_1| is below 1, so everything in the bracket except c1v1c_1\mathbf{v}_1 fades, with the slowest term shrinking like ∣λ2/λ1∣k|\lambda_2/\lambda_1|^k (here λ2\lambda_2 is the second-largest in size). The factor λ1k\lambda_1^k in front only changes the length, and the rescaling removes it, which also stops the numbers from overflowing or underflowing.

Once xk\mathbf{x}_k is a unit eigenvector, the eigenvalue can be read off with one dot product. Axk=λ1xk\mathbf{A}\mathbf{x}_k = \lambda_1\mathbf{x}_k, so xk⋅(Axk)=λ1 (xk⋅xk)=λ1\mathbf{x}_k\cdot(\mathbf{A}\mathbf{x}_k) = \lambda_1\,(\mathbf{x}_k\cdot\mathbf{x}_k) = \lambda_1, because a unit vector dotted with itself is 1. This estimate keeps the sign of λ1\lambda_1, which a ratio of lengths would lose.

Watch it on A=[4123]\mathbf{A} = \begin{bmatrix} 4 & 1 \\ 2 & 3 \end{bmatrix} from (1,0)(1,\allowbreak 0), skipping the rescaling so the numbers stay whole. Each row is the previous one times A\mathbf{A}; for example A(18,14)=(72+14, 36+42)=(86,78)\mathbf{A}(18,\allowbreak 14) = (72 + 14,\allowbreak \ 36 + 42) = (86,\allowbreak 78). The direction is measured by the slope y/xy/x, which should approach 1, the slope of (1,1)(1,\allowbreak 1):

kkAk(1,0)\mathbf{A}^k(1,\allowbreak 0)slope y/xy/xdistance from 1
0(1,0)(1,\allowbreak 0)01
1(4,2)(4,\allowbreak 2)0.50.5
2(18,14)(18,\allowbreak 14)0.7780.222
3(86,78)(86,\allowbreak 78)0.9070.093
4(422,406)(422,\allowbreak 406)0.9620.038
5(2094,2062)(2094,\allowbreak 2062)0.9850.015

Divide each distance by the one before: 0.5/1=0.50.5/1 = 0.5, then 0.222/0.5≈0.440.222/0.5 \approx 0.44, 0.093/0.222≈0.420.093/0.222 \approx 0.42, 0.038/0.093≈0.410.038/0.093 \approx 0.41 and 0.015/0.038≈0.400.015/0.038 \approx 0.40. The factor approaches 0.40.4, which is ∣λ2/λ1∣=2/5|\lambda_2/\lambda_1| = 2/5. When the top two eigenvalues are close in size, that factor is close to 1 and convergence is slow. When c1=0c_1 = 0 it fails, though a random start almost never has c1c_1 exactly zero. And when the dominant eigenvalues are a complex pair, the direction keeps rotating and never settles.

To recap this section: the spectral radius ρ=max⁡∣λ∣\rho = \max|\lambda| decides the long run (decay below 1, explosion above 1, no verdict at exactly 1), the first few steps can still grow even when ρ<1\rho < 1, and power iteration turns "the largest wins" into a way to find the winner, gaining a factor ∣λ2/λ1∣|\lambda_2/\lambda_1| per step.

Now write the tools of this lesson in code: power iteration, powers through PDkP−1\mathbf{P}\mathbf{D}^k\mathbf{P}^{-1}, the spectral radius and a stability verdict.

Code itPower iteration and a stability check

Build the tools of this lesson.

  • power_iteration(A, x0, steps): multiply, rescale to length 1, repeat. Return the estimate λ=v⋅(Av)\lambda = \mathbf{v}\cdot(\mathbf{A}\mathbf{v}) and the unit vector v\mathbf{v}.
  • matrix_power_eig(A, k): Ak=PDkP−1\mathbf{A}^k = \mathbf{P}\mathbf{D}^k\mathbf{P}^{-1}, with P\mathbf{P} and the eigenvalues from np.linalg.eig.
  • spectral_radius(A): ρ(A)=max⁡i∣λi∣\rho(\mathbf{A}) = \max_i|\lambda_i|.
  • stability(A): the long-run verdict from ρ(A)\rho(\mathbf{A}): 'decays', 'explodes' or 'borderline'.

Do not call np.linalg.matrix_power inside your functions; the tests use it to check you.

⌘+Enter runsPython sleeps until you run code
Write your code where the starter says raise NotImplementedError, then press Run tests. Each check says what it expects.

For fluency with the powers formula, here is a practice set with fresh matrices each time.

Practice setPowers reps
3 correct in a row completes the set. A miss starts the count again.

The matrix A=[11.50−0.5]\mathbf{A} = \begin{bmatrix}1 & 1.5 \\ 0 & -0.5\end{bmatrix} has eigenvectors p1=(−1,1)\mathbf{p}_1 = (-1,\allowbreak 1) with λ1=−12\lambda_1 = -\tfrac{1}{2} and p2=(1,0)\mathbf{p}_2 = (1,\allowbreak 0) with λ2=1\lambda_2 = 1. Use them to compute A9v\mathbf{A}^{9}\mathbf{v} for v=[3−2]\mathbf{v} = \begin{bmatrix}3 \\ -2\end{bmatrix}. Give each entry to 2 decimal places.

A^9 v

One entry per box, top to bottom. 0.25, -2, 3/4 and sqrt(2) all work. Enter moves to the next empty box and checks once all are filled.

Why this is the heart of Part 1

Everything so far was about one matrix multiplying a vector again and again. A recurrent network does exactly that, and the eigenvalues decide whether it can learn from anything but the last few steps.

Module 7 builds a recurrent neural network (RNN). It reads a sequence one step at a time and keeps a hidden state ht\mathbf{h}_t, a vector updated by the same weight matrix W\mathbf{W} at every step:

ht=tanh⁡(Wht−1+Uxt+b),\mathbf{h}_t = \tanh(\mathbf{W}\mathbf{h}_{t-1} + \mathbf{U}\mathbf{x}_t + \mathbf{b}),

where xt\mathbf{x}_t is the input at step tt, U\mathbf{U} and b\mathbf{b} are more learned numbers (module 7 names the two matrices Whh\mathbf{W}_{hh} and Wxh\mathbf{W}_{xh}), and tanh⁡\tanh squashes each entry into (−1,1)(-1,\allowbreak 1). To train it, we need to know how the loss depends on early states, and backpropagation through time will derive that each step backward multiplies the gradient by W⊤\mathbf{W}^\top and by a diagonal matrix of tanh slopes. Going kk steps back means kk such factors.

Set the tanh slopes aside for a moment (they are at most 1). The core is then (W⊤)kg(\mathbf{W}^\top)^k\mathbf{g} for a gradient vector g\mathbf{g}. W⊤\mathbf{W}^\top has the same eigenvalues as W\mathbf{W}:

det⁡(W⊤−λI)=det⁡((W−λI)⊤)=det⁡(W−λI).\det(\mathbf{W}^\top - \lambda\mathbf{I}) = \det\big((\mathbf{W} - \lambda\mathbf{I})^\top\big) = \det(\mathbf{W} - \lambda\mathbf{I}).

The first step uses I⊤=I\mathbf{I}^\top = \mathbf{I}, so (W−λI)⊤=W⊤−λI(\mathbf{W} - \lambda\mathbf{I})^\top = \mathbf{W}^\top - \lambda\mathbf{I}; the second uses the fact that a matrix and its transpose have the same determinant. Same characteristic polynomial, same eigenvalues. So everything in this lesson applies: a gradient from kk steps back is scaled by roughly ρ(W)k\rho(\mathbf{W})^k.

Three rows of identical stations joined in a chain, with a glowing pulse travelling along each row. In the top row the pulse shrinks by the same fraction at every station until it is a faint speck; in the middle row it keeps exactly the same size; in the bottom row it grows by the same fraction at every station until it floods the last station.The same factor at every step: a little below 1 and the signal fades away, exactly 1 and it holds, a little above 1 and it explodes.

Here is that experiment with a random 64×6464 \times 64 matrix. The code rescales it so its spectral radius is exactly 1, then multiplies it by 0.9, 1.0 and 1.1, sends the same random gradient back 100 steps through each, and plots the gradient's size after each step, as a multiple of its starting size, on a log scale.

⌘+Enter runs · edit freelyPython sleeps until you run code

Because each W\mathbf{W} is ρ\rho times the same matrix G, (W⊤)kg(\mathbf{W}^\top)^k\mathbf{g} is exactly ρk\rho^k times the ρ=1\rho = 1 result. So read the ρ=1\rho = 1 line first. Over the first 30 or so steps it falls, with some wobble, from 1 to about 0.45, as the parts of the gradient along eigenvectors with smaller ∣λ∣|\lambda| die out. After that it stays in a narrow band, between about 0.33 and 0.46. It does not sit perfectly still because the two largest eigenvalues of this random matrix are a complex pair, both of modulus 1: the part of the gradient that survives keeps turning inside a plane, and its length wobbles as it turns. At step 100 it happens to be 0.43.

The other two lines are that same curve tilted by log⁡10ρ\log_{10}\rho per step, about −0.046-0.046 for 0.9 and +0.041+0.041 for 1.1. Over 100 steps the tilt is a factor of 0.9100≈0.0000270.9^{100} \approx 0.000027 on one side and 1.1100≈13,8001.1^{100} \approx 13{,}800 on the other. That is exactly how the two printed numbers relate to 0.43: 0.43×0.000027≈0.0000110.43 \times 0.000027 \approx 0.000011 and 0.43×13,800≈5,9000.43 \times 13{,}800 \approx 5{,}900.

Neither extreme is usable. A vanished gradient means the network gets no signal about how its early inputs affected the loss, so it cannot learn dependencies that far back. An exploded gradient throws the weights into chaos, which is why module 7 clips gradients.

How fast does a factor below 1 erase a signal? Put a number on it.

Work it outHow fast 0.9 erases a signal

In a recurrent network, suppose a gradient component is multiplied by 0.9 at every step back in time. After how many steps is it smaller than 1% of its starting size for the first time? Enter a whole number of steps.

steps

Type a number: 0.25, -2, 3/4 and sqrt(2) all work. Enter checks.

The instrument below runs the same experiment on a small tanh RNN, with 8 hidden units, whose recurrent matrix is ρ\rho times a random orthogonal matrix. (An orthogonal matrix, met properly in the next lesson, keeps every length, so every eigenvalue of this one has size exactly ρ\rho.) On screen is a log-scale chart of the gradient's size against the number of steps back kk, relative to its size at the last step TT: the white line at 1 means unchanged, the band above it means the gradient grew, and the band below means it shrank. The lime line is the RNN. The readouts give the factor per step and the size after 10, 50 and 60 steps; a slider sets ρ\rho, and a toggle brings in the tanh slopes.

The tanh slopes are between 0 and 1, so they can only reduce the most that a single step can stretch the gradient (the lesson after next makes this precise with singular values). That makes vanishing the more common failure. The fix in module 8 is architectural: the LSTM adds a second path, the cell state, along which the per-step factor is a diagonal matrix of "forget gate" values. A diagonal matrix's eigenvalues are its diagonal entries, and the network learns to hold them close to 1 when it needs to remember, so the gradient along that path neither vanishes nor explodes.

To finish, explain the whole chain of reasoning in your own words, with two concrete networks.

In your own wordsTwo networks, fifty steps

Two recurrent networks are identical except for the recurrent weight matrix. In the first, ρ(W)=0.7\rho(\mathbf{W}) = 0.7; in the second, ρ(W)=1.3\rho(\mathbf{W}) = 1.3. Explain what happens in each to the gradient signal from an input 50 steps in the past, why, and why neither network can easily learn a dependency that long.

A few sentences first: 0 of 60 characters.

Saved in this browser as you type.

Next: Symmetric matrices and PCA