tag:blogger.com,1999:blog-6555947.post2269359728266668413..comments2014-01-12T10:46:48.153-07:00Comments on The Geomblog: Adjacency matrix of a tree..Suresh Venkatasubramanianhttps://plus.google.com/112165457714968997350noreply@blogger.comBlogger8125tag:blogger.com,1999:blog-6555947.post-60005347057690480472009-03-30T10:34:00.000-06:002009-03-30T10:34:00.000-06:00There are several things that can be checked algeb...There are several things that can be checked algebraically (reusing ideas from several other posts):<BR/><BR/>i) the number of edges, via the sum of entries of A.<BR/><BR/>For a tree it must be n-1.<BR/><BR/>ii) Connectedness.<BR/>A^k has a positive (i,j) entry iff there is a path from i to j with k edges, possibly going back and forth repeatedly and using the same edge several times.<BR/><BR/>A^n is not positive for a tree, as a tree is bipartite, and in <I>exactly</I> n steps you cannot reach every vertex j from every vertex i, only those in the same or the other bipartition class, according to the parity of n.<BR/><BR/>But for a tree, we have A^n+ A^(n-1) positive, or (I+A)^n positive.<BR/><BR/>iii) the number of spanning trees, as the determinant of the Laplacian matrix from which one row and column has been removed. (with appropriate sign if not the SAME row and column are removed), by the matrix-tree theorem.<BR/>For a tree this number is 1.<BR/><BR/><BR/>Condition (iii) is necessary and sufficient: a graph with exactly one spanning tree must be a tree.<BR/><BR/>Conditions (i)+(ii) are also necessary and sufficient:<BR/>a connected graph with n-1 edges is a tree.Günter Rotenoreply@blogger.comtag:blogger.com,1999:blog-6555947.post-9032085504517064732009-03-23T13:44:00.000-06:002009-03-23T13:44:00.000-06:00Mitch, trees will have multiple paths between pair...Mitch, trees will have multiple paths between pairs of nodes. They will have only one *simple* path, but your formula counts paths (i.e., it is wrong).Anonymousnoreply@blogger.comtag:blogger.com,1999:blog-6555947.post-69599117319274326212009-03-23T10:19:00.000-06:002009-03-23T10:19:00.000-06:00Suresh, trivial necessary conditions:1. the sum of...Suresh, trivial necessary conditions:<BR/><BR/>1. the sum of all elements must be 2(n-1) (twice the number of eddges)?<BR/>2. each row/column must sum >0<BR/><BR/>I need to refine this, but to borrow some theory from from graph reachability, I think we should have that 0 < b_{ij} <= n for all b_{ij}, where B=(A+A^2...+A^n)<BR/><BR/>For the loop case, the sum for some pair of nodes will be >n. I not sure this handles disjoint subgraphs.srnoreply@blogger.comtag:blogger.com,1999:blog-6555947.post-3430959032432500582009-03-23T10:12:00.000-06:002009-03-23T10:12:00.000-06:00tree = Exactly 1 path between each pair of nodes.A...tree = Exactly 1 path between each pair of nodes.<BR/><BR/>A^k_{i,j} = # of paths between i and j of length k.<BR/><BR/>I + A + A^2 + .. + A^{n-1} = J (the matrix of all 1's<BR/> = (1 - A^n)/(1 - A)<BR/><BR/>Is that what you're looking for?Mitchhttp://www.blogger.com/profile/06352106235527027461noreply@blogger.comtag:blogger.com,1999:blog-6555947.post-10778109352555107402009-03-23T07:58:00.000-06:002009-03-23T07:58:00.000-06:00can't you just invoke the matrix-tree theorem to c...can't you just invoke the matrix-tree theorem to count the number of spanning trees and check if it's equal to one?halhttp://www.blogger.com/profile/02162908373916390369noreply@blogger.comtag:blogger.com,1999:blog-6555947.post-22950788910085879732009-03-23T07:25:00.000-06:002009-03-23T07:25:00.000-06:00How about the sum of 1's being 2(n-1) and the n^th...How about the sum of 1's being 2(n-1) and the n^th power having strictly positive entries?deepcnoreply@blogger.comtag:blogger.com,1999:blog-6555947.post-21032188438344588502009-03-23T07:05:00.000-06:002009-03-23T07:05:00.000-06:00You might look at the linear algebra literature fo...You might look at the linear algebra literature for what types of matrices can be quickly inverted. I believe trees matrices have been identified as such a class and the related literature may hold a useful characterization. Sorry I can't give a more specific reference.<BR/><BR/>Jeff PJeffhttp://www.blogger.com/profile/02817986846758586086noreply@blogger.comtag:blogger.com,1999:blog-6555947.post-30241847073126822742009-03-23T04:16:00.000-06:002009-03-23T04:16:00.000-06:00There is an algebraic description in terms of the ...There is an algebraic description in terms of the Laplacian matrix, which is almost the same as the adjacency matrix except that the diagonal contains the negative vertex degree instead of 0 (see <A>Wikipedia</A>). The multiplicity of the eigenvalue 0 counts the connected components, and the trace of this matrix is -2 times the number of edges of the graph. So for a tree there must be n-1 nonzero eigenvalues and the trace must be 2n-2 where n is the number of vertices.Ulrich Bauerhttp://num.math.uni-goettingen.de/~bauer/noreply@blogger.com