11. Linear Algebra II — Eigenvalues, Eigenvectors, Determinants

Level: Intermediate You'll use this for: PageRank, PCA, graph/network centrality, and stability analysis.

A = np.array([[2, 0], [0, 3]])
eigenvalues, eigenvectors = np.linalg.eig(A)
print(eigenvalues)   # [2. 3.]

Start from the definition: A·v = λ·v  =>  (A - λI)·v = 0

For a non-zero v to solve this, (A - λI) must be non-invertible, i.e.
det(A - λI) = 0.

A - λI = [2-λ   1  ]
         [1     2-λ]

det(A - λI) = (2-λ)(2-λ) - (1)(1)
            = (2-λ)² - 1
            = 4 - 4λ + λ² - 1
            = λ² - 4λ + 3

Set it to 0 and factor:  λ² - 4λ + 3 = (λ-1)(λ-3) = 0
  ->  λ = 1  or  λ = 3

Determinant

A single number summarizing a matrix's transformation: how much it scales area/volume, and whether it flips orientation. det(A) = 0 means the matrix "collapses" space into a lower dimension — it's not invertible (no unique solution exists for Ax = b).

np.linalg.det(np.array([[1, 2], [3, 4]]))   # -2.0
np.linalg.det(np.array([[1, 2], [2, 4]]))   # 0.0 -> singular, not invertible

# Toy 3-page web: A links to B and C, B links to C, C links to A and B
M = np.array([[0,   0,   0.5],
              [0.5, 0,   0.5],
              [0.5, 1,   0  ]])
eigvals, eigvecs = np.linalg.eig(M)
dominant = eigvecs[:, np.argmax(eigvals)]
rank = np.abs(dominant) / np.sum(np.abs(dominant))
print(rank)   # relative importance of pages A, B, C

The eigen-equation, symbol by symbol

A · v = λ · v          (v ≠ 0)

Finding the eigenvectors, by hand

We found λ = 1 and λ = 3 for A = [[2,1],[1,2]] above. To get each eigenvector, plug λ back into (A - λI)·v = 0 and solve:

λ = 3:  A - 3I = [-1  1]   ->  -v₁ + v₂ = 0  ->  v₁ = v₂   ->  v = (1, 1)
                 [ 1 -1]

λ = 1:  A - 1I = [ 1  1]   ->   v₁ + v₂ = 0  ->  v₁ = -v₂  ->  v = (1, -1)
                 [ 1  1]

Check: A·(1,1) = (2+1, 1+2) = (3,3) = 3·(1,1). ✓ Geometrically, A stretches the diagonal (1,1) by 3× and leaves the anti-diagonal (1,-1) alone. Every other vector is a mix of those two, so it gets partly stretched and partly left alone, which turns it.

Two theorems give you free sanity checks:

trace(A) = sum of eigenvalues        2 + 2 = 4 = 1 + 3   ✓
det(A)   = product of eigenvalues    2·2 - 1·1 = 3 = 1·3 ✓

Diagonalization: why eigenvalues predict the future

If A has n independent eigenvectors, stack them as the columns of P and the eigenvalues on the diagonal of D:

A = P · D · P⁻¹          and therefore          Aᵏ = P · Dᵏ · P⁻¹

Applying A a thousand times is hard. Raising each eigenvalue to the thousandth power is easy. For our A:

A¹⁰ = P · [1¹⁰   0  ] · P⁻¹ = [ (3¹⁰+1)/2   (3¹⁰-1)/2 ] = [29525  29524]
          [0    3¹⁰ ]         [ (3¹⁰-1)/2   (3¹⁰+1)/2 ]   [29524  29525]

The long-run behaviour of any repeated linear process is governed by its largest eigenvalue. If |λ_max| > 1 it blows up, if < 1 it dies out, and if = 1 it settles into a steady state. That one fact explains three very different things:

• AI, exploding/vanishing gradients in RNNs: backprop through T time steps multiplies by the recurrent weight matrix T times, roughly Wᵀ. If |λ_max(W)| = 1.1 and T = 100, gradients scale by 1.1¹⁰⁰ ≈ 13,780. If it's 0.9, they scale by 0.9¹⁰⁰ ≈ 0.00003. LSTMs, gradient clipping and orthogonal initialization (all eigenvalues exactly magnitude 1) are each a fix for this.
• Network, PageRank and Markov chains: steady state = the eigenvector for λ = 1 (below).
• Control, feedback-loop stability: an autoscaler or congestion controller is stable only if its update matrix has every eigenvalue inside the unit circle (Ch. 29).

The spectral theorem: symmetric matrices are the friendly ones

Theorem. If A is real and symmetric (A = Aᵀ), then all its eigenvalues are real, and it has a full set of orthogonal eigenvectors, so A = Q·D·Qᵀ with Qᵀ = Q⁻¹.

This matters because the most important matrices in practice are symmetric: covariance matrices (PCA, Ch. 20), Hessians (Ch. 13, 21), graph Laplacians (below), and kernel matrices. For all of them the eigenvalues are real numbers you can sort and interpret. That's why the PCA code in Ch. 20 uses np.linalg.eigh, the solver specialized for symmetric matrices.

Power iteration, and PageRank properly

