Two graphs the eigenvalues cannot tell apart

The cycles and the cuts turned a graph into a matrix and read two numbers off it: the rank, which counted the independent cuts, and the nullity, which counted the independent cycles. It ended by admitting how little that is. Two graphs with the same number of points, edges and pieces have the same rank and nullity whatever else is true of them, and a count that coarse cannot tell a ring from a tree with a triangle hanging off it.

The natural refinement is to ask the matrix for more than its rank. A square matrix has eigenvalues — the stretch factors of the directions it leaves alone — and a graph’s matrix has a full list of them, one for each point, all real because the matrix is symmetric. That list is called the graph’s spectrum, and it is a far richer summary than one rank. The question this essay asks is how rich: whether the eigenvalues of a graph’s matrix determine the graph.

The answer is no, and the smallest witness is small enough to check by hand. Put one point in the middle of four others and join it to each of them: a star with four arms. Separately, draw a square and put one point beside it with no edges at all. The two drawings have five points and four edges apiece and share nothing else — one is connected, the other falls into two pieces; one has a point with four neighbours, the other has no point with more than two.

Both have eigenvalues $2$, $-2$ and $0$ three times. The characteristic polynomials are not merely close in value; written out in whole numbers they are identical, $x^5 - 4x^3$, coefficient for coefficient. Anything the eigenvalues can say about one of these graphs they say about the other, and one of them is in two pieces.

The matrix that is being asked #

The adjacency matrix of a graph on $n$ points is the $n \times n$ array with a $1$ in row $i$ and column $j$ when points $i$ and $j$ are joined, and $0$ otherwise. It is not the matrix the cycles and the cuts used — that one had a row for every edge — but it is built from the same information, and it has the property the incidence matrix lacked: it is square, so it has a characteristic polynomial and eigenvalues.

Relabelling the points permutes the rows and columns together, which is a change of basis by a permutation matrix, and a change of basis never alters eigenvalues. So the spectrum belongs to the graph, not to the drawing or the numbering, and any two isomorphic graphs have the same one. That is the direction that is free. The question is the converse — whether equal spectra force isomorphic graphs — and it is a question about how much information survives the passage from an array of $n^2$ entries to a list of $n$ numbers.

Put that way, the answer ought to be no by counting alone: the number of graphs on $n$ points grows like $2^{n^2/2}$, and a list of $n$ numbers, each a root of a whole-number polynomial with bounded coefficients, is a much smaller space. That argument is suggestive and not a proof, because the spectra of graphs are not arbitrary lists. What settles it is an example, and the star is the smallest one there is.

Nothing here depends on which eigenvalue method finds the numbers. The characteristic polynomial $\det(xI - A)$ has whole-number coefficients for any whole-number matrix, and two graphs are cospectral exactly when those whole numbers agree. The figures compare the whole numbers, never a pair of decimal lists that happen to look alike.

What the eigenvalues count #

Before the failure, the success, because it is larger than it has any right to be.

The trace of a matrix is the sum of its eigenvalues, and the trace of its $k$-th power is the sum of their $k$-th powers — the eigenvalues of $A^k$ are the $k$-th powers of those of $A$. On the other side, the entry of $A^k$ in row $i$ and column $j$ counts the walks of $k$ steps from $i$ to $j$: each step multiplies by $A$ once, and a product of entries is $1$ exactly when every step in the sequence runs along an edge. The diagonal entries count walks that come back to where they started, so

$$\operatorname{tr} A^k = \sum_i \lambda_i^k = \text{the number of closed walks of length } k.$$

That identity is the whole mechanism — it is the same one by which a matrix counts the returns of a map in dynamics — and it hands over a great deal. A closed walk of length two goes out along an edge and straight back, and there are two of them for every edge, one from each end; so the number of edges is half the sum of the squared eigenvalues. A closed walk of length three is a triangle traversed from one of its three corners in one of two directions; so the number of triangles is a sixth of the sum of the cubes.

The prism makes the bookkeeping concrete. Its eigenvalues are $3, 1, 0, 0, -2, -2$. Their squares add to $9 + 1 + 4 + 4 = 18$, which is twice its nine edges; their cubes add to $27 + 1 - 8 - 8 = 12$, which is six times its two triangles. Neither count was taken from the drawing. The eigenvalues were found from the polynomial and the walks were counted by stepping round the graph, and the figure requires the two to agree at every length before it draws a cell.

The spectrum also knows whether a graph is bipartite. A graph whose points split into two sides with every edge crossing has no closed walk of odd length, so every odd power sum is zero; and the only way for every odd power sum of a list of real numbers to vanish is for the list to be symmetric about zero. The star and the square are both bipartite, and both spectra are symmetric — the $2$ and the $-2$, the zeros in the middle.

Why the pair has to agree #

With that mechanism in hand, the coincidence stops being mysterious and becomes a statement about walks. Two graphs are cospectral exactly when they have the same number of closed walks of every length — because the power sums of a list of $n$ numbers determine the list, which is Newton’s identities run in reverse.

