[Advanced] — the directions a transformation does not turn, and the change of basis that makes a matrix diagonal.

Before you start

What you will be able to do after this lesson:

  1. Find eigenvalues from the characteristic equation, and eigenvectors from the null space of .
  2. Explain what an eigenvector is geometrically, and give a matrix that has no real eigenvalues at all.
  3. Diagonalise a matrix, and use it to compute in a handful of operations rather than multiplications.
  4. Find the steady state of a Markov chain as an eigenvector, and implement power iteration.

Study route: read 1–5, attempt the prediction in section 3, then run the lab. Block 5 is PageRank in miniature.


1. Why this exists

A linear map generally does two things to a vector: stretches it and turns it. The turning is what makes maps hard to reason about, and hard to iterate — apply a matrix ten times and the result is a tangle.

But most maps have special directions where the turning simply does not happen. Along those directions the map is nothing but a stretch by a number. Find them, use them as your coordinate axes, and the matrix becomes diagonal — and a diagonal matrix is as easy to work with as a list of numbers.

That is the whole idea, and its consequences are everywhere:

  • PageRank is the dominant eigenvector of a web-link matrix.
  • Principal component analysis finds the eigenvectors of a covariance matrix — the directions data varies most along.
  • Stability of a physical system, a control loop or an iterative numerical method is decided by whether eigenvalue magnitudes exceed .
  • Quantum mechanics is built on them: observable quantities are eigenvalues of operators.
  • The classification of quadric surfaces in quadric surfaces was, as flagged there, a statement about the signs of eigenvalues.

2. The definition

A non-zero vector is an eigenvector of with eigenvalue when:

In words: applying the matrix has the same effect as multiplying by a single number. The direction survives; only the length changes, by the factor .

What happens along that direction
Stretched
Shrunk
Fixed — unchanged
Collapsed to zero — this direction is in the kernel
Flipped, and scaled by

The requirement matters: holds for every , so allowing it would make the definition vacuous.

Eigenvectors are never unique either — if is one, so is and . What is really determined is a direction, or more precisely the eigenspace: the null space of , which is a subspace.

3. Finding them

Rearrange the definition:

The middle step needs the : you cannot subtract a number from a matrix, so must be written as .

Now the key move. We need a non-zero in the null space of . From vector spaces, a non-trivial null space means the matrix is singular, and from lesson 1 singular means zero determinant:

This is the characteristic equation, and its left-hand side is a polynomial in of degree .

For a matrix it takes a memorable form. Writing :

So for : the eigenvalues sum to the trace and multiply to the determinant. A useful check, and often the fastest route.

Then the eigenvectors: for each , solve by elimination. The matrix is singular by construction, so there will be a free variable — pick a convenient value for it.

Worked example

For : , so , giving .

For : , so , giving .

Check: . ✓ And . ✓

TIP

Predict before section 4. Consider the matrix that rotates the plane by : . Before computing anything — is there any direction a rotation leaves pointing the same way? What does that tell you about its real eigenvalues, and what will the characteristic equation look like? Decide before opening the answers.

4. Diagonalisation

Suppose () has independent eigenvectors. Put them in the columns of and the eigenvalues on the diagonal of . Then:

The first equality is just ” applied to each eigenvector is that eigenvector times its eigenvalue”, written for all columns at once.

Read right to left as a recipe:

  1. — rewrite the input in eigenvector coordinates.
  2. — scale each coordinate by its eigenvalue. This is the whole transformation, and it is just multiplications.
  3. — convert back to ordinary coordinates.

The payoff is powers. Since the middle terms cancel:

and is just each diagonal entry raised to the th power. Computing becomes three matrix multiplications and exponentiations, instead of 99 matrix multiplications — and, more importantly, you can see what happens as grows: the largest dominates everything.

Not every matrix is diagonalisable. A shear has twice but only one independent eigenvector, so no basis of eigenvectors exists. Such matrices are called defective, and the nearest available simplification is the Jordan form.

