If graph is tree what can be said about its adjacency matrix ? - MathOverflow most recent 30 from http://mathoverflow.net 2013-05-19T21:07:53Z http://mathoverflow.net/feeds/question/89692 http://www.creativecommons.org/licenses/by-nc/2.5/rdf http://mathoverflow.net/questions/89692/if-graph-is-tree-what-can-be-said-about-its-adjacency-matrix If graph is tree what can be said about its adjacency matrix ? Alexander Chervov 2012-02-27T18:47:33Z 2012-06-24T22:52:48Z <p><strong>Question</strong> If graph is tree what can be said about its <a href="http://en.wikipedia.org/wiki/Adjacency_matrix" rel="nofollow">adjacency matrix</a> ? And vice versa ?</p> <p>Especially I am interested in case when graph is <a href="http://en.wikipedia.org/wiki/Bipartite_graph" rel="nofollow">bipartite graph</a>.</p> <p>Such graphs are related to error-correction codes (see e.g. <a href="http://mathoverflow.net/questions/89658/adjacency-matrices-of-graphs-as-parity-check-matrices-of-error-correcting-codes" rel="nofollow">http://mathoverflow.net/questions/89658/adjacency-matrices-of-graphs-as-parity-check-matrices-of-error-correcting-codes</a>). If they are trees <a href="http://en.wikipedia.org/wiki/Belief_propagation" rel="nofollow">belief propagation</a> is known to produce exact results.</p> http://mathoverflow.net/questions/89692/if-graph-is-tree-what-can-be-said-about-its-adjacency-matrix/98611#98611 Answer by Francesc Font-Clos for If graph is tree what can be said about its adjacency matrix ? Francesc Font-Clos 2012-06-01T22:36:18Z 2012-06-24T22:52:48Z <p>check the "matrix tree theorem"</p> <p>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. </p> http://mathoverflow.net/questions/89692/if-graph-is-tree-what-can-be-said-about-its-adjacency-matrix/98981#98981 Answer by tweetie-bird for If graph is tree what can be said about its adjacency matrix ? tweetie-bird 2012-06-06T19:42:11Z 2012-06-06T23:52:59Z <p>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$. </p> <p>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.)</p> <p>${\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. </p>