49. Graph theory: adjacency and Laplacian matrices, spectral graph theory (intro)

§24.0 already used a graph's connectivity informally (Perron-Frobenius's irreducibility condition). This lesson makes that connection explicit: every graph has two natural symmetric matrices attached to it, and their eigenvalues — its spectrum — reveal genuinely non-obvious structural facts, using nothing beyond §21.0's Spectral Theorem.

The adjacency matrix

For a graph with n vertices, the adjacency matrix A has A_{ij}=1 if vertices i,j are connected by an edge, 0 otherwise (and A_{ii}=0, no self-loops). For an undirected graph, A is symmetric — §21.0's Spectral Theorem applies directly, giving real eigenvalues and an orthonormal eigenbasis, with no extra assumptions needed.

A quick structural fact: (A^k)_{ij} counts the number of length-k walks from i to j (each step of matrix multiplication, §16.2's row-times-column rule, sums over every possible intermediate vertex, exactly matching how a walk of length k chooses its intermediate stops). This is §19.1's power formula again, now counting paths instead of computing an abstract quantity.

The graph Laplacian

L=D-A

where D=\operatorname{diag}(\deg(1),\dots,\deg(n)) (the degree matrix, each vertex's number of edges on the diagonal). L is symmetric (D diagonal, A symmetric) and — this is the genuinely useful fact — positive semidefinite:

\vec x^TL\vec x=\sum_{(i,j)\in\text{edges}}(x_i-x_j)^2\ge0

(a sum of squares, one term per edge — not derived here in full, but directly checkable by expanding \vec x^TD\vec x-\vec x^TA\vec x and regrouping). By §21.2's PSD eigenvalue test, every eigenvalue of L is \ge0.

Reading connectivity off the spectrum

L\vec1=\vec0 always (D\vec1 gives each vertex's degree, and A\vec1 also gives each vertex's degree — the number of neighbors — so they cancel exactly): 0 is always an eigenvalue of L, with \vec1 (or any constant vector) as eigenvector.

The multiplicity of eigenvalue 0 equals the number of connected components. For a single connected graph, 0 is a simple eigenvalue (multiplicity 1) — the second-smallest eigenvalue, \lambda_2>0, is called the algebraic connectivity (or Fiedler value), and it measures how well-connected the graph is: small \lambda_2 means the graph is "almost disconnected" (a near-bottleneck splitting it into two loosely joined halves), large \lambda_2 means it's robustly connected. This is the theoretical basis of spectral clustering: the sign pattern of the eigenvector for \lambda_2 (the Fiedler vector) tends to split a graph's vertices into exactly the two natural clusters a bottleneck would separate.

Doing it in Python

import numpy as np

# A graph: 0-1, 1-2, 2-3, 3-0, 1-3 (a 4-cycle with one diagonal)
edges = [(0,1), (1,2), (2,3), (3,0), (1,3)]
n = 4
A = np.zeros((n, n))
for i, j in edges:
    A[i, j] = A[j, i] = 1

degrees = A.sum(axis=1)
D = np.diag(degrees)
L = D - A

print("degrees:", degrees.tolist())
print("L =")
for row in L.tolist():
    print(row)

eigvals = np.linalg.eigvalsh(L)
print("\nLaplacian eigenvalues:", [round(v, 4) or 0.0 for v in eigvals.tolist()])
print("smallest eigenvalue is 0 (connected):", np.isclose(eigvals[0], 0))

degrees: [2.0, 3.0, 2.0, 3.0]
L =
[2.0, -1.0, 0.0, -1.0]
[-1.0, 3.0, -1.0, -1.0]
[0.0, -1.0, 2.0, -1.0]
[-1.0, -1.0, -1.0, 3.0]

Laplacian eigenvalues: [0.0, 2.0, 4.0, 4.0]
smallest eigenvalue is 0 (connected): True

Confirming a disconnected graph has a repeated zero eigenvalue:

import numpy as np

# Two disconnected triangles: {0,1,2} and {3,4,5}
edges = [(0,1), (1,2), (2,0), (3,4), (4,5), (5,3)]
n = 6
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

eigvals = np.linalg.eigvalsh(L)
zero_count = int(np.sum(np.isclose(eigvals, 0)))
print("eigenvalues:", [round(v, 4) or 0.0 for v in eigvals.tolist()])
print("number of zero eigenvalues:", zero_count, " (matches 2 connected components)")

eigenvalues: [0.0, 0.0, 3.0, 3.0, 3.0, 3.0]
number of zero eigenvalues: 2  (matches 2 connected components)

Worked example

Find the Laplacian eigenvalues of a "path" graph on 3 vertices: edges 0–1, 1–2.

Degrees: \deg(0)=1,\deg(1)=2,\deg(2)=1.

L=\begin{pmatrix}1&-1&0\\-1&2&-1\\0&-1&1\end{pmatrix}

\operatorname{tr}L=4. \det L=0 (guaranteed — \vec1 is always in the null space). Characteristic polynomial (expanding along row 1): \lambda(\lambda-1)(\lambda-3)=0\Rightarrow\lambda=0,1,3 (verified by 0+1+3=4=\operatorname{tr}L ✓).

\boxed{\lambda=0,1,3}

Sanity check. Only \lambda=0 appears once — matching "connected graph \Rightarrow simple zero eigenvalue" — and this graph genuinely is connected (a straight path visits every vertex). \lambda_2=1 is the algebraic connectivity: a 3-vertex path is fairly well-connected for its size, and 1 is a moderate value confirming that, neither near 0 (which would signal a near-split) nor as large as a densely connected graph's would be.

Your turn

1. A graph has 5 connected components. What is the multiplicity of eigenvalue 0 in its Laplacian?

2. For the complete graph K_n (every vertex connected to every other), each vertex has degree n-1. What is \operatorname{tr}(L)?

3. True or false: the Laplacian's largest eigenvalue can exceed the number of vertices n.

Solutions

1. Multiplicity 5 — directly from "multiplicity of eigenvalue 0 equals the number of connected components," stated above.

2. \operatorname{tr}(L)=\sum\deg(i)=n(n-1) (every one of the n vertices contributes degree n-1) — readable directly from the degree matrix's diagonal, without needing eigenvalues at all (§19.3's similarity-invariant trace, here computed the easy way rather than by summing eigenvalues).

3. False, for a simple graph (no repeated edges). It's a theorem (not proved here) that every Laplacian eigenvalue satisfies \lambda\le n, with equality only for specific highly-connected structures — the eigenvalues of a graph on n vertices are always bounded by the vertex count itself, mirroring how §22.2's condition number bounds relate a matrix's size to its extreme singular values.

Check yourself in code

For a triangle graph (vertices 0,1,2, all pairwise connected), build the Laplacian and find its eigenvalues.

Print exactly this:

L =
[2.0, -1.0, -1.0]
[-1.0, 2.0, -1.0]
[-1.0, -1.0, 2.0]
eigenvalues: [0.0, 3.0, 3.0]

import numpy as np

edges = [(0, 1), (1, 2), (0, 2)]
n = 3
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

print("L =")
for row in L.tolist():
    print(row)
# print the Laplacian's eigenvalues, rounded to 4 decimal places

import numpy as np

edges = [(0, 1), (1, 2), (0, 2)]
n = 3
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

print("L =")
for row in L.tolist():
    print(row)

eigvals = np.linalg.eigvalsh(L)
print("eigenvalues:", [round(v, 4) or 0.0 for v in eigvals.tolist()])

A graph's Laplacian L=D-A is always symmetric PSD, always has 0 as an eigenvalue (eigenvector \vec1), and the multiplicity of that zero eigenvalue counts connected components exactly — with the second-smallest eigenvalue measuring how robustly connected a single component is. All of it follows from §21.0's Spectral Theorem applied to one specifically constructed symmetric matrix.

Next: an application already previewed by §20.5 itself — linear regression, restated explicitly as the least-squares problem it always was.