Symmetric matrices are always well behaved. If , then its eigenvalues are all real, and eigenvectors for different eigenvalues are orthogonal. This is the spectral theorem, and it is why covariance matrices — symmetric by construction — always yield the clean orthogonal axes that PCA uses.

5. Markov chains and power iteration

A Markov chain has a transition matrix whose columns are probabilities summing to . Such a matrix always has as an eigenvalue, and its eigenvector — normalised to sum to — is the steady state the system settles into regardless of where it started.

You do not need the characteristic polynomial to find it. Power iteration works:

  1. Start with any vector that is not orthogonal to the dominant eigenvector.
  2. Repeatedly set , normalising each time.
  3. It converges to the eigenvector of the largest-magnitude eigenvalue.

Why it works: write in the eigenvector basis. Each application multiplies the th component by . After steps the ratio of any other component to the dominant one is . Everything but the dominant direction dies out geometrically, at a rate set by .

This is PageRank. The matrix is the web’s link structure, and the dominant eigenvector is the ranking. Google’s original contribution was not the mathematics — it was noticing that the mathematics applied, and making power iteration work at web scale.

Worked example — runnable

Runnable example: save as eigen.py in any empty directory and run python3 eigen.py. Standard library only; writes no files.

"""Eigenvalues by hand, diagonalisation, fast powers, and power iteration."""
import math
 
EPS = 1e-9
 
 
def matmul(A, B):
    return [[sum(A[i][k] * B[k][j] for k in range(len(B))) for j in range(len(B[0]))]
            for i in range(len(A))]
 
 
def apply(A, v):
    return [sum(A[i][k] * v[k] for k in range(len(v))) for i in range(len(A))]
 
 
def inverse2(A):
    d = A[0][0] * A[1][1] - A[0][1] * A[1][0]
    return [[A[1][1] / d, -A[0][1] / d], [-A[1][0] / d, A[0][0] / d]]
 
 
def eigen2(A):
    """Eigenvalues of a 2x2 from lambda^2 - (trace)lambda + det = 0."""
    tr = A[0][0] + A[1][1]
    de = A[0][0] * A[1][1] - A[0][1] * A[1][0]
    disc = tr * tr - 4 * de
    if disc < -EPS:
        return []                       # no REAL eigenvalues
    s = math.sqrt(max(0.0, disc))
    return sorted({(tr + s) / 2, (tr - s) / 2}, reverse=True)
 
 
def eigenvector2(A, lam):
    """A unit vector in the null space of A - lambda I."""
    a, b = A[0][0] - lam, A[0][1]
    c, d = A[1][0], A[1][1] - lam
    # both rows describe the same line through the origin; use a non-zero one
    v = [-b, a] if (abs(a) > EPS or abs(b) > EPS) else [-d, c]
    # an eigenvector is a DIRECTION, so -v works too; fix the sign for readability
    if v[0] < -EPS or (abs(v[0]) < EPS and v[1] < 0):
        v = [-v[0], -v[1]]
    n = math.hypot(*v)
    return [v[0] / n, v[1] / n]
 
 
def power_iteration(A, x0, steps=60):
    x = x0[:]
    for _ in range(steps):
        x = apply(A, x)
        n = math.sqrt(sum(v * v for v in x))
        x = [v / n for v in x]
    lam = sum(x[i] * apply(A, x)[i] for i in range(len(x)))   # Rayleigh quotient
    return x, lam
 
 
