Eigenvectors and Eigenvalues

Discover: a definition that chases its own tail

In 1998 two Stanford PhD students, Sergey Brin and Lawrence Page, described a prototype search engine called Google. One of its key ideas was a way to score every page on the web by importance, and it fits on one line:

Read it aloud: “the PageRank of page $A$ is one minus $d$, plus $d$ times the sum, over the pages $T_1$ to $T_n$ that link to $A$, of each one's PageRank divided by its number of outgoing links.” Here $C(T)$ counts the links going out of page $T$, and $d$ is a “damping factor” the paper usually sets to $0.85$. Each page splits its own importance equally among the pages it links to, and a page is important if important pages link to it.

Now look again. To compute $PR(A)$ you need $PR(T_1)$. But $PR(T_1)$ is defined by the same formula, using the pages that link to it, and one of those might well be $A$. The definition chases its own tail. How can a number be defined in terms of itself, and how would you ever compute it?

The answer is one of the most useful ideas in linear algebra. Collect all the PageRanks into a single vector: the formula says that a certain matrix leaves that vector exactly where it is. A vector that a matrix doesn't turn is called an eigenvector, and by the end of this chamber you'll compute PageRank yourself.

Learn: the directions a matrix only stretches

Chamber 4 taught you to see a matrix as a machine that moves space. Feed it a vector and, almost always, the output points somewhere new. But for most matrices a few special directions are merely stretched: the output lies on the same line through the origin as the input.

Read it as “A v equals lambda v”. A non-zero vector $\mathbf{v}$ with this property is an eigenvector of $A$, and the number $\lambda$ (lambda) is its eigenvalue: the factor by which $A$ stretches that direction. The zero vector is excluded because $A\mathbf{0} = \lambda\mathbf{0}$ for every $\lambda$, which tells you nothing.

The size and sign of $\lambda$ tell the story. With $\lambda = 3$ the eigenvector triples in length. With $\lambda = \tfrac{1}{2}$ it halves. With $\lambda = -1$ it flips to point the other way, still on its line. With $\lambda = 0$ it is flattened to $\mathbf{0}$, so it lies in the null space.

You have met eigenvectors already without the name:

• A diagonal matrix such as $\begin{bmatrix} 2 & 0 \\ 0 & 0.5 \end{bmatrix}$ stretches the $x$-axis by 2 and squashes the $y$-axis by half. Its eigenvectors are $\mathbf{e}_1$ (with $\lambda = 2$) and $\mathbf{e}_2$ (with $\lambda = 0.5$).
• A projection $P$ onto a line (Chamber 7) leaves vectors on the line alone ($\lambda = 1$) and sends the perpendicular direction to zero ($\lambda = 0$).
• A reflection across a line keeps the line ($\lambda = 1$) and flips the perpendicular direction ($\lambda = -1$).
• A rotation by $90°$ turns every direction. It has no real eigenvectors at all.

One more fact before you go hunting. If $\mathbf{v}$ is an eigenvector, so is any non-zero multiple $c\mathbf{v}$, because $A(c\mathbf{v}) = cA\mathbf{v} = \lambda(c\mathbf{v})$. Eigenvectors come in whole lines through the origin, so we really look for eigen-directions.

Now find some by eye. Turn the unit vector $\mathbf{x}$ around the circle and watch where $A$ sends it.

A few things to notice. The stretch matrix's eigenvectors are the axes, as expected. The symmetric matrix $\begin{bmatrix} 2 & 1 \\ 1 & 2 \end{bmatrix}$ has eigen-directions at $45°$ and $135°$, which meet at a right angle. The triangular matrix's two directions don't: they meet at about $72°$. And one of its eigenvalues is negative, so there $A\mathbf{x}$ points straight back the way $\mathbf{x}$ came. With Show A(circle) on, you can see each eigen-direction pointing to where the ellipse crosses it, at distance $|\lambda|$ from the origin.

Learn: finding eigenvalues with the determinant

Hunting by eye works in two dimensions. For anything bigger we need algebra, and the derivation takes four steps, each resting on an earlier chamber.

1. 1

   Move everything to one side

   $A\mathbf{v} = \lambda\mathbf{v}$ is the same as $A\mathbf{v} - \lambda I\mathbf{v} = \mathbf{0}$, that is, $(A - \lambda I)\mathbf{v} = \mathbf{0}$. We slip in the identity $I$ because we can't subtract a number from a matrix, but $\lambda I$ is a matrix.

2. 2

   Read it as a null space

   We need a non-zero $\mathbf{v}$ with $(A - \lambda I)\mathbf{v} = \mathbf{0}$: the matrix $A - \lambda I$ must have a non-trivial null space (Chamber 6).

3. 3

   Translate to singular

   A square matrix has a non-trivial null space exactly when it is singular, not invertible (Chamber 5).