You rarely need all eigenvalues, just the dominant one. Power iteration finds it by repeatedly multiplying and re-normalizing, because the largest-eigenvalue component outgrows the rest (that's the diagonalization argument above). Google's real PageRank adds a damping factor:

PR = (1 - d)/N · 1  +  d · M · PR

Toy web from above, d = 0.85, start uniform at [1/3, 1/3, 1/3]:

iter 1:  [0.192, 0.333, 0.475]
iter 2:  [0.252, 0.333, 0.415]
iter 3:  [0.226, 0.333, 0.440]
...
steady:  [0.234, 0.333, 0.433]     <- C ranks highest: both A and B link to it

The teleport term does two jobs. It guarantees a unique answer even when the web has dead ends and closed loops (that's the Perron–Frobenius theorem: a positive stochastic matrix has a unique dominant eigenvector with λ = 1). It also makes convergence fast, because the error shrinks by a factor of about d = 0.85 per iteration, so 50 iterations reach about 0.85⁵⁰ ≈ 0.0003.

Markov chains: bursty packet loss, modelled

A Markov chain is a system that hops between states with fixed probabilities. The transition matrix P[i][j] is the probability of moving from state i to j, and each row sums to 1. In the long run the fraction of time spent in each state is the stationary distribution π:

π · P = π        (π is a left eigenvector of P with eigenvalue 1)
Σᵢ πᵢ = 1

Networking in the wild: the Gilbert–Elliott channel. Real links don't drop packets independently (Ch. 8's coin-flip model). They drop them in bursts, during Wi-Fi interference or a congested queue. The classic model has two states:

                      to Good   to Bad
P =  from Good   [    0.99      0.01  ]        Good: 0% loss
     from Bad    [    0.30      0.70  ]        Bad:  50% loss

Solve π·P = π for two states. Flow into Bad has to equal flow out of Bad, so π_G · 0.01 = π_B · 0.30. Combined with π_G + π_B = 1:

π_B = 0.01 / (0.01 + 0.30) = 0.032     (the link is "Bad" 3.2% of the time)
average loss = 0.032 · 50% ≈ 1.6%
mean burst length = 1 / 0.30 ≈ 3.3 packets in a row in the Bad state

The long-run loss rate is the same 1.6% as an independent-loss model would give, but the losses arrive in clumps. That's why forward-error-correction schemes (used in video calls and QUIC experiments) interleave packets: it spreads one burst across many FEC blocks so each block loses only one packet. Netem, Linux's network emulator, ships this exact model (tc qdisc ... loss gemodel).

The same π·P = π equation is the language-model view of text too. An n-gram model is a Markov chain over words, and the "random surfer" of PageRank is a Markov chain over web pages.

The graph Laplacian: measuring how hard a network is to cut

For a graph with adjacency matrix A and degree matrix D (node degrees on the diagonal), the Laplacian is:

L = D - A

Its eigenvalues are all ≥ 0, and the smallest is always 0. The second-smallest eigenvalue λ₂ (the algebraic connectivity or Fiedler value) measures how well-connected the graph is. λ₂ = 0 exactly when the network is already split in two, and a bigger λ₂ means it takes more link cuts to partition it.

Four routers, three topologies:

def fiedler(edges, n=4):
    A = np.zeros((n, n))
    for i, j in edges:
        A[i, j] = A[j, i] = 1
    L = np.diag(A.sum(axis=1)) - A
    return np.sort(np.linalg.eigvalsh(L))[1]

print(fiedler([(0,1), (1,2), (2,3)]))          # 0.586  line
print(fiedler([(0,1), (1,2), (2,3), (3,0)]))   # 2.0    ring

Adding one link (line → ring) more than triples λ₂. That's a quantitative answer to "which single link should we add for the most resilience?": try each candidate and pick the largest jump in λ₂. The eigenvector for λ₂ (the Fiedler vector) has positive entries on one side of the network's weakest cut and negative on the other. Spectral clustering in ML and community detection in social graphs both partition data with that sign pattern.

Real-life engineering ties

• SWE: recommendation systems, search ranking.
• AI: Principal Component Analysis (PCA, Ch. 20) is literally "find the eigenvectors of the covariance matrix"; eigenvalues of a Hessian determine whether a training loss landscape point is a minimum, maximum, or saddle point.
• Network: identifying the most critical router/node in a topology (eigenvector/betweenness centrality) for redundancy planning; spectral graph analysis for detecting network partitions.
• Security: anomaly detection via PCA (projecting traffic onto the top eigenvectors and flagging what doesn't fit); social-graph analysis for identifying influential/central accounts in fraud rings.

More real-life examples:

• Academic citation-ranking metrics (Eigenfactor, and the ideas behind Google Scholar) rank journals/papers using the same eigenvector- centrality math as PageRank, applied to a citation graph.
• Social network platforms use graph centrality measures (eigenvector, PageRank-style, or betweenness centrality) to identify influential accounts for recommendation, ranking, and bot-network detection.
• Network engineers use centrality analysis on a topology graph to find single points of failure — the router/link whose removal would fragment the network the most — directly informing redundancy investment.
• Structural engineers compute the eigenvalues of a system's stiffness matrix to find its resonant frequencies — the 1940 Tacoma Narrows Bridge collapse is a famous real-world illustration of why eigenvalue analysis of physical systems matters.

Common mistake

Assuming every matrix has "nice" real eigenvalues — many don't (some are complex), and non-square matrices don't have eigenvalues at all (you need Singular Value Decomposition instead, Ch. 20).