if __name__ == "__main__":
    A = [[4.0, 1.0], [2.0, 3.0]]
 
    print("Block 1 - the worked example, verified")
    lams = eigen2(A)
    print(f"  A = {A}")
    print(f"  trace = {A[0][0] + A[1][1]}, det = {A[0][0]*A[1][1] - A[0][1]*A[1][0]}")
    print("  characteristic equation: lambda^2 - 7 lambda + 10 = 0")
    print(f"  eigenvalues: {lams}")
    assert lams == [5.0, 2.0]
    print(f"  they sum to {sum(lams)} (the trace) and multiply to {lams[0]*lams[1]} (the det)")
    for lam in lams:
        v = eigenvector2(A, lam)
        Av = apply(A, v)
        lv = [lam * c for c in v]
        print(f"    lambda={lam}: v = {[round(c, 6) for c in v]}"
              f"   Av = {[round(c, 6) for c in Av]}   lambda*v = {[round(c, 6) for c in lv]}")
        assert all(abs(p - q) < 1e-9 for p, q in zip(Av, lv))
 
    print()
    print("Block 2 - some matrices have NO real eigenvalues")
    cases = [
        ("rotate 90 degrees", [[0.0, -1.0], [1.0, 0.0]]),
        ("rotate 30 degrees", [[math.cos(math.radians(30)), -math.sin(math.radians(30))],
                               [math.sin(math.radians(30)), math.cos(math.radians(30))]]),
        ("reflect in y=x",    [[0.0, 1.0], [1.0, 0.0]]),
        ("scale by 3",        [[3.0, 0.0], [0.0, 3.0]]),
        ("shear",             [[1.0, 1.0], [0.0, 1.0]]),
        ("projection",        [[1.0, 0.0], [0.0, 0.0]]),
    ]
    for label, M in cases:
        e = eigen2(M)
        print(f"  {label:20} eigenvalues: {[round(x, 6) for x in e] if e else 'none (real)'}")
    assert eigen2([[0.0, -1.0], [1.0, 0.0]]) == []
    print("  a rotation turns EVERY direction, so no real eigenvector can exist")
    print("  the reflection has +1 (the mirror line) and -1 (perpendicular to it)")
    print("  the projection has 1 (the x-axis) and 0 (the y-axis, which is the kernel)")
    assert eigen2([[1.0, 0.0], [0.0, 0.0]]) == [1.0, 0.0]
 
    print()
    print("Block 3 - diagonalisation, and powers for almost free")
    v1 = eigenvector2(A, 5.0)
    v2 = eigenvector2(A, 2.0)
    P = [[v1[0], v2[0]], [v1[1], v2[1]]]
    D = [[5.0, 0.0], [0.0, 2.0]]
    Pinv = inverse2(P)
    rebuilt = matmul(matmul(P, D), Pinv)
    print(f"  P D P^-1 = {[[round(x, 9) for x in r] for r in rebuilt]}")
    print(f"  A        = {A}")
    for i in range(2):
        for j in range(2):
            assert abs(rebuilt[i][j] - A[i][j]) < 1e-9
 
    naive = [[1.0, 0.0], [0.0, 1.0]]
    for _ in range(10):
        naive = matmul(naive, A)
    Dn = [[5.0 ** 10, 0.0], [0.0, 2.0 ** 10]]
    fast = matmul(matmul(P, Dn), Pinv)
    print(f"  A^10 by 10 multiplications: {[[round(x, 3) for x in r] for r in naive]}")
    print(f"  A^10 by P D^10 P^-1:        {[[round(x, 3) for x in r] for r in fast]}")
    for i in range(2):
        for j in range(2):
            assert abs(naive[i][j] - fast[i][j]) < 1e-6
    print(f"  5^10 = {5**10:,} dwarfs 2^10 = {2**10:,}: the largest eigenvalue dominates")
 
    print()
    print("Block 4 - symmetric matrices: real eigenvalues, orthogonal eigenvectors")
    S = [[2.0, 1.0], [1.0, 2.0]]
    se = eigen2(S)
    sv = [eigenvector2(S, l) for l in se]
    print(f"  S = {S}, eigenvalues {se}")
    for l, v in zip(se, sv):
        print(f"    lambda={l}: v = {[round(c, 6) for c in v]}")
    dotp = sv[0][0] * sv[1][0] + sv[0][1] * sv[1][1]
    print(f"  their dot product = {dotp:.9f}  ->  orthogonal, as the spectral theorem promises")
    assert abs(dotp) < 1e-9
 
    print()
    print("Block 5 - a Markov chain: the steady state is an eigenvector")
    # columns are probabilities: sunny -> (0.9 sunny, 0.1 rainy); rainy -> (0.5, 0.5)
    M = [[0.9, 0.5], [0.1, 0.5]]
    print(f"  transition matrix {M}   (columns sum to 1)")
    print(f"  eigenvalues: {[round(x, 6) for x in eigen2(M)]}   - note the 1")
    assert abs(eigen2(M)[0] - 1.0) < 1e-9
 
    print("  starting from 'certainly sunny' and iterating:")
    state = [1.0, 0.0]
    for step in range(1, 41):
        state = apply(M, state)
        if step in (1, 2, 3, 5, 10, 20, 40):
            print(f"    after {step:2} steps: sunny {state[0]:.9f}  rainy {state[1]:.9f}")
    print(f"  exact steady state is (5/6, 1/6) = ({5/6:.9f}, {1/6:.9f})")
    assert abs(state[0] - 5 / 6) < 1e-9 and abs(state[1] - 1 / 6) < 1e-9
 
    print("  and from a completely different start it converges to the same place:")
    other = [0.0, 1.0]
    for _ in range(40):
        other = apply(M, other)
    print(f"    from 'certainly rainy': sunny {other[0]:.9f}  rainy {other[1]:.9f}")
    assert abs(other[0] - 5 / 6) < 1e-9
 
    print()
    print("Block 6 - power iteration finds the dominant eigenvector without any algebra")
    vec, lam = power_iteration(A, [1.0, 0.0])
    print(f"  starting from (1,0): converged to {[round(c, 6) for c in vec]}, lambda = {lam:.9f}")
    assert abs(lam - 5.0) < 1e-6
    expected = eigenvector2(A, 5.0)
    aligned = abs(vec[0] * expected[0] + vec[1] * expected[1])
    print(f"  |alignment with the true eigenvector| = {aligned:.9f}")
    assert abs(aligned - 1.0) < 1e-6
 
    print("  convergence rate is set by |lambda2/lambda1| = 2/5 = 0.4 per step:")
    x = [1.0, 0.0]
    for k in range(1, 13):
        x = apply(A, x)
        n = math.sqrt(sum(v * v for v in x))
        x = [v / n for v in x]
        err = 1 - abs(x[0] * expected[0] + x[1] * expected[1])
        if k in (1, 2, 4, 8, 12):
            print(f"    step {k:2}: 1 - alignment = {err:.3e}")
 
    print()
    print("eigen: passed")