4. 4

   Translate to a determinant

   A square matrix is singular exactly when its determinant is zero (Chamber 5). So $\lambda$ is an eigenvalue of $A$ if and only if $\det(A - \lambda I) = 0$.

This is the characteristic equation, and $p(\lambda) = \det(A - \lambda I)$ (read “p of lambda”) is the characteristic polynomial. For a $2 \times 2$ matrix it is worth expanding once and for all:

The coefficient $a + d$ is the trace $\operatorname{tr}(A)$ (read “trace of A”), the sum of the diagonal entries, and $ad - bc$ is the determinant. So $p(\lambda) = \lambda^2 - \operatorname{tr}(A)\,\lambda + \det A$. If the roots are $\lambda_1$ and $\lambda_2$, then $p(\lambda) = (\lambda - \lambda_1)(\lambda - \lambda_2) = \lambda^2 - (\lambda_1 + \lambda_2)\lambda + \lambda_1\lambda_2$, and matching coefficients gives two free checks:

A worked example with the lab's symmetric matrix $S = \begin{bmatrix} 2 & 1 \\ 1 & 2 \end{bmatrix}$. The trace is 4 and the determinant is 3, so $p(\lambda) = \lambda^2 - 4\lambda + 3 = (\lambda - 3)(\lambda - 1)$ and the eigenvalues are 3 and 1. For each one, find the null space of $S - \lambda I$:

Those are the $45°$ and $135°$ lines you found in the lab. For the triangular matrix $T = \begin{bmatrix} 2 & 1 \\ 0 & -1 \end{bmatrix}$ it's even quicker. $T - \lambda I$ is triangular, and a triangular determinant is the product of its diagonal (Chamber 5), so $p(\lambda) = (2 - \lambda)(-1 - \lambda)$ and the eigenvalues are simply the diagonal entries, 2 and $-1$. For $\lambda = -1$, $T + I = \begin{bmatrix} 3 & 1 \\ 0 & 0 \end{bmatrix}$ gives $\mathbf{v}_2 = (1, -3)$.

And the rotation $R = \begin{bmatrix} 0 & -1 \\ 1 & 0 \end{bmatrix}$? Its trace is 0 and its determinant is 1, so $p(\lambda) = \lambda^2 + 1$, which has no real roots. The algebra agrees with the picture: a quarter turn leaves no direction on its own line.

Learn: diagonalisation and matrix powers

Put the eigen-equations for all $n$ eigenvectors side by side. Stack the eigenvectors as the columns of a matrix $V$ and the eigenvalues on the diagonal of $\Lambda$ (capital lambda). Column $i$ of $AV$ is $A\mathbf{v}_i = \lambda_i\mathbf{v}_i$, which is also column $i$ of $V\Lambda$. So $AV = V\Lambda$, and when $V$ is invertible:

Read it right to left, as a journey. $V^{-1}$ translates a vector into eigen-coordinates. $\Lambda$ stretches each coordinate by its own eigenvalue, independently. $V$ translates back. In the right coordinates, every diagonalisable matrix is just a stretch.

The payoff is powers. Multiply two copies and the middle cancels:

Powering a diagonal matrix just powers its diagonal entries. Applying $A$ a hundred times costs no more than raising $n$ numbers to the hundredth power.

When is $V$ invertible? When the eigenvectors are independent, and there's a clean guarantee. Here is the proof for two eigenvectors; the same idea extends to any number.

Claim. If $A\mathbf{v}_1 = \lambda_1\mathbf{v}_1$ and $A\mathbf{v}_2 = \lambda_2\mathbf{v}_2$, with $\mathbf{v}_1, \mathbf{v}_2 \ne \mathbf{0}$ and $\lambda_1 \ne \lambda_2$, then $\mathbf{v}_1$ and $\mathbf{v}_2$ are linearly independent.

Proof. Suppose $c_1\mathbf{v}_1 + c_2\mathbf{v}_2 = \mathbf{0}$. We must show $c_1 = c_2 = 0$. Apply $A$ to both sides. By linearity and the eigen-equations,

Multiply the original equation by $\lambda_2$ instead, giving $c_1\lambda_2\mathbf{v}_1 + c_2\lambda_2\mathbf{v}_2 = \mathbf{0}$, and subtract it from the line above. The $\mathbf{v}_2$ terms cancel:

Here $\lambda_1 - \lambda_2 \ne 0$ and $\mathbf{v}_1 \ne \mathbf{0}$, so $c_1 = 0$. Then the original equation reads $c_2\mathbf{v}_2 = \mathbf{0}$ with $\mathbf{v}_2 \ne \mathbf{0}$, so $c_2 = 0$ too. $\blacksquare$

