Spectral Graph Theory: Eigenstructure of Network Adjacency and Laplacian Matrices

Take the Delhi Metro map, or the layout of servers that keep an online railway-booking system talking to itself, or a WhatsApp friend circle. Strip away the geography and the icons, and each of these is the same mathematical object: a set of points and a set of connections between them — a graph. Now ask a question that actually matters to whoever runs that network: if one connection fails, does the whole thing stay in one piece, or does it split into two disconnected islands? Which single link would hurt the most if it went down? Which nodes secretly belong to the same tightly-knit cluster? You could try to answer this by staring at the picture. But for a network with ten thousand nodes there is no picture worth staring at. What you can do instead is write the graph as a matrix, compute its eigenvalues, and read the answers straight off the numbers — no drawing required. That is the entire promise of spectral graph theory: the shape of a network is encoded, exactly and recoverably, in the eigenvalues of two matrices built from it. This chapter derives that encoding from first principles and proves the theorem that makes it work.

From a Network to a Matrix: the Adjacency Matrix

A simple graph G = (V, E) is a set of n vertices V and a set of edges E, each edge an unordered pair of distinct vertices, with no repeated edges and no self-loops. Its adjacency matrix A is the n×n matrix with

A_ij = 1 if vertex i and vertex j are connected by an edge, and A_ij = 0 otherwise (including A_ii = 0, since there are no self-loops).

Consider three students: Aisha is friends with Bhavya, and Bhavya is friends with Chetan, but Aisha and Chetan haven't met. Label them 1, 2, 3. Then

A = | 0  1  0 |
    | 1  0  1 |
    | 0  1  0 |

Because friendship is symmetric, A_ij = A_ji for every pair — the adjacency matrix of any undirected graph is always symmetric, A = A^T. This one fact is the reason everything in this chapter works cleanly: for real symmetric matrices, the Spectral Theorem guarantees every eigenvalue is real (no complex numbers to worry about) and eigenvectors belonging to different eigenvalues are automatically orthogonal. Contrast this with a directed graph's adjacency matrix, which is generally not symmetric and can have complex eigenvalues — outside this chapter's scope.

What a Graph's Eigenvalue Actually Means

Recall the defining equation: a nonzero vector v is an eigenvector of matrix M with eigenvalue λ if Mv = λv — multiplying by M only rescales v, it doesn't change its direction. For an adjacency matrix, look at what one row of the product means: (Av)_i = Σ_j~i v_j, the sum of v's values at every neighbour of vertex i. So an eigenvector of A is a labelling of the vertices with real numbers such that "replace each vertex's number with the sum of its neighbours' numbers" reproduces the exact same labelling, just scaled by λ. Eigenvectors are the labelling patterns that are stable, up to scale, under one step of "spread to your neighbours."

To find these λ, rewrite Av = λv as (A − λI)v = 0. This has a nonzero solution v only when the matrix A − λI is singular, i.e. when its determinant is zero. So every eigenvalue of A is a root of the characteristic equation det(A − λI) = 0. Let's actually solve it for Aisha–Bhavya–Chetan:

        | -λ   1    0 |
A - λI =|  1  -λ    1 |
        |  0   1   -λ |

det(A - λI) = -λ[(-λ)(-λ) - 1·1] - 1[1·(-λ) - 1·0] + 0
            = -λ(λ² - 1) - (-λ)
            = -λ³ + λ + λ
            = -λ³ + 2λ
            = -λ(λ² - 2)

Setting this to zero: λ = 0, λ = √2, λ = −√2. Solving (A − λI)v = 0 for each root gives the eigenvectors (1, 0, −1), (1, √2, 1), and (1, −√2, 1) respectively — you can check each directly by substituting back into Av = λv, row by row.

Look at the eigenvector for the largest eigenvalue, λ = √2: it's (1, √2, 1) — positive at every vertex, and largest at Bhavya, the vertex with the most connections. This is not a coincidence; it's a small instance of the Perron–Frobenius phenomenon: the eigenvector for a connected graph's largest eigenvalue is always sign-consistent, and it weights well-connected vertices more heavily.