Expected output:

Block 1 - the worked example, verified
  A = [[4.0, 1.0], [2.0, 3.0]]
  trace = 7.0, det = 10.0
  characteristic equation: lambda^2 - 7 lambda + 10 = 0
  eigenvalues: [5.0, 2.0]
  they sum to 7.0 (the trace) and multiply to 10.0 (the det)
    lambda=5.0: v = [0.707107, 0.707107]   Av = [3.535534, 3.535534]   lambda*v = [3.535534, 3.535534]
    lambda=2.0: v = [0.447214, -0.894427]   Av = [0.894427, -1.788854]   lambda*v = [0.894427, -1.788854]

Block 2 - some matrices have NO real eigenvalues
  rotate 90 degrees    eigenvalues: none (real)
  rotate 30 degrees    eigenvalues: none (real)
  reflect in y=x       eigenvalues: [1.0, -1.0]
  scale by 3           eigenvalues: [3.0]
  shear                eigenvalues: [1.0]
  projection           eigenvalues: [1.0, 0.0]
  a rotation turns EVERY direction, so no real eigenvector can exist
  the reflection has +1 (the mirror line) and -1 (perpendicular to it)
  the projection has 1 (the x-axis) and 0 (the y-axis, which is the kernel)

Block 3 - diagonalisation, and powers for almost free
  P D P^-1 = [[4.0, 1.0], [2.0, 3.0]]
  A        = [[4.0, 1.0], [2.0, 3.0]]
  A^10 by 10 multiplications: [[6510758.0, 3254867.0], [6509734.0, 3255891.0]]
  A^10 by P D^10 P^-1:        [[6510758.0, 3254867.0], [6509734.0, 3255891.0]]
  5^10 = 9,765,625 dwarfs 2^10 = 1,024: the largest eigenvalue dominates

