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

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.

-
Every tree is a bipartite graph and the adjacency matrix is therefore of this form en.wikipedia.org/wiki/… – Jernej Feb 27 2012 at 19:09
If a graph is a tree then its adjacency matrix can be written in the form $N + N^T$ where $N$ is nilpotent (pick a root and direct all the edges towards it). – Qiaochu Yuan Feb 27 2012 at 19:33
The Smith Normal Form of the adjacency matrix must be $(1,\dots,1,0)$. – Andy B Feb 27 2012 at 21:30
All trees are bipartite. As the comments show many strange things can said about their adjacency matrices. Voting to close. – Chris Godsil Feb 28 2012 at 2:15
@Qiaochu Yuan: If an undirected graph with no loops is not a tree, you can still write its adjacency matrix as $N + N^T$ where $N$ is nilpotent. Is there something related to this which is particular to trees? – Douglas Zare Jun 6 at 20:18
show 4 more comments

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.

-
You can modify any eigenvector with eigenvalue $\lambda$ by negating the values on one of the parts to get an eigenvector with eigenvalue $-\lambda$. – Douglas Zare Jun 6 at 20:12
I see -- you have given a proof of my conjecture in the specific case of adjacency matrices of bipartite graphs (rather than working with the relations among real numbers), noting that the standard basis vectors are indexed by the nodes of the graph and that applying the adjacency matrix sends a node to the sum of standard basis vectors indexing its neighbors. That's a nice proof! Thanks! – tweetie-bird Jun 6 at 20:27
Now I'm also curious about the general statement for real numbers $\lambda_1, \dots ,\lambda_n$ of whether knowing $\sum_{j=1}^n \lambda_j^i =0$ for all positive, odd integers $i$ implies that the nonzero reals come in pairs $\mu_j, \nu_j$ of equal magnitude and opposite sign. It looks like this might follow from a variant on the Vandermonde determinant being nonzero where the usual Vandermonde matrix entry $a_i^j$ is replaced by $\mu_i^j + \mu_i^{j-1}\nu_i + \mu_i^{j-2}\nu_i^2 + \cdots + \nu_i^j$. – tweetie-bird Jun 6 at 23:40
@tweetie-bird: Look at the characteristic polynomial $P(x)=\prod(x-\lambda_i)$. Since your odd-power sums vanish then $\log P(x)$ is even. This implies $P$ is even so the roots come in pairs $\pm \lambda$. – Gjergji Zaimi Jun 7 at 0:08
Thanks! I'm a little slow in understanding your comment though I'm afraid. I don't yet see how to deduce that $log P(x)$ is even. I'll keep thinking about it. – tweetie-bird Jun 7 at 0:24
show 2 more comments

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.

-
What is the connection? The matrix-tree theorem counts spanning trees in a general graph. The OP asked something about trees (or bipartite graphs). – Felix Goldberg Jun 7 at 8:49
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. – Francesc Font-Clos Jun 24 at 22:50