Combinatorial proof of (a special case of) the spectral theorem?

Question

The spectral theorem for a real $n \times n$ symmetric matrix $A$ says that $A$ is diagonalizable with all eigenvalues real. If $A$ happens to have non-negative integer entries, it can be interpreted as the adjacency matrix of an undirected graph $G$, and the spectral theorem gives us information about how the sequences $A_{ij}^n$ behave, which count the number of walks of length $n$ from vertex $i$ to vertex $j$. In particular, it says that $A_{ij}^n$ has the form $\sum_{k=1}^{n} a_{ijk} \lambda_k^n$ for some real $\lambda_k$ and some $a_{ijk}$.

If $A$ is not symmetric, on the other hand, two things can happen that don't happen in the above case:

• The $\lambda_k$ may fail to be real. In other words, there can be "periodicity" of period greater than $2$ in the sequences $A_{ij}^n$. This happens, for example, if $A$ is a directed cycle graph.

• The coefficients $a_{ijk}$ may be polynomials in $n$. This happens, for example, if $A$ is a directed path graph with loops based at each vertex.

Is it possible to prove "combinatorially" that neither of these things can happen when $A$ is symmetric? (What I mean is that, given only that you know what $A_{ij}^n$ looks like in terms of eigenvalues, what can you prove just by looking at $G$?) For example, it is straightforward to prove that the coefficient of the largest positive eigenvalue is constant by a path-counting argument which I described here. I think a path-counting argument can also in principle prove that the $\lambda_k$ are real via some kind of mixing argument which could show that the only constraint on the length of a long walk from a vertex to itself is its length mod 2 (due to the presence of even cycles). I think such an argument can at least show that the eigenvalues of maximum absolute value must be real, but I don't know how easy it is to deduce information about the other eigenvalues.

If you have a solution with "adjacency matrix" replaced by "Laplacian," I'd also be interested in that.

Answer 1

I believe the answer is yes and that this might be found somewhere in the literature on the graph reconstruction problem.

Let me denote the characteristic polynomial of the graph $G$ as $\phi(G,x)$ and let its cofactors be $\phi_{ij}(G,x)$. In the paper "Walk Generating Functions, Christoffel-Darboux Identities and the Adjacency Matrix of a Graph", C.D. Godsil proves the following lemma (5.2) which is a graph theoretic analogue to the Christoffel-Darboux formula for orthogonal polynomials, the identity can be proven by purely combinatorial means:

Let $V(G)=\{1,2,\dots,n\}$ be the vertices of $G$, then for any pair $i,j$ one has $$\sum_{k\in V(G)}\phi_{ik}(G,x)\phi_{jk}(G,y)=\frac{\phi_{ij}(G,x)\phi(G,y)-\phi_{ij}(G,y)\phi(G,x)}{y-x}.$$

Taking $i=j$ one obtains $$\sum_{k\in V(G)}\phi_{ik}(G,x)\phi_{ik}(G,y)=\frac{\phi_{ii}(G,x)\phi(G,y)-\phi_{ii}(G,y)\phi(G,x)}{y-x}.$$

If there was a graph with a complex eigenvalue then pick such a graph with the smallest number of vertices. Let the eigenvalue be $\eta$, and substitute in our identity $x=\eta, y=\bar{\eta}$. We see that the RHS vanishes and so must $\sum_{k\in V(G)}|\phi_{ik}(G,\eta)|^2$, so in particular $\phi_{ii}(G,\eta)=0$. But $\phi_{ii}(G,x)=\phi(G/i,x)$ and so $G/i$ would then be a graph with one less vertex having $\eta$ as an eigenvalue, contradicting our minimality assumption.

Answer 2

Not an answer, but perhaps the basis for a plan of attack ...

A consequence of the spectral theorem as it applies to the adjacency matrix of a graph $G$ is that, for every (presumably real) eigenvalue --say, with multiplicity $m$-- there exists a geometric realization, $R$, of $G$ in $\mathbb{R}^m$ such that each automorphism of $G$ induces a rigid isometry of $R$. I call these "spectral realizations" (which I discuss at length in my note "Spectral Realizations of Graphs" (PDF)). A spectral realization has this eigenic property: moving each vertex to the vector sum of its neighbors has the same effect as scaling the realization by the associated eigenvalue.

For example, these are the spectral realizations of the 15-cycle and the (skeleton of the) Truncated Octahedron (uniform polyhedron $U_8$).

Spectral Realizations of the 15-cycle http://daylateanddollarshort.com/math/pdfs/mathoverflow-spectralpolygons.png

(Whoops! Typo: Caption should read "Note that (b), (c), (e), and (h) are faithful".)

Spectral Realizations of the Truncated Octahedron http://daylateanddollarshort.com/math/pdfs/mathoverflow-spectralpolyhedra.png

(The caption seems to imply that there are other, higher-dimensional, realizations of the Truncated Octahedron; in this case, there are none. The caption is a template used for over 70 figures in my note, and I haven't gone back to edit the individual cases.)

One way to attack your problem, then, would be to attempt to reverse the implication: Use the combinatorics of the graph to prove independently that sufficiently many spectral realizations exist, "using up" all the eigen-dimensions; the associated eigenvalues must be real as they serve as scale factors for the eigenic property of these realizations.

It's not clear to me how a combinatorial approach to finding these realizations would proceed; they fall so neatly out of the spectral theorem, after all. However, I can demonstrate that sometimes there's a nice interplay between the combinatorics and the geometry; here's an example I left as a comment to an answer of another MO question:

Proposition: If $\lambda$ is a (real) eigenvalue of a bipartite graph, then so is $-\lambda$.

Proof: If $\lambda$ is a (real) eigenvalue, then there exists a corresponding spectral realization of the graph, such that the realization has the eigenic property with scale factor $\lambda$. If the graph is bipartite, take a two-coloring of its vertices; for each vertex of a chosen color, move the corresponding realized vertex to its reflection in the origin. The result is a realization with eigenic scale factor $-\lambda$, which must therefore be an eigenvalue of the graph. QED. (Note: The Truncated Octahedron, pictured above, is bipartite.)

I'd love to see the geometry of these realizations explained completely from the combinatorics of the graphs. (I'm personally trying to investigate the combinatorial conditions under which two spectral realizations may share the same vertex coordinates, as with pairs of the Truncated Octahedra realization shown, or the Dodecahedron and Great Stellated Dodecahedron, etc.) I hope you keep us posted on your progress in this area.