Two identities let you sanity-check any eigenvalue computation without a calculator. First, for any matrix, the trace (sum of diagonal entries) equals the sum of the eigenvalues: trace(A) = Σλ_i. Here trace(A) = 0, and indeed 0 + √2 − √2 = 0. Second, trace(A²) = Σλ_i², and combinatorially trace(A²) = Σ_iΣ_j A_ijA_ji = Σ_iΣ_j A_ij² (since A is symmetric) = Σ_iΣ_j A_ij (since each entry is 0 or 1, so A_ij² = A_ij) = Σ_i d_i = 2|E|, twice the edge count, because every edge contributes to exactly two rows' degree sums. Check: 0² + (√2)² + (−√2)² = 4, and 2|E| = 2 × 2 = 4. Matches. Whenever you compute a graph's eigenvalues by hand, run both checks before trusting the answer.

Two Bounds That Locate the Largest Eigenvalue Without Solving a Cubic

For a general graph you rarely want to solve a degree-n characteristic polynomial. Two short arguments bound λ_max using only the degrees.

Lower bound (Rayleigh quotient). For a real symmetric matrix, the Spectral Theorem gives an orthonormal eigenbasis e₁,…,e_n with eigenvalues λ₁ ≥ λ₂ ≥ … ≥ λ_n. Write any unit vector as x = Σc_ie_i with Σc_i² = 1. Then x^TAx = Σλ_ic_i² ≤ λ₁Σc_i² = λ₁, with equality at x = e₁. So λ_max = max_x≠0 (x^TAx)/(x^Tx) — the maximum of this ratio, the Rayleigh quotient, over every possible x, not just eigenvectors. Plug in the all-ones vector 1 (not unit-length, but the ratio form handles that): 1^TA1 = Σ_iΣ_jA_ij = Σ_id_i = 2|E|, and 1^T1 = n. So the Rayleigh quotient at x = 1 equals 2|E|/n, the average degree. Since λ_max is the maximum over all x, in particular λ_max ≥ average degree.