The trick is worth remembering: apply $A$ to create a second equation, then combine the two to eliminate one eigenvector. So an $n \times n$ matrix with $n$ distinct eigenvalues is always diagonalisable. With repeated eigenvalues it may not be: the shear $\begin{bmatrix} 1 & 1 \\ 0 & 1 \end{bmatrix}$ has only one eigen-direction, and no $V$ exists.

Fibonacci from eigenvalues

Here is diagonalisation doing something that looks like magic. The Fibonacci numbers $1, 1, 2, 3, 5, 8, 13, \ldots$ obey $F_{n+1} = F_n + F_{n-1}$. Write one step as a matrix acting on a pair:

(starting from $F_1 = 1$, $F_0 = 0$). The trace is 1 and the determinant is $-1$, so $p(\lambda) = \lambda^2 - \lambda - 1$, with roots

That's $\varphi$ (phi), the golden ratio, and its partner $\psi$ (psi). Since $\lambda^2 = \lambda + 1$ for both roots, you can check that $(\lambda, 1)$ is an eigenvector: $F(\lambda, 1) = (\lambda + 1, \lambda) = (\lambda^2, \lambda) = \lambda(\lambda, 1)$. Now write the starting vector in eigen-coordinates. The difference of the two eigenvectors is $(\varphi - \psi, 0) = (\sqrt{5}, 0)$, so

Applying $F^n$ multiplies each eigenvector by its eigenvalue $n$ times. Reading off the second entry:

This is Binet's formula: irrational numbers on the right, whole numbers on the left, for every $n$. Because $|\psi| < 1$, the $\psi^n$ term dies away, so $F_n$ is simply the nearest integer to $\varphi^n/\sqrt{5}$, and each Fibonacci number is about $1.618$ times the one before. The golden ratio is the growth rate, because it is the dominant eigenvalue.

Learn: power iteration

The characteristic polynomial is fine for a $2 \times 2$ matrix. For the web, with billions of pages, it is hopeless: nobody can expand a determinant that size. But multiplying a vector by a matrix, even a huge sparse one, is cheap. Power iteration finds the dominant eigenvector with nothing else:

Multiply, rescale so the numbers don't blow up, repeat. Why does it work? Suppose $A$ has eigenvectors $\mathbf{v}_1, \mathbf{v}_2$ with $|\lambda_1| > |\lambda_2|$, and the start is $\mathbf{x}_0 = c_1\mathbf{v}_1 + c_2\mathbf{v}_2$ with $c_1 \ne 0$. Each multiplication by $A$ multiplies each eigen-component by its eigenvalue, so

The ratio $|\lambda_2/\lambda_1|$ is less than 1, so the second term fades geometrically and the direction swings onto $\mathbf{v}_1$. The rescaling only changes the length, never the direction. The speed is set by the ratio: the error shrinks by a factor of about $|\lambda_2/\lambda_1|$ per step.

By hand, with $S = \begin{bmatrix} 2 & 1 \\ 1 & 2 \end{bmatrix}$ and $\mathbf{x}_0 = (1, 0)$, skipping the rescaling:

The vectors line up with $(1, 1)$ fast, because $|\lambda_2/\lambda_1| = \tfrac{1}{3}$. To read off the eigenvalue, use the Rayleigh quotient $\frac{\mathbf{x}^\top A\mathbf{x}}{\mathbf{x}^\top\mathbf{x}}$, which equals $\lambda$ exactly when $\mathbf{x}$ is an eigenvector. At $(5, 4)$ it is already $\tfrac{122}{41} \approx 2.976$, and at $(41, 40)$ it is $2.9997$, closing in on $\lambda_1 = 3$.

import numpy as np

def power_iteration(A, x, steps=50):
    for _ in range(steps):
        x = A @ x
        x = x / np.linalg.norm(x)          # rescale: direction is all that matters
    return x, (x @ A @ x) / (x @ x)        # eigenvector and Rayleigh quotient

S = np.array([[2.0, 1.0], [1.0, 2.0]])
x, lam = power_iteration(S, np.array([1.0, 0.0]))
print(x.round(4), round(lam, 4))           # [0.7071 0.7071] 3.0

The Fibonacci recurrence is power iteration too. Starting from $(1, 0)$ and applying $F$ over and over, the direction settles on $(\varphi, 1)$, which is why $F_{n+1}/F_n \to \varphi$.

Two caveats. The start must have some component along $\mathbf{v}_1$ ($c_1 \ne 0$); a random start almost surely does. And there must be a single eigenvalue of largest size: if $\lambda_2 = -\lambda_1$, the vector flips back and forth for ever.

Learn: Markov chains and PageRank

A Markov chain is a system that hops between states at random, where the next hop depends only on where you are now. Its transition matrix $P$ has $P_{ij}$ equal to the probability of moving to state $i$ from state $j$, so each column is a probability distribution and sums to 1. If $\boldsymbol{\pi}_t$ is the vector of probabilities of being in each state at time $t$, one step is a matrix multiplication: $\boldsymbol{\pi}_{t+1} = P\boldsymbol{\pi}_t$. Running the chain is power iteration.

