Spectral Invariants & the Characteristic Polynomial

01 The Hamiltonian–Lagrangian Analogy

The incidence matrix \(B\) generates two natural square matrices via the product \(BB^\top\). Since \(BB^\top = D + A\) (where \(D\) is the degree matrix and \(A\) the adjacency matrix), we get a natural splitting into two operators.

Q = D + A = BB^\top \qquad \text{(``Hamiltonian'': } T + V\text{)}$$ $$L = D - A \qquad\quad \text{(``Lagrangian'': } T - V\text{)}

Think of \(D\) as a "kinetic" term: each vertex's local connectivity, its capacity to transmit. Think of \(A\) as a "potential" term: the coupling between vertices. Their sum \(Q\) is the signless Laplacian. Their difference \(L\) is the graph Laplacian.

The analogy has teeth. In physics the Hamiltonian generates time evolution and its eigenvalues are energy levels. The Lagrangian's stationary points give the equations of motion. In graph theory:

\(Q\) is positive semidefinite. Its smallest eigenvalue is zero only for bipartite graphs. Its spectrum detects bipartiteness and encodes structural information complementary to \(L\).

\(L\) is positive semidefinite. Its kernel is the space of locally constant functions: one zero eigenvalue per connected component. Its nonzero eigenvalues measure how "hard" it is to cut the graph. The heat equation \(\dot{u} = -Lu\) describes diffusion on the network, exactly as the Lagrangian generates dynamics.

The stationary principle. The Fiedler vector (eigenvector of the smallest nonzero Laplacian eigenvalue) solves a variational problem: it minimises \(\mathbf{x}^\top L \mathbf{x}\) subject to \(\mathbf{x} \perp \mathbf{1}\) and \(\|\mathbf{x}\| = 1\). This is the graph-theoretic analogue of the principle of least action. The Fiedler vector finds the "easiest cut" of the graph.

02 The Eigenvalue Spectrum

The eigenvalues of \(L\), \(Q\), and \(A\) are three different windows onto the same graph. Each carries distinct information.

Spectral ExplorerEigenvalues of L, Q, and A

Eigenvalues shown as bars. L (green), Q (blue), A (orange).

The Laplacian spectrum (green bars) always starts with at least one zero. Additional zeros indicate disconnected components. The first nonzero eigenvalue \(\lambda_2\) (the Fiedler value or algebraic connectivity) measures how tightly connected the graph is. For the complete graph \(K_4\), \(\lambda_2 = 4\); for the path \(P_4\), \(\lambda_2 \approx 0.59\). Paths are easy to cut; complete graphs are not.

The signless Laplacian spectrum (blue bars) is always nonnegative. Its smallest eigenvalue is zero if and only if the graph has a bipartite component. Check: the square and path are bipartite (smallest blue bar at zero); the triangle and \(K_4\) are not.

The adjacency spectrum (orange bars) can be negative. For a \(d\)-regular graph, the largest adjacency eigenvalue is always \(d\). The gap between the largest and second-largest eigenvalue controls expansion and mixing.

03 The Characteristic Polynomial

All three spectra are roots of their respective characteristic polynomials. For the adjacency matrix:

p_A(\lambda) = \det(\lambda I - A)

This is a polynomial of degree \(|V|\) whose roots are the eigenvalues. But its coefficients carry independent combinatorial meaning. The coefficient of \(\lambda^{n-k}\) in \(p_A(\lambda)\) counts (with sign) the number of certain subgraph structures with \(k\) edges. Specifically, it sums over all "elementary subgraphs" — disjoint unions of edges and cycles — that cover exactly \(k\) vertices.

For the Laplacian, the characteristic polynomial encodes even more. By the Matrix-Tree theorem, the coefficient of \(\lambda\) in \(p_L(\lambda)\) (up to sign) equals the number of spanning trees times \(n\):

p_L(\lambda) = \lambda \prod_{i=2}^n (\lambda - \lambda_i) \implies \text{coefficient of } \lambda = (-1)^{n-1} \prod_{i=2}^n \lambda_i = (-1)^{n-1} n \cdot \tau(G)

where \(\tau(G)\) is the number of spanning trees.

Characteristic PolynomialCoefficients of det(λI − M)

Polynomial coefficients shown for A and L.

From Fibonacci to characteristic polynomials. The Fibonacci matrix \(Q = \begin{pmatrix}1&1\\1&0\end{pmatrix}\) has characteristic polynomial \(\lambda^2 - \lambda - 1\). Its roots are \(\phi = \frac{1+\sqrt{5}}{2}\) (the golden ratio) and \(\hat{\phi} = \frac{1-\sqrt{5}}{2}\). The closed-form Binet formula \(F_n = \frac{\phi^n - \hat{\phi}^n}{\sqrt{5}}\) comes directly from diagonalising \(Q\) via its characteristic polynomial. The same idea — eigendecomposition via the characteristic polynomial — gives closed-form expressions for random walks, diffusion, and mixing on graphs.

04 The Invariant Hierarchy

Eigenvalues are powerful but not all-powerful. There exist non-isomorphic graphs with identical spectra (cospectral graphs). The full hierarchy of invariants, from weakest to strongest:

Kirchhoff's Theorem

The number of spanning trees equals any cofactor of \(L\), or equivalently \(\frac{1}{n}\prod_{i=2}^{n} \lambda_i\).

A single number extracted from the Laplacian that counts a topological quantity. The descendant of the Fibonacci determinant.

Chromatic Polynomial

\(P(G, k)\) counts proper colourings with \(k\) colours. It is a polynomial in \(k\) whose coefficients encode the graph's cycle structure. \(P(G, k) = 0\) for \(k < \chi(G)\), the chromatic number.

Ihara Zeta Function

Counts prime (backtrackless) cycles. For adjacency matrix \(A\) and degree matrix \(D\):

\(\zeta_G(u)^{-1} = (1-u^2)^{|E|-|V|} \det(I - Au + (D-I)u^2)\)

A graph-theoretic Riemann zeta. The Riemann hypothesis for regular graphs is equivalent to the graph being Ramanujan (optimal spectral gap).

Tutte Polynomial

\(T(G; x, y)\) is the universal deletion-contraction invariant. Special evaluations yield: spanning trees (\(T(1,1)\)), colourings, reliability, the Jones polynomial, and the Potts model partition function.

Strictly stronger than any single matrix invariant.

The Potts model and the surface code

The Tutte polynomial of a planar graph, evaluated along a certain curve, gives the partition function of the \(q\)-state Potts model. The Ising model is \(q = 2\). The surface code error threshold maps to the phase transition of the random-bond Ising model. So the invariant hierarchy closes on the physics:

Determinant (Fibonacci) \to counts a single quantity Spectrum (eigenvalues) \to counts spanning trees, measures connectivity Characteristic polynomial \to encodes the full spectrum in one object Ihara zeta \to counts prime cycles, the "Riemann hypothesis" for graphs Tutte polynomial \to universal invariant, contains all above as special cases Potts partition function \to statistical mechanics on the graph = error threshold

What none of these capture. All of the above are graph invariants: they are preserved under relabelling of vertices. But none distinguishes all non-isomorphic graphs. The graph isomorphism problem — whether two graphs are "the same" up to relabelling — remains unresolved by any known polynomial-time invariant. The Weisfeiler-Leman hierarchy of colour-refinement algorithms gives progressively stronger (but never complete) tests. Whether graph isomorphism is in P remains open.