Block 4 - symmetric matrices: real eigenvalues, orthogonal eigenvectors
  S = [[2.0, 1.0], [1.0, 2.0]], eigenvalues [3.0, 1.0]
    lambda=3.0: v = [0.707107, 0.707107]
    lambda=1.0: v = [0.707107, -0.707107]
  their dot product = 0.000000000  ->  orthogonal, as the spectral theorem promises

Block 5 - a Markov chain: the steady state is an eigenvector
  transition matrix [[0.9, 0.5], [0.1, 0.5]]   (columns sum to 1)
  eigenvalues: [1.0, 0.4]   - note the 1
  starting from 'certainly sunny' and iterating:
    after  1 steps: sunny 0.900000000  rainy 0.100000000
    after  2 steps: sunny 0.860000000  rainy 0.140000000
    after  3 steps: sunny 0.844000000  rainy 0.156000000
    after  5 steps: sunny 0.835040000  rainy 0.164960000
    after 10 steps: sunny 0.833350810  rainy 0.166649190
    after 20 steps: sunny 0.833333335  rainy 0.166666665
    after 40 steps: sunny 0.833333333  rainy 0.166666667
  exact steady state is (5/6, 1/6) = (0.833333333, 0.166666667)
  and from a completely different start it converges to the same place:
    from 'certainly rainy': sunny 0.833333333  rainy 0.166666667

Block 6 - power iteration finds the dominant eigenvector without any algebra
  starting from (1,0): converged to [0.707107, 0.707107], lambda = 5.000000000
  |alignment with the true eigenvector| = 1.000000000
  convergence rate is set by |lambda2/lambda1| = 2/5 = 0.4 per step:
    step  1: 1 - alignment = 5.132e-02
    step  2: 1 - alignment = 7.722e-03
    step  4: 1 - alignment = 1.866e-04
    step  8: 1 - alignment = 1.208e-07
    step 12: 1 - alignment = 7.917e-11

eigen: passed

Block 5 is the whole idea in one place. Two completely different starting states, forty steps of nothing but matrix–vector multiplication, and both land on — the eigenvector for , to nine decimal places.

Common pitfalls and traps

  • Forgetting the . It is , not . Subtracting a scalar from a matrix is not defined.
  • Accepting . It satisfies the equation for every and is excluded by definition. When solving you want the non-trivial null space vectors.
  • Expecting real eigenvalues. A rotation has none — the characteristic equation has a negative discriminant. Over the complex numbers every matrix has eigenvalues counted with multiplicity, which is one of the strongest arguments for complex numbers existing.
  • Assuming every matrix diagonalises. A repeated eigenvalue may come with too few independent eigenvectors. The shear in block 2 has twice and only one eigendirection.
  • Using the characteristic polynomial numerically. For anything beyond , finding polynomial roots is badly conditioned — small coefficient errors move the roots a lot. Real software uses the QR algorithm, never the characteristic polynomial.
  • Expecting power iteration always to converge. It needs a strictly dominant eigenvalue and a starting vector with a component along it. Two eigenvalues of equal magnitude — as with a rotation — make it oscillate instead.

Check your understanding

  1. Find the eigenvalues of and their eigenvectors, by inspection.
  2. A matrix has trace and determinant . What are its eigenvalues?
  3. What does an eigenvalue of tell you about a matrix?
  4. Why are the eigenvalues of a triangular matrix just its diagonal entries?
  5. A Markov transition matrix always has . Why must that be so?