Upper bound. Let Av = λv, and let v_k be the entry of largest absolute value (v_k ≠ 0). Row k of Av = λv reads Σ_jA_kjv_j = λv_k, so λ = Σ_jA_kj(v_j/v_k). Taking absolute values, |λ| ≤ Σ_jA_kj|v_j/v_k| ≤ Σ_jA_kj = d_k ≤ Δ, the maximum degree in the graph — because |v_j| ≤ |v_k| for every j by choice of k. So every eigenvalue of A, not just λ_max, satisfies |λ| ≤ Δ. (This is the graph-theory special case of the Gershgorin Circle Theorem, which you'll meet in full generality in JEE-level and GATE-level linear algebra.)

For Aisha–Bhavya–Chetan: average degree = 4/3 ≈ 1.33, max degree = 2, and indeed 1.33 ≤ √2 ≈ 1.414 ≤ 2. When a graph is regular — every vertex has the same degree d — both bounds collapse to exactly d, because A·1 = d·1 literally (each row sums to d), so 1 is itself an eigenvector with eigenvalue exactly d, and the inequality chain is tight throughout.

Bipartite Graphs: a Symmetric Spectrum

A graph is bipartite if its vertices split into two groups X and Y such that every edge joins a vertex in X to one in Y — no edge stays inside X or inside Y. Claim: if a bipartite graph has λ as an adjacency eigenvalue, it also has −λ as an eigenvalue, with the same multiplicity. The spectrum of a bipartite graph is symmetric about 0.

Proof: let Av = λv, and define v′ by flipping the sign on Y: v′_i = v_i for i ∈ X, v′_i = −v_i for i ∈ Y. For i ∈ X, every neighbour j of i lies in Y (bipartite property), so (Av′)_i = Σ_j~iv′_j = Σ_j~i(−v_j) = −(Av)_i = −λv_i = −λv′_i. For i ∈ Y, every neighbour lies in X, so (Av′)_i = Σ_j~iv′_j = Σ_j~iv_j = (Av)_i = λv_i = λ(−v′_i) = −λv′_i. Either way, Av′ = −λv′, so −λ is an eigenvalue too. □

The 4-cycle C4 (square: 1–2–3–4–1) is bipartite with parts {1,3} and {2,4}. Cycle graphs have the known eigenvalues 2cos(2πk/n) for k = 0,…,n−1; for n = 4 this gives {2, 0, −2, 0} — symmetric about 0, as the theorem predicts. Its top eigenvector is the all-ones vector (1,1,1,1) with λ = 2; sign-flipping the Y-part gives (1,−1,1,−1), and you can check directly that A(1,−1,1,−1)^T = (−2, 2, −2, 2)^T = −2·(1,−1,1,−1)^T, confirming −2 is an eigenvalue.

Now contrast with the triangle K3 (every pair of its 3 vertices is an edge). K3 cannot be 2-coloured without a same-colour edge, so it is not bipartite. Its adjacency matrix is A = J − I, where J is the 3×3 all-ones matrix. J has rank 1, so it has eigenvalue 0 with multiplicity n−1 = 2, and one more eigenvalue equal to trace(J) − 0 − 0 = 3 (with eigenvector the all-ones vector, since J·1 = 3·1 directly). So A = J − I has eigenvalues 3−1 = 2 and 0−1 = −1 (twice): the spectrum of K3 is {2, −1, −1}. This is not symmetric about 0 — consistent with K3 not being bipartite. (The converse of the theorem above — symmetric spectrum forces bipartiteness — is also true, but proving it needs machinery beyond this chapter.)

The Degree Matrix and the Graph Laplacian

Let D = diag(d₁,…,d_n), the diagonal matrix of vertex degrees. The graph Laplacian is L = D − A. For Aisha–Bhavya–Chetan, degrees are (1, 2, 1), so

L = D - A = | 1 -1  0 |
            |-1  2 -1 |
            | 0 -1  1 |

The Laplacian's defining property is a quadratic-form identity, and it's worth deriving rather than quoting. For any real vector x:

x^T L x = x^T D x - x^T A x
        = Σᵢ dᵢxᵢ² - Σᵢ Σⱼ Aᵢⱼ xᵢ xⱼ

Since d_i counts the edges touching vertex i, Σ_id_ix_i² = Σ_{edges (i,j)}(x_i² + x_j²) — each edge contributes x_i² to vertex i's share and x_j² to vertex j's share. And because A is symmetric, Σ_iΣ_jA_ijx_ix_j counts each edge twice, once as (i,j) and once as (j,i), so it equals 2Σ_edges(i,j)x_ix_j. Putting the pieces together:

x^TLx = Σ_{edges (i,j)}(x_i² + x_j² − 2x_ix_j) = Σ_{edges (i,j)}(x_i − x_j)²

This single identity carries two immediate consequences. First, since a sum of squares is never negative, x^TLx ≥ 0 for every x — L is positive semi-definite. Combined with symmetry, every eigenvalue of L is real and non-negative: for an eigenvector v with Lv = μv, μ‖v‖² = v^TLv ≥ 0 forces μ ≥ 0. Second, plug in x = 1, the all-ones vector: every term (x_i − x_j)² = (1−1)² = 0, so 1^TL1 = 0, and directly (L1)_i = d_i − Σ_jA_ij = d_i − d_i = 0 for every i. Every graph's Laplacian, connected or not, has the all-ones vector as an eigenvector with eigenvalue 0. Zero is never a surprise; hold onto this — it matters in the next section.

The Central Theorem: Zero-Eigenvalue Multiplicity Counts Components

Theorem. The multiplicity of 0 as an eigenvalue of L equals the number of connected components of G.

Proof. Because L is symmetric and positive semi-definite, x^TLx = 0 if and only if Lx = 0 (one direction is immediate; for the other, L PSD symmetric means L = B^TB for some matrix B built from oriented edges, so x^TLx = ‖Bx‖² = 0 forces Bx = 0, hence Lx = B^TBx = 0). So the kernel of L is exactly {x : x^TLx = 0} = {x : (x_i − x_j)² = 0 for every edge (i,j)} = {x : x_i = x_j whenever i and j are adjacent}. If i and j lie in the same connected component, a path of edges connects them, forcing x to be constant along that path — so x must be constant on every connected component. Across different components there is no such constraint, so x can take a different constant value on each one. The space of such vectors is spanned by the c indicator vectors of the c components (1 on that component's vertices, 0 elsewhere), which are linearly independent — so this kernel has dimension exactly c. Since L is symmetric, its geometric and algebraic multiplicities always agree, so the eigenvalue 0 occurs exactly c times. □

Check this on two small graphs. Aisha–Bhavya–Chetan is connected (one component); solving det(L − λI) = 0 for the Laplacian above gives λ(λ−1)(λ−3) = 0 after expansion, so the spectrum is {0, 1, 3} — zero appears exactly once, matching one component. Now take a different, disconnected network: Aisha–Bhavya are friends, and separately Chetan–Divya are friends, but no edges cross between the two pairs (two components). Each pair contributes an independent 2×2 Laplacian block [[1,−1],[−1,1]], whose characteristic equation (1−λ)² − 1 = 0 gives λ = 0 or λ = 2. So the full spectrum is {0, 0, 2, 2} — zero appears exactly twice, matching two components. The diagram below shows both cases side by side.

You can verify the eigenvalue arithmetic yourself instead of trusting hand computation alone:

import numpy as np

# Path graph: Aisha(1)-Bhavya(2)-Chetan(3)
A = np.array([
    [0, 1, 0],
    [1, 0, 1],
    [0, 1, 0]
])

D = np.diag(A.sum(axis=1))      # degree matrix: [1, 2, 1]
L = D - A                        # graph Laplacian

print("Adjacency eigenvalues:", np.round(np.linalg.eigvalsh(A), 3))
print("Laplacian eigenvalues:", np.round(np.linalg.eigvalsh(L), 3))

# Output:
# Adjacency eigenvalues: [-1.414  0.     1.414]
# Laplacian eigenvalues: [0.     1.     3.   ]

numpy's eigvalsh returns eigenvalues in ascending order for a symmetric matrix — the output lines up exactly with the by-hand factorisation −λ(λ² − 2) = 0 and λ(λ−1)(λ−3) = 0 above.

Misconception Check: "A Zero Eigenvalue Means the Graph Is Disconnected"

This is one of the most common errors students make with this material, and it's worth stating precisely why it's wrong. A zero Laplacian eigenvalue is not, by itself, evidence of disconnection — it is proved above that 0 is always a Laplacian eigenvalue, for every graph, connected or not, because L·1 = 0 unconditionally. Aisha–Bhavya–Chetan is fully connected and its spectrum {0, 1, 3} still contains a zero. What changes between a connected graph and a disconnected one is never whether 0 shows up — it's how many times it shows up. The correct diagnostic is the multiplicity of the zero eigenvalue, not its mere presence. One zero: connected. Two zeros: exactly two components. And so on.

Algebraic Connectivity: a Robustness Score

Order the Laplacian eigenvalues as 0 = μ₁ ≤ μ₂ ≤ … ≤ μ_n. The second-smallest value, μ₂, is called the algebraic connectivity or Fiedler value (after Miroslav Fiedler, who introduced it in 1973). By the theorem just proved, μ₂ > 0 exactly when the graph has only one component, i.e. is connected — a second zero would mean a second component. The size of μ₂ beyond just "positive" measures how tightly knit the graph is: a large μ₂ means you'd have to delete many, or heavily-used, edges before the network splits; a small positive μ₂ means the network is one thin bridge away from fracturing into two pieces. This is exactly the metro-network question from the opening: compute μ₂ once from the Laplacian, and you have a numerical robustness score without simulating a single line closure.

The eigenvector paired with μ₂, the Fiedler vector, does even more: it assigns each vertex a real number such that vertices on the same "side" of the network get similar values, and the two sides get opposite signs. For Aisha–Bhavya–Chetan, solving (L − 1·I)v = 0 gives v = (1, 0, −1) (verify: L(1,0,−1)^T = (1, 0, −1)^T, exactly 1 times the vector). The sign pattern is exactly right: Aisha at +1, Chetan at −1 on opposite "sides", and Bhavya — the bridge who is friends with both — sits at the neutral value 0 in between. Splitting a large network by the sign of each vertex's Fiedler-vector entry is the core idea behind spectral bisection, used for community detection in social graphs and for partitioning large networks for parallel processing.

Bonus: Counting Spanning Trees From the Spectrum (Kirchhoff's Theorem)

One more classical fact worth knowing, though its full proof needs the Cauchy–Binet determinant identity and is beyond this chapter: for a connected graph on n vertices with Laplacian eigenvalues 0 = μ₁ ≤ μ₂ ≤ … ≤ μ_n, the number of spanning trees is

t(G) = (1/n) · μ₂μ₃⋯μ_n

— the product of every nonzero eigenvalue, divided by n. Check it on both worked examples. For Aisha–Bhavya–Chetan, spectrum {0, 1, 3}: t = (1/3)(1)(3) = 1 — correct, since a path graph is already a tree and has exactly one spanning tree, itself. For the triangle K3, spectrum {0, 3, 3} (from L = D − A = 2I − (J−I) = 3I − J, and J's eigenvalues 3 and 0,0 computed earlier, giving L's eigenvalues 3−3=0 and 3−0=3,3): t = (1/3)(3)(3) = 3 — correct, since deleting any one of K3's three edges leaves a spanning tree, giving exactly three.

Where This Fits Your Exams

CBSE Class 12's Matrices and Determinants chapter supplies the exact machinery used throughout — computing determinants, expanding a cubic, solving a polynomial equation — even though "eigenvalue" is not itself an NCERT term. In JEE Main, JEE Advanced, and BITSAT, characteristic-equation problems (find λ so that a given homogeneous system has a non-trivial solution) are a direct application of det(A − λI) = 0, and "properties of symmetric matrices" (real eigenvalues, orthogonal eigenvectors) recur as standalone facts. Olympiad and KVPY-style problem sets lean on the same proof techniques used here — the parity/sign-flip argument for bipartite spectra, and counting arguments like Kirchhoff's theorem, are standard combinatorics-meets-algebra tools. At the GATE-foundation level, eigenvalues of symmetric matrices sit inside Engineering Mathematics' linear algebra syllabus, and algebraic connectivity together with spectral clustering appear as concepts within graph-based machine learning material.

Practice: Test the Machinery

Try each of these before reading the worked answer beneath it.

1. Star graph K_1,3: one centre vertex (1) connected to three leaves (2, 3, 4), with no edges between leaves. Find its adjacency eigenvalues. Hint: use the symmetry among the leaves — try an eigenvector of the form (a, b, b, b).

   Answer: with v = (a,b,b,b), row 1 of Av = λv gives 3b = λa (centre sees all three leaves); row 2 gives a = λb (each leaf sees only the centre). Substituting a = λb into 3b = λa gives 3b = λ²b, so λ² = 3, i.e. λ = ±√3. Separately, vectors like (0, 1, −1, 0) that are zero at the centre and sum to zero across the leaves satisfy Av = 0 directly (check row 1: 1×1 + 1×(−1) + 1×0 = 0), giving λ = 0 with multiplicity 2. Full spectrum: {√3, 0, 0, −√3}.

2. Verify the two sanity checks (trace and trace-of-square) against your answer to Q1.

   Answer: trace(A) = 0, and √3 + 0 + 0 − √3 = 0 ✓. trace(A²) should equal 2|E| = 2×3 = 6, and Σλ² = 3 + 0 + 0 + 3 = 6 ✓.

3. Find the Laplacian spectrum of K_1,3, and use it to count its spanning trees via Kirchhoff's theorem.

   Answer: degrees are (3,1,1,1), giving Laplacian spectrum {0, 1, 1, 4} (you can verify trace: 0+1+1+4 = 6 = 3+1+1+1). Kirchhoff: t = (1/4)(1)(1)(4) = 1 — correct, since a star is already a tree.

4. True or false, with reason: a connected graph can have algebraic connectivity μ₂ = 0.

   Answer: False. By the central theorem, the multiplicity of the eigenvalue 0 equals the number of connected components. A connected graph has exactly one component, so 0 occurs with multiplicity exactly 1 — meaning μ₁ = 0 but μ₂ must be strictly greater than 0.

Summary

• The adjacency matrix A of an undirected graph is symmetric, so by the Spectral Theorem all its eigenvalues are real and eigenvectors for distinct eigenvalues are orthogonal.
• Every eigenvalue λ of A satisfies (average degree) ≤ λ_max and |λ| ≤ (max degree) for all eigenvalues — proved via the Rayleigh quotient and a direct row-sum argument; both bounds are tight for regular graphs.
• Bipartite graphs have adjacency spectra symmetric about 0, proved by flipping the sign of one part; K3's spectrum {2,−1,−1} shows a non-bipartite graph breaks this symmetry.
• The Laplacian L = D − A satisfies x^TLx = Σ_edges(x_i−x_j)², making it positive semi-definite with 0 always an eigenvalue (eigenvector: all-ones).
• Central theorem: the multiplicity of the Laplacian's zero eigenvalue equals the number of connected components — proved via the kernel of the quadratic form.
• The second-smallest Laplacian eigenvalue, algebraic connectivity μ₂, is positive iff the graph is connected, and its eigenvector (the Fiedler vector) is used to split networks into clusters.
• Kirchhoff's Matrix-Tree theorem recovers the exact count of spanning trees as the product of nonzero Laplacian eigenvalues divided by n.

Think About It

Think about this: How would you explain spectral graph theory: eigenstructure of network adjacency and laplacian matrices to a friend who has never seen a computer? What real-world analogy would you use? Imagine you had to build a system using these concepts — what would be your first step? Try this: before moving on, write down three things you learned and one question you still have.