9
$\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.

Improve this question
$\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
    Commented Feb 27, 2012 at 19:09
  • 8
    $\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$
    – Qiaochu Yuan
    Commented 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
    Commented 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$
    – Chris Godsil
    Commented 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$
    – Douglas Zare
    Commented Jun 6, 2012 at 20:18

2 Answers 2

Reset to default
5
$\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.

Improve this answer
$\endgroup$
7
  • 3
    $\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$
    – Douglas Zare
    Commented 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$
    – tweetie-bird
    Commented 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$
    – tweetie-bird
    Commented 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$
    – Gjergji Zaimi
    Commented 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$
    – tweetie-bird
    Commented 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.

Improve this answer
$\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$
    – Felix Goldberg
    Commented 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$
    – Francesc Font-Clos
    Commented Jun 24, 2012 at 22:50

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .