If graph is tree what can be said about its adjacency matrix ? - MathOverflow

If graph is tree what can be said about its adjacency matrix ?

2012-02-27T18:47:33Z

Question If graph is tree what can be said about its adjacency matrix ? And vice versa ?

Especially I am interested in case when graph is bipartite graph.

Such graphs are related to error-correction codes (see e.g. http://mathoverflow.net/questions/89658/adjacency-matrices-of-graphs-as-parity-check-matrices-of-error-correcting-codes). If they are trees belief propagation is known to produce exact results.

Answer by Francesc Font-Clos for If graph is tree what can be said about its adjacency matrix ?

2012-06-01T22:36:18Z

check the "matrix tree theorem"

So, a tree has only one spanning tree (which is itself of course), and conversely, if a graph has only one spanning tree, it must be a tree. Hence using the matrix tree theorem, which as you say counts the number of spanning trees, we can determine if a general graph is a tree or not.

Answer by tweetie-bird for If graph is tree what can be said about its adjacency matrix ?

2012-06-06T19:42:11Z

A graph is bipartite iff the odd powers of the adjacency matrix have all 0's on the diagonal. So this implies that the sum of the $i$-th powers of the eigenvalues is 0 for each odd $i$. Since the adjacency matrix is symmetric, it has real eigenvalues. Thus, the eigenvalues are real numbers $\lambda_1,\dots ,\lambda_n $ with $\sum_{j=1}^n \lambda_j^i = 0$ for each odd $i$.

I am guessing this probably should mean that the nonzero eigenvalues come in pairs of equal magnitude and opposite sign. I wonder if there is a good trick for efficiently proving this sort of thing -- about collections of real numbers satisfying such an infinite family of relations? (If so, I don't know this trick.)

${\bf Edit:}$ Douglas Zare proved my above conjecture as a comment, so it is true for bipartite graphs that the nonzero eigenvalues of the adjacency matrix come in pairs of equal magnitude and opposite sign.