8
$\begingroup$

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.

$\endgroup$
9
  • 2
    $\begingroup$ Every tree is a bipartite graph and the adjacency matrix is therefore of this form en.wikipedia.org/wiki/… $\endgroup$
    – Jernej
    Feb 27, 2012 at 19:09
  • 7
    $\begingroup$ 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). $\endgroup$ Feb 27, 2012 at 19:33
  • 2
    $\begingroup$ The Smith Normal Form of the adjacency matrix must be $(1,\dots,1,0)$. $\endgroup$
    – Andy B
    Feb 27, 2012 at 21:30
  • 2
    $\begingroup$ All trees are bipartite. As the comments show many strange things can said about their adjacency matrices. Voting to close. $\endgroup$ Feb 28, 2012 at 2:15
  • 1
    $\begingroup$ @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? $\endgroup$ Jun 6, 2012 at 20:18

2 Answers 2

4
$\begingroup$

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.

$\endgroup$
7
  • 2
    $\begingroup$ You can modify any eigenvector with eigenvalue $\lambda$ by negating the values on one of the parts to get an eigenvector with eigenvalue $-\lambda$. $\endgroup$ Jun 6, 2012 at 20:12
  • $\begingroup$ 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! $\endgroup$ Jun 6, 2012 at 20:27
  • $\begingroup$ 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$. $\endgroup$ Jun 6, 2012 at 23:40
  • $\begingroup$ @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$. $\endgroup$ Jun 7, 2012 at 0:08
  • $\begingroup$ 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. $\endgroup$ Jun 7, 2012 at 0:24
-1
$\begingroup$

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.

$\endgroup$
2
  • 2
    $\begingroup$ What is the connection? The matrix-tree theorem counts spanning trees in a general graph. The OP asked something about trees (or bipartite graphs). $\endgroup$ Jun 7, 2012 at 8:49
  • $\begingroup$ 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. $\endgroup$ Jun 24, 2012 at 22:50

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

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