The Matrix-Tree Theorem

THE MATRIX-TREE THEOREM 1 The Matrix-Tree Theorem. The Matrix-Tree Theorem is a formula for the number of spanning trees of a graph in terms of the determinant of a certain matrix. We begin with the necessary graph-theoretical background. Let G be a finite graph, allowing multiple edges but not loops. (Loops could be allowed, but they turn out to be completely irrelevant.) We say that G is connected if there exists a walk between any two vertices of G. A cycle is a closed walk with no repeated vertices or edges, except for the the first and last vertex. A tree is a connected graph with no cycles. In particular, a tree cannot have multiple edges, since a double edge is equivalent to a cycle of length two. The three nonisomorphic trees with five vertices are given by: r r r r r r r r r @ @@r r r @ @ @r @ @ r @r A basic theorem of graph theory (whose easy proof we leave as an exercise) is the following. 1.1 Proposition. Let G be a graph with p vertices. The following conditions are equivalent. (a) G is a tree. (b) G is connected and has p − 1 edges. (c) G is has no cycles and has p − 1 edges. (d) There is a unique path (= walk with no repeated vertices) between any two vertices. 1 A spanning subgraph of a graph G is a graph H with the same vertex set as G, and such that every edge of H is an edge of G. If G has q edges, then the number of spanning subgraphs of G is equal to 2q , since we can choose any subset of the edges of G to be the set of edges of H. (Note that multiple edges between the same two vertices are regarded as distinguishable.) A spanning subgraph which is a tree is called a spanning tree. Clearly G has a spanning tree if and only if it is connected [why?]. An important invariant of a graph G is its number of spanning trees, called the complexity of G and denoted κ(G). 1.2 Example. c, d, e. Let G be the graph illustrated below, with edges a, b, r @ @ a r b r c @e @ @ @r d Then G has eight spanning trees, namely, abc, abd, acd, bcd, abe, ace, bde, and cde (where, e.g., abc denotes the spanning subgraph with edge set {a, b, c}). 1.3 Example. Let G = K5 , the complete graph on five vertices. A simple counting argument shows that K5 has 60 spanning trees isomorphic to the first tree in the above illustration of all nonisomorphic trees with five vertices, 60 isomorphic to the second tree, and 5 isomorphic to the third tree. Hence κ(K5 ) = 125. It is even easier to verify that κ(K1 ) = 1, κ(K2 ) = 1, κ(K3 ) = 3, and κ(K4 ) = 16. Can the reader make a conjecture about the value of κ(Kp ) for any p ≥ 1? Our object is to obtain a “determinantal formula” for κ(G). For this we need an important result from matrix theory which is often omitted from a beginning linear algebra course. This result, known as the Binet-Cauchy theorem (or sometimes as the Cauchy-Binet theorem), is a generalization of the familiar fact that if A and B are n × n matrices, then det(AB) = 2 det(A) det(B) (where det denotes determinant)1. We want to extend this formula to the case where A and B are rectangular matrices whose product is a square matrix (so that det(AB) is defined). In other words, A will be an m × n matrix and B an n × m matrix, for some m, n ≥ 1. We will use the following notation involving submatrices. Suppose A = (aij ) is an m × n matrix, with 1 ≤ i ≤ m, 1 ≤ j ≤ n, and m ≤ n. Given an m-element subset S of {1, 2, . . . , n}, let A[S] denote the m×m submatrix of A obtained by taking the columns indexed by the elements of S. In other words, if the elements of S are given by j1 < j2 < · · · < jm , then A[S] = (ai,jk ), where 1 ≤ i ≤ m and 1 ≤ k ≤ m. For instance, if   1 2 3 4 5 A =  6 7 8 9 10  11 12 13 14 15 and S = {2, 3, 5}, then   2 3 5 A[S] =  7 8 10  . 12 13 15 Similarly, let B = (bij ) be an n × m matrix with 1 ≤ i ≤ n, 1 ≤ j ≤ m and m ≤ n. Let S be an m-element subset of {1, 2, . . . , n} as above. Then B[S] denotes the m × m matrix obtained by taking the rows of B indexed by S. Note that At [S] = A[S]t , where t denotes transpose. 1.4 Theorem. (the Binet-Cauchy Theorem) Let A = (aij ) be an m × n matrix, with 1 ≤ i ≤ m and 1 ≤ j ≤ n. Let B = (bij ) be an n × m matrix with 1 ≤ i ≤ n and 1 ≤ j ≤ m. (Thus AB is an m × m matrix.) If m > n, then det(AB) = 0. If m ≤ n, then X det(AB) = (det A[S])(det B[S]), S 1 In the “additional material” handout (Theorem 2.4) there is a more general determinantal formula without the use of the Binet-Cauchy theorem. However, the use of the Binet-Cauchy theorem does afford some additional algebraic insight. 3 where S ranges over all m-element subsets of {1, 2, . . . , n}. Before proceeding to the proof, let us give an example. We write |aij | for the determinant of the matrix (aij ). Suppose     c1 d 1 a1 a2 a3 A= , B =  c2 d 2  . b1 b2 b3 c3 d 3 Then det(AB ) = a1 a2 c d a a c d a a c d · 1 1 + 1 3 · 1 1 + 2 3 · 2 2 . b1 b2 c2 d 2 b1 b3 c3 d 3 b2 b3 c3 d 3 Proof of Theorem 1.4 (sketch). First suppose m > n. Since from linear algebra we know that rank(AB) ≤ rank(A) and that the rank of an m × n matrix cannot exceed n (or m), we have that rank(AB) ≤ n < m. But AB is an m × m matrix, so det(AB) = 0, as claimed. Now assume m ≤ n. We use notation such as Mrs to denote an r × s matrix M. It is an immediate consequence of the definition of matrix multiplication (which the reader should check) that      Rmm Smn Vmn Wmm RV + SX RW + SY = . (1) Tnm Unn Xnn Ynm T V + UX T W + UY In other words, we can multiply “block” matrices of suitable dimensions as if their entries were numbers. Note that the entries of the right-hand side of (1) all have well-defined dimensions (sizes), e.g., RV + SX is an m × n matrix since both RV and SX are m × n matrices. Now in equation (1) let R = Im (the m × m identity matrix), S = A, T = Onm (the n × m matrix of 0’s), U = In , V = A, W = Omm , X = −In , and Y = B. We get      Im A A Omm Omn AB = . (2) Onm In −In B −In B Take the determinant of both sides of (2). The first matrix on the left-hand side is an upper triangular matrix with 1’s on the main diagonal. Hence its 4 determinant is one. Since the determinant of a product of square matrices is the product of the determinants of the factors, we get A Omm −In B = Omn AB . −In B (3 ) It is easy to see [why?] that the determinant on the right-hand side of (3) is equal to ± det(AB). So consider the left-hand side. A nonzero term in the expansion of the determinant on the left-hand side is obtained by taking the product (with a certain sign) of m + n nonzero entries, no two in the same row and column (so one in each row and each column). In particular, we must choose m entries from the last m columns. These entries belong to m of the bottom n rows [why?], say rows m + s1 , m + s2 , . . . , m + sm . Let S = {s1 , s2 , . . . , sm } ⊆ {1, 2, . . . , n}. We must choose n − m further entries from the last n rows, and we have no choice but to choose the −1’s in those rows m+i for which i 6∈ S. Thus every term in the expansion of the left-hand side of (3) uses exactly n − m of the −1’s in the bottom left block −In . What is the contribution to the expansion of the left-hand side of (3) from those terms which use exactly the −1’s from rows m + i where i 6∈ S? We obtain this contribution by deleting all rows and columns to which these −1’s belong (in other words, delete row m + i and column i whenever i ∈ {1, 2, . . . , n} − S), taking the determinant of the 2m × 2m matrix MS that remains, and multiplying by an appropriate sign [why?]. But the matrix MS is in block-diagonal form, with the first block just the matrix A[S] and the second block just B[S]. Hence det MS = (det A[S])(det B[S]) [why?]. Taking all possible subsets S gives X det AB = ±(det A[S])(det B[S]). S⊆{1,2,...,n} |S|=m It is straightforward but somewhat tedious to verify that all the signs are +; we omit the details. This completes the proof. 2 Let G be a graph with vertices v1 , . . . , vp . The adjacency matrix of G is the p × p matrix A = A(G), over the field of complex numbers, whose (i, j)-entry aij is equal to the number of edges incident to vi and vj . Thus 5 A is a real symmetric matrix (and hence has real eigenvalues) whose trace is the number of loops in G. We now define two matrices related to A(G). Assume for simplicity that G has no loops. (This assumption is harmless since loops have no effect on κ(G).) 1.5 Definition. Let G be as above. Give G an orientation o, i.e, for every edge e with vertices u, v, choose one of the ordered pairs (u, v) or (v, u). (If we choose (u, v), say, then we think of putting an arrow on e pointing from u to v; and we say that e is directed from u to v, that u is the initial vertex and v the final vertex of e, etc.) (a) The incidence matrix M (G) of G (with respect to the orientation o) is the p × q matrix whose (i, j)-entry M ij is given by  if the edge ej has initial vertex vi  1, −1, if the edge ej has final vertex vi M ij =  0, otherwise. (b) The laplacian matrix L(G) of G is the p × p matrix whose (i, j)-entry Lij is given by  −mij , if i 6= j and there are mij edges between vi and vj Lij = deg(vi ), if i = j, where deg(vi ) is the number of edges incident to vi . (Thus L(G) is symmetric and does not depend on the orientation o.) Note that every column of M (G) contains one 1, one −1, and q − 2 0’s; and hence the sum of the entries in each column is 0. Thus all the rows sum to the 0 vector, a linear dependence relation which shows that rank(M (G)) < p. Two further properties of M (G) and L(G) are given by the following lemma. 1.6 Lemma. (a) We have M M t = L. (b) If G is regular of degree d (i.e., every vertex of G has degree d), then L(G) = dI − A(G), where A(G) denotes the adjacency matrix of G. 6 Hence if G (or A(G)) has eigenvalues λ1 , . . . , λp , then L(G) has eigenvalues d − λ1 , . . . , d − λp . Proof. (a) This is immediate from the definition of matrix multiplication. Specifically, for vi , vj ∈ V (G) we have X (M M t )ij = M ik M jk . ek ∈E(G) If i 6= j, then in order for M ik Mjk 6= 0, we must have that the edge ek connects the vertices vi and vj . If this is the case, then one of M ik and Mjk will be 1 and the other −1 [why?], so their product is always −1. Hence (M M t )ij = −mij , as claimed. There remains the case i = j. Then M ik M ik will be 1 if ek is an edge with vi as one of its vertices and will be 0 otherwise [why?]. So now we get (M M t )ii = deg(vi ), as claimed. This proves (a). (b) Clear by (a), since the diagonal elements of M M t are all equal to d. 2 Now assume that G is connected, and let M 0 (G) be M (G) with its last row removed. Thus M 0 (G) has p − 1 rows and q columns. Note that the number of rows is equal to the number of edges in a spanning tree of G. We call M 0 (G) the reduced incidence matrix of G. The next result tells us the determinants (up to sign) of all (p − 1) × (p − 1) submatrices N of M 0 . Such submatrices are obtained by choosing a set S of p − 1 edges of G, and taking all columns of M 0 indexed by the edges in S. Thus this submatrix is just M 0 [S]. 1.7 Lemma. Let S be a set of p − 1 edges of G. If S does not form the set of edges of a spanning tree, then det M 0 [S] = 0. If, on the other hand, S is the set of edges of a spanning tree of G, then det M 0 [S] = ±1. Proof. If S is not the set of edges of a spanning tree, then some subset R of S forms the edges of a cycle C in G. Consider the submatrix M 0 [R] of M 0 [S] obtained by taking the columns indexed by edges in R. Suppose that the cycle C defined by R has edges f1 , . . . , fs in that order. Multiply the column of M 0 [R] indexed by fj by 1 if in going around C we traverse 7 fi in the direction of its arrow; otherwise multiply the column by −1. These column multiplications will multiply the determinant of M 0 [R] by ±1. It is easy to see (check a few small examples to convince yourself) that every row of this modified M 0 [R] has the sum of its elements equal to 0. Hence the sum of all the columns is 0. Thus in M 0 [S] we have a set of columns for which a linear combination with coefficients ±1 is 0 (the column vector of all 0’s). Hence the columns of M 0 [S] are linearly dependent, so det M 0 [S] = 0, as claimed. Now suppose that S is the set of edges of a spanning tree T . Let e be an edge of T which is connected to vp (the vertex which indexed the bottom row of M , i.e., the row removed to get M 0 ). The column of M 0 [S] indexed by e contains exactly one nonzero entry [why?], which is ±1. Remove from M 0 [S] the row and column containing the nonzero entry of column e, obtaining a (p−2)×(p−2) matrix M ′0 . Note that det(M 0 [S]) = ± det(M ′0 ) [why?]. Let T ′ be the tree obtained from T by contracting the edge e to a single vertex (so that vp and the remaining vertex of e are merged into a single vertex u). Then M ′0 is just the matrix obtained from the incidence matrix M (T ′ ) by removing the row indexed by u [why?]. Hence by induction on the number p of vertices (the case p = 1 being trivial), we have det(M ′0 ) = ±1. Thus det(M 0 [S]) = ±1, and the proof follows. 2 We have now assembled all the ingredients for the main result of this section (due originally to Borchardt). Recall that κ(G) denotes the number of spanning trees of G. 1.8 Theorem. (the Matrix-Tree Theorem) Let G be a finite connected graph without loops, with laplacian matrix L = L(G). Let L0 denote L with the last row and column removed (or with the ith row and column removed for any i). Then det(L0 ) = κ(G). Proof. Since L = M M t (Lemma 1.6(a)), it follows immediately that L0 = M 0 M t0 . Hence by the Binet-Cauchy theorem (Theorem 1.4), we have X det(L0 ) = (det M 0 [S])(det M t0 [S]), (4) S where S ranges over all (p−1)-element subsets of {1, 2 . . . , q} (or equivalently, over all (p − 1)-element subsets of the set of edges of G). Since in general 8 At [S] = A[S]t , equation (4) becomes X det(L0 ) = (det M 0 [S])2 . (5) S According to Lemma 1.7, det(M 0 [S]) is ±1 if S forms the set of edges of a spanning tree of G, and is 0 otherwise. Therefore the term indexed by S in the sum on the right-hand side of (5) is 1 if S forms the set of edges of a spanning tree of G, and is 0 otherwise. Hence the sum is equal to κ(G), as desired. 2 The operation of removing a row and column from L(G) may seem somewhat contrived. We would prefer a description of κ(G) directly in terms of L(G). Such a description will follow from the next lemma. 1.9 Lemma. Let M be a p×p matrix with real entries such that the sum of the entries in every row and column is 0. Let M0 be the matrix obtained from M by removing the last row and last column (or more generally, any row and any column). Then the coefficient of x in the characteristic polynomial det(M − xI) of M is equal to −p · det(M0 ). (Moreover, the constant term of det(M − xI) is 0.) Proof. The constant term of det(M − xI) is det(M), which is 0 since the rows of M sum to 0. For simplicity we prove the rest of the lemma only for removing the last row and column, though the proof works just as well for any row and column. Add all the rows of M − xI except the last row to the last row. This doesn’t effect the determinant, and will change the entries of the last row all to −x (since the rows of M sum to 0). Factor out −x from the last row, yielding a matrix N(x) satisfying det(M −xI) = −x det(N(x)). Hence the coefficient of x in det(M − xI) is given by − det(N(0)). Now add all the columns of N(0) except the last column to the last column. This does not effect det(N (0)). Because the columns of M sum to 0, the last column of N(0) becomes the column vector [0, 0, . . . , 0, p]t . Expanding the determinant by the last column shows that det(N(0)) = p · det(M0 ), and the proof follows. 2 1.10 Corollary. (a) Let G be a connected (loopless) graph with p vertices. Suppose that the eigenvalues of L(G) are µ1 , . . . , µp−1, µp , with µp = 9 0. Then 1 κ(G) = µ1 µ2 · · · µp−1 . p (b) Suppose that G is also regular of degree d, and that the eigenvalues of A(G) are λ1 , . . . , λp−1, λp , with λp = d. Then 1 κ(G) = (d − λ1 )(d − λ2 ) · · · (d − λp−1 ). p Proof. (a) We have det(L − xI) = (µ1 − x) · · · (µp−1 − x)(µp − x) = −(µ1 − x)(µ2 − x) · · · (µp−1 − x)x. Hence the coefficient of x is −µ1 µ2 · · · µp−1 . By Lemma 1.9, we get −µ1 µ2 · · · µp−1 = p · det(L0 ). By Theorem 1.8 we have det(L0 ) = κ(G), and the proof follows. (b) Immediate from (a) and Lemma 1.6(b). 2 Let us look at a couple of examples of the use of the Matrix-Tree Theorem. 1.11 Example. Let G = Kp , the complete graph on p vertices. Now Kp is regular of degree d = p − 1, and A(Kp ) + I = J, the p × p matrix of all 1’s. Note that rank(J) = 1 [why?], so p − 1 eigenvalues of J are equal to 0. Since trace(J) = p and the sum of the eigenvalues equals the trace, the remaining eigenvalue of J is p. Thus the eigenvalues of A(Kp ) = J −I are −1 (p−1 times) and p−1 (once).Hence from Corollary 1.10 there follows 1 κ(Kp ) = ((p − 1) − (−1))p−1 = pp−2 . p This surprising result is often attributed to Cayley, who stated it without proof in 1889 (and even cited Borchardt explicitly). However, it was in fact stated by Sylvester in 1857, while a proof was published by Borchardt in 1860. It is clear that Cayley and Sylvester could have produced a proof 10 if asked to do so. There are many other proofs known, including elegant combinatorial arguments due to Prüfer, Joyal, Pitman, and others. 1.12 Example. The n-cube Cn is the graph with vertex set Zn2 (the set of all n-tuples of 0’s and 1’s), and two vertices u and v are connected by an edge if they differ in exactly one component. Now Cn is regular of degree
n, n and it can be shown that its eigenvalues are n − 2i with multiplicity i for 0 ≤ i ≤ n. (See the solution to Exercise 10.18(d) of the text.) Hence from Corollary 1.10(b) there follows the amazing result n n 1 Y κ(Cn ) = n (2i)( i ) 2 i=1 = 2 2n −n−1 n Y n i( i ) . i=1 To my knowledge a direct combinatorial proof is not known. 11