So the pair can be checked without any eigenvalue at all. In the star, a closed walk of even length $2m$ alternates between the centre and the arms. Starting at the centre it chooses an arm for each of its $m$ outward steps, $4^m$ ways; starting at one of the four arms it is forced to the centre on every odd step and chooses an arm on each of the $m - 1$ intermediate outward steps before the last, which returns it to the arm it began on, $4^{m-1}$ ways for each of four arms. That is $2 \cdot 4^m$ in all.

In the square, every step from a corner goes one way or the other round it, so there are $4^m$ walks of $2m$ steps from any corner. Before the last step the walk has taken an odd number of steps and stands on one of the start’s two neighbours, and from there one of its two choices returns to the start and the other goes to the opposite corner — so exactly half the walks come home, $\tfrac12 4^m$ from each corner, and four corners give $2 \cdot 4^m$. The lone point contributes nothing, since no walk of positive length can start there. The same $2 \cdot 4^m$, arrived at by two different arguments about two different drawings. The lone point is exactly what the square needs: without it the square’s matrix would be four by four and the star’s five by five, and a spectrum that includes its own length cannot be shared across sizes. With it, the square borrows a zero eigenvalue and a place in the count, and contributes nothing else.

A different matrix hears the pieces #

The adjacency matrix is not the only square array a graph has, and the one a determinant that counts trees used behaves differently. The Laplacian has each point’s number of neighbours down the diagonal and a $-1$ for every edge off it; it is the incidence matrix multiplied by its own transpose, which is why it is symmetric and why none of its eigenvalues is negative.

A vector is sent to zero by the Laplacian exactly when it is constant across every edge — the potentials the cycles and the cuts called flat — so the number of zero eigenvalues is the number of pieces. That is a statement the adjacency matrix cannot make, and it separates the star from the square at once.

The star’s Laplacian eigenvalues are $5, 1, 1, 1, 0$, and the square-and-point’s are $4, 2, 2, 0, 0$. One zero against two, and the number of pieces read straight off the list. The matrix-tree theorem says more: the product of the non-zero Laplacian eigenvalues divided by the number of points is the number of spanning trees, which for the star is $5 \cdot 1 \cdot 1 \cdot 1 / 5 = 1$ — the star is its own only spanning tree — and for a disconnected graph is zero by the extra zero eigenvalue.

This is the shape of the whole subject. Each matrix hears some features and is deaf to others, and which it hears is decided by what its powers count. The adjacency matrix’s powers count walks, so it hears closed walks and anything computable from them. The Laplacian’s quadratic form, $\sum (x_i - x_j)^2$ over the edges, measures how much a function on the points varies across edges, so it hears pieces, trees, how fast a random walk forgets its start and the narrow doors that slow it. Neither is the graph.

Every small graph, checked #

A single pair is an existence proof and says nothing about how common the phenomenon is. That question can be settled completely for small graphs, because there are not many of them.

On six points there are $2^{15} = 32{,}768$ ways to choose which of the fifteen possible edges are present, and they fall into 156 graphs once relabellings are identified. The census below walks every labelled graph, groups them into those 156 classes by generating each class’s full orbit under the 720 relabellings, computes each class’s two characteristic polynomials in whole numbers, and asks how many classes share a polynomial with another. The class counts for two to six points must come out as the known $2, 4, 11, 34, 156$ before anything else is read.

On four points or fewer every graph is determined by either spectrum. On five, the adjacency census finds exactly one coincidence — the pair already drawn — and the Laplacian finds none. On six, ten of the 156 graphs have an adjacency twin and four have a Laplacian twin. The Laplacian is the sharper instrument at this size, and it is not a perfect one either.

The count is exhaustive and so it is a theorem about six points, not a sample: there is no seventh pair hiding in an unexamined corner, because there are no unexamined corners. It says nothing about seven, where the same procedure would walk two million labelled graphs, and much less about seventy.

The Laplacian’s smallest failure #

The first Laplacian coincidence is worth seeing, because the difference it hides is not the one the adjacency pair hid.

Both are connected, so the count of zero eigenvalues agrees. Both have seven edges, which the Laplacian must preserve, since its trace is twice the number of edges. Both have twelve spanning trees — the product of the non-zero eigenvalues, $72$, divided by six — and that is a fact nobody would guess by looking. But their points have different numbers of neighbours: one graph has a point of degree four and five of degree two, the other three of degree three, two of degree two and one of degree one. The Laplacian carries the degrees on its diagonal and still cannot recover them from its eigenvalues. The spectrum knows the sum of the degrees and the sum of their squares, since those are the traces of the first two powers adjusted by the edges, and that is not the same thing as knowing the list.

So the two matrices fail differently. The adjacency matrix could not hear a missing connection; the Laplacian hears connections and cannot hear how the edges are shared out among the points. Combining them helps and is still not enough — there are graphs cospectral for both at once, and for every one of the several other matrices that have been tried.

The drum a graph beats #

The question has a famous continuous cousin, and the analogy is exact enough to be useful.