Answers — open only after an attempt
  1. A diagonal matrix acts on each axis separately: with eigenvector , and with eigenvector . The flips that axis as well as stretching it.
  2. , so : and . Check: they sum to and multiply to . ✓
  3. There is a non-zero vector with , so the null space is non-trivial. Hence is singular — not invertible, determinant zero. In fact is the product of the eigenvalues, so a zero eigenvalue forces a zero determinant.
  4. Because is still triangular, and the determinant of a triangular matrix is the product of its diagonal entries. So , which vanishes exactly at the diagonal entries.
  5. Because each column sums to , so the row sums of are , meaning maps the all-ones vector to itself — an eigenvector with . A matrix and its transpose have the same characteristic polynomial and hence the same eigenvalues, so has too. That guarantees a steady state exists.

And the prediction from section 3: a rotation turns every direction, so no real eigenvector can exist. The characteristic equation is , whose discriminant is — no real roots. The complex roots are , which is the first hint that rotation and complex multiplication are the same operation.

Practice — independent task

Implement pagerank(links, damping=0.85) — power iteration on a real link structure.

  1. Build the transition matrix from an adjacency list: if page has outgoing links, each gets probability in column .
  2. Handle dangling nodes — pages with no outgoing links produce a zero column, which breaks the column-sum property. The standard fix distributes their rank evenly over all pages; implement it and say in a comment why the raw matrix fails without it.
  3. Apply damping: , where is all-ones. Explain what the damping factor represents and why guarantees convergence.
  4. Run power iteration until the change falls below a tolerance you choose. Report the number of iterations.
  5. Verify the result is an eigenvector: check to within 1e-9, and that the entries sum to .

Then investigate:

  1. Build a small graph where one page is linked by many low-ranked pages and another by one high-ranked page. Show which wins, and explain why that is the behaviour Google wanted.
  2. Measure how the iteration count varies with for , and relate it to the convergence rate from section 5.

Edge cases: a single page; two pages linking only to each other (a “rank sink” — what does damping do about it?); a page linking to itself; a disconnected graph.

Done when: your eigenvector check passes, your step-6 example behaves as you predicted before running it, and your step-7 numbers show the trend you expect from the theory rather than one you rationalise afterwards.

Tradeoffs, limits and extensions

Never compute eigenvalues from the characteristic polynomial. Root-finding for polynomials is ill-conditioned: Wilkinson’s classic example is a degree-20 polynomial whose roots move by orders of magnitude under a change of in one coefficient. Production libraries use the QR algorithm, which is iterative and numerically stable, and compute the polynomial — if at all — from the eigenvalues rather than the reverse.

Symmetric is a much easier case. Real eigenvalues, orthogonal eigenvectors, always diagonalisable, and specialised algorithms that are faster and more accurate than the general ones. If your matrix is symmetric, say so to your library. Covariance matrices, adjacency matrices of undirected graphs, and Hessians are all symmetric, which is why PCA and spectral clustering are numerically comfortable.

The SVD generalises this to non-square matrices. Eigenvalues need square, and even then may not give a full basis. The singular value decomposition exists for every matrix, always has orthogonal factors, and is the tool of choice for rank, least squares, compression and pseudo-inverses. Where eigenvalues are the natural object for iteration, singular values are the natural object for approximation.

Before moving on

You are done with this lesson when you can:

  • Find eigenvalues from trace and determinant, and eigenvectors from the null space of .
  • Explain geometrically why a rotation has no real eigenvectors.
  • Diagonalise a matrix and use it to compute a high power cheaply.
  • Find a Markov steady state, by algebra and by power iteration, and explain why power iteration works.

Recap for later lookup: with ; solve ; for , , so eigenvalues sum to the trace and multiply to the determinant; eigenvectors span the null space of ; gives ; symmetric matrices have real eigenvalues and orthogonal eigenvectors; power iteration converges to the dominant eigenvector at rate ; a Markov matrix always has , whose eigenvector is the steady state.

Where next: this is the last lesson in linear algebra. The natural continuations are quadric surfaces, whose classification is a statement about eigenvalue signs, and 06-calculus/04-calculus-3/03-optimization, where the Hessian’s eigenvalues decide whether a stationary point is a maximum, a minimum or a saddle.

↑ Back to Linear Algebra