Take the 2-minute tour ×
MathOverflow is a question and answer site for professional mathematicians. It's 100% free, no registration required.

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. Adjacency matrices of graphs as parity check matrices of error correcting codes ). If they are trees belief propagation is known to produce exact results.

share|improve this question
1  
Every tree is a bipartite graph and the adjacency matrix is therefore of this form en.wikipedia.org/wiki/… –  Jernej Feb 27 '12 at 19:09
6  
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 '12 at 19:33
1  
The Smith Normal Form of the adjacency matrix must be $(1,\dots,1,0)$. –  Andy B Feb 27 '12 at 21:30
1  
All trees are bipartite. As the comments show many strange things can said about their adjacency matrices. Voting to close. –  Chris Godsil Feb 28 '12 at 2:15
1  
Despite the votes to close, I think this is a reasonable question, just the accents should be changed; say, like this: what is the (most) efficient way to tell from the adjacency matrix whether the graph is a tree? –  Seva Jun 7 '12 at 7:14

2 Answers 2

up vote 4 down vote accepted

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.

share|improve this answer
2  
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 '12 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 '12 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 '12 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 '12 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 '12 at 0:24

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.

share|improve this answer
2  
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 '12 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 '12 at 22:50

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

Not the answer you're looking for? Browse other questions tagged or ask your own question.