In 1966 Mark Kac asked whether one can hear the shape of a drum: whether the frequencies at which a membrane vibrates determine its outline. The frequencies are the eigenvalues of the Laplacian of the region — the continuous version of the matrix above — and the question is precisely whether a Laplacian’s spectrum determines the space it lives on. In 1992 Carolyn Gordon, David Webb and Scott Wolpert produced two different polygonal drums with the same frequencies, and the construction behind them, due to Toshikazu Sunada, is combinatorial: it glues copies of a triangle together according to two different permutation patterns, and the equality of spectra comes from an equality of counts — a group-theoretic statement that two ways of assembling the pieces see every closed path the same number of times.

That is the closed-walk argument above, moved from a graph to a surface. Two objects sound the same when they have the same number of returns of every length, and the returns do not remember where they were made. The drums are to Kac’s question what the star and the square are to the matrix one: the smallest honest counterexample, found by making the returns agree while the shape disagrees.

It also explains why the answer was widely expected to be yes before it was no. What a spectrum does determine is substantial — for a drum, its area, its perimeter and the number of its holes; for a graph, its edges, its triangles and its bipartiteness — and a list of invariants that long feels as though it ought to close. It does not, and it fails at the first size it can.

How often a spectrum decides #

Whether the star is typical or exceptional is the question the census begins to answer, and the answer changes with the kind of graph.

For trees it is nearly always no. Allen Schwenk proved in 1973 that almost every tree has a partner with the same adjacency spectrum: as the number of points grows, the share of trees determined by their spectrum falls to zero. The reason is a transplanting trick. A particular small branch can be grafted onto a tree at either of two points without changing the characteristic polynomial, and a large random tree almost always contains that branch somewhere, so almost every large tree has a twin made by moving it.

For graphs in general the evidence points the other way, and it is only evidence. Andries Brouwer and Edward Spence counted cospectral graphs up to twelve points by computer in 2009: the share with an adjacency twin climbs to about a fifth near eleven points and then begins to fall at twelve, while the Laplacian’s share stays lower throughout. Willem Haemers conjectured that almost all graphs are determined by their spectrum, meaning that the share of graphs with a twin tends to zero. The conjecture is open, and the gap in knowledge is lopsided in an unusual way: families of cospectral pairs are easy to construct — Chris Godsil and Brendan McKay’s switching method of 1982 turns many graphs into twins of themselves — and families of graphs proved to have no twin are rare and special.

So the census at six points is the first page of a table whose later pages are only partly written, and the number that matters most, the limit of the share, is not known to exist.

The pictures show six points and stop #

Every graph drawn here has at most six points, and every claim about larger graphs is quoted. The census is a theorem at six and silent at seven; the rise to a fifth and the fall at twelve are Brouwer and Spence’s counts, not the figure’s.

The eigenvalues are drawn as marks on a line, which shows that two lists coincide and nothing about why. The explanation — equal numbers of closed walks — is in the walk table, and the walk table establishes it only length by length up to eight. That the whole infinite sequence agrees follows from the polynomials agreeing, which the figures check in whole numbers; the table illustrates that fact and does not prove it.

No figure shows the isomorphism test failing. That the star and the square are different graphs is visible — one has two pieces — and that the six-point Laplacian pair differs is certified by their degree lists. The census distinguishes classes by generating orbits, which is a complete test at six points and an impractical one at sixty; the problem of deciding whether two large graphs are the same is a subject of its own, with a quasi-polynomial algorithm due to László Babai since 2015 and no polynomial one known.

Still open: which graphs a spectrum determines #

The sharpest form of the question is Haemers’s conjecture — that the share of graphs on $n$ points with a cospectral twin tends to zero as $n$ grows — and it is open for the adjacency matrix, for the Laplacian and for every other matrix anybody has proposed. The computations support it and nobody has a proof that even a positive share of graphs is determined.

A more modest question is also open: which specific families are. The complete graphs, the cycles, the paths and the disjoint unions of complete graphs are determined by their adjacency spectra; the complete bipartite graphs are not in general, and the star is the smallest of them to fail. For most named families the question has not been settled, and each answer so far has needed its own argument.

What the pair teaches about invariants #

The habit worth keeping is the one the closed walks supplied.

An eigenvalue sounds like a delicate, global quantity, the output of a root-finding problem nobody would solve by hand. The trace formula turns it into a census: the whole spectrum is the same information as the list of closed-walk counts, and those are counted by stepping round the drawing. So asking what a spectrum determines is asking what the returns determine, and a structure the returns never visit — the lone point, the way degrees are shared out — is a structure the spectrum cannot see.

That makes the negative answer less of a disappointment and more of a map. Each matrix a graph can be given counts some family of closed paths; the features those paths detect are exactly the features its spectrum detects; and two graphs that agree on every such count are twins for that matrix however different they look. The star and the square agree on every walk and disagree on everything else, which is the precise sense in which a list of eigenvalues is a shadow of the graph and not the graph itself.