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](http://qchu.wordpress.com/2010/04/27/the-mckay-correspondence-i/). 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. 



Combinatorial proof of (a special case of) the spectral theorem?
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"](http://journals.cambridge.org/action/displayFulltext?type=1&fid=2197932&jid=CPC&volumeId=1&issueId=01&aid=1771436), 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.