A worked example. Tomorrow is sunny with probability $0.9$ after a sunny day, and with probability $0.5$ after a rainy one:

Start on a sunny day, $\boldsymbol{\pi}_0 = (1, 0)$. Then $\boldsymbol{\pi}_1 = (0.9, 0.1)$, $\boldsymbol{\pi}_2 = (0.86, 0.14)$, $\boldsymbol{\pi}_3 = (0.844, 0.156)$, and the numbers settle down. The limit is a stationary distribution: a $\boldsymbol{\pi}$ with $P\boldsymbol{\pi} = \boldsymbol{\pi}$ (read “P pi equals pi”). That is an eigenvector with eigenvalue 1. Solving $(P - I)\boldsymbol{\pi} = \mathbf{0}$: the first row says $-0.1\,s + 0.5\,r = 0$, so $s = 5r$, and with $s + r = 1$ we get $\boldsymbol{\pi} = (\tfrac{5}{6}, \tfrac{1}{6})$. Five days in six are sunny in the long run. The other eigenvalue is $\operatorname{tr}(P) - 1 = 0.4$, so the chain forgets its starting day like $0.4^t$.

Why must 1 always be an eigenvalue? Because each column of $P$ sums to 1, the row vector of ones passes through unchanged: $\mathbf{1}^\top P = \mathbf{1}^\top$. Transposing, $P^\top\mathbf{1} = \mathbf{1}$, so 1 is an eigenvalue of $P^\top$. And $A$ and $A^\top$ always share eigenvalues, because $\det(A^\top - \lambda I) = \det\big((A - \lambda I)^\top\big) = \det(A - \lambda I)$.

PageRank is a Markov chain

Back to the formula you couldn't compute. Brin and Page describe a “random surfer” who clicks links at random and, every so often, gets bored and jumps to a random page. As the formula is written, at each step the surfer follows a random outgoing link with probability $d$ and jumps to a random page with probability $1 - d$. A page's PageRank measures how often the surfer is there in the long run: the stationary distribution of this chain.

Take a web of four pages: $A$ links to $B$ and $C$, $B$ links to $C$, $C$ links to $A$, and $D$ links to $C$. Build the link matrix $M$, with $M_{ij} = 1/C(j)$ when page $j$ links to page $i$:

Column $j$ says where page $j$'s rank goes. All four of the paper's equations at once read $\mathbf{r} = (1 - d)\mathbf{1} + dM\mathbf{r}$, and the Decoder below shows how that becomes an eigenvector equation $G\mathbf{r} = \mathbf{r}$. To compute it, just iterate: start with every rank equal to 1 and apply the formula again and again. It's power iteration, and the error shrinks by at least a factor $d$ each round.

import numpy as np

d = 0.85
M = np.array([[0, 0, 1, 0],
              [0.5, 0, 0, 0],
              [0.5, 1, 0, 1],
              [0, 0, 0, 0]])
r = np.ones(4)
for _ in range(100):
    r = (1 - d) + d * M @ r       # the paper's formula, for every page at once
print(r.round(3), r.sum().round(6))   # [1.49  0.783 1.577 0.15 ] 4.0

Page $C$ wins: three pages link to it. But $A$ comes a close second with a single incoming link, because that link comes from the important page $C$ and is $C$'s only outgoing link. Page $D$, which nobody links to, gets only the baseline $1 - d = 0.15$. This is exactly the intuition the paper gives: a page ranks highly if many pages point to it, or if a few highly ranked pages do.

Read beyond the course

Papers and lectures

Brin and Page's paper is long and mostly about engineering a search engine: crawling, indexing, storage. You only need a page and a half of it now. Read the abstract, then jump to Section 2.1, “PageRank: Bringing Order to the Web”, and read Sections 2.1.1 and 2.1.2 slowly. That is the formula, the sentence connecting it to “the principal eigenvector of the normalized link matrix of the web”, and the random-surfer story. Skip Sections 3 to 5 unless you're curious how a search engine was built in 1998. Appendix A is short and worth a look: the founders argue that search engines funded by advertising will be “inherently biased towards the advertisers”.

Watch

The first video animates exactly what you did in the lab: most vectors are knocked off their span, a few stay on it. Watch for the moment the eigenbasis turns a matrix into a diagonal one. The second derives the mean-and-product trick for $2 \times 2$ eigenvalues; try each of its examples before it reveals the answer.

Your turn

Match symbols to words and to code, prove two facts, then compute: Fibonacci's growth, a frog's favourite lily pad, and the PageRank of a small web, using the paper's formula exactly as printed.

Proofs

Code it up