Difference between revisions of "Matrix tree theorem"
(Importing text file) |
m (tex done) |
||
(5 intermediate revisions by 3 users not shown) | |||
Line 1: | Line 1: | ||
− | + | <!--This article has been texified automatically. Since there was no Nroff source code for this article, | |
+ | the semi-automatic procedure described at https://encyclopediaofmath.org/wiki/User:Maximilian_Janisch/latexlist | ||
+ | was used. | ||
+ | If the TeX and formula formatting is correct and if all png images have been replaced by TeX code, please remove this message and the {{TEX|semi-auto}} category. | ||
− | + | Out of 101 formulas, 100 were replaced by TEX code.--> | |
− | + | {{TEX|semi-auto}}{{TEX|done}} | |
+ | Let be a [[Graph|graph]] with \nu vertices $\{ v _ { 1 } , \dots , v _ { \nu } \}$ and \epsilon edges \{ e _ { 1 } , \dots , e _ { \epsilon } \}, some of which may be oriented. The incidence matrix of G is the ( \nu \times \epsilon )-matrix $M = [ m _ { i j } ]$ whose entries are given by $m _ { i j } = 1 if e_{j}$ is a non-oriented link (i.e. an edge that is not a loop) incident to v_i or if e_{j} is an oriented link with head v_i, $m _ { i j } = - 1 if e_{j}$ is an oriented link with tail v_i, m _ { i j } = 2 if e_{j} is a loop (necessarily non-oriented) at v_i, and $m _ { i j } = 0 otherwise. The mixed Laplacian matrix of G is defined as L = [ l _ {i j } ] = M M ^ { T }$. It is easy to see that the diagonal entries of L give the degrees of the vertices with, however, each loop contributing 4 to the count, and the off-diagonal entry l_{i j} gives the number of non-oriented edges joining v_i and v _ { j } minus the number of oriented edges joining them. Let \tau ( G ) denote the number of [[spanning tree]]s of G, with orientation ignored. | ||
− | + | The matrix tree theorem in its classical form, which is already implicit in the work of G. Kirchhoff [[#References|[a9]]], states that if L is the Laplacian of any orientation of a loopless undirected graph G and L ^ { * } is the matrix obtained by deleting any row s and column t of L, then \tau ( G ) = ( - 1 ) ^ { s + t } \operatorname { det } ( L ^ { * } ); that is, each [[Cofactor|cofactor]] of L is equal to the tree-number of G. If \operatorname{adj}( L ) denotes the adjoint of the matrix L and J denotes the matrix with all entries equal to 1, then $\operatorname { adj } ( L ) = \tau ( G ) J. The proof of this theorem uses the Binet–Cauchy theorem to expand the cofactor of L together with the fact that every non-singular ( \nu - 1 ) \times ( \nu - 1 )-minor of M (cf. also [[Minor|Minor]]) comes from a spanning tree of G having value \pm 1. In the case of the complete graph K _ { \nu } (with some orientation), L = \nu I - J, and it can be seen that \tau ( K _ { \nu } ) = \nu ^ { \nu - 2 }, which is Cayley's formula for the number of labelled trees on \nu$ vertices [[#References|[a4]]]. Temperley's result [[#References|[a3]]], Prop. 6.4, avoids using the cofactor notation in the following form: \nu ^ { 2 } \tau ( G ) = \operatorname { det } ( J + L ). It is interesting to note that this determinantal way of computing \tau ( G ) requires \nu ^ { 3 } operations rather than the 2 ^ { \nu } operations when using recursion [[#References|[a17]]], p. 66. | |
+ | |||
+ | For a loopless directed graph G, let $L ^ { - } = D ^ { - } - A ^ { \prime } and L ^ { + } = D ^ { + } - A ^ { \prime }, where D ^ { - } and D ^ { + } are the diagonal matrices of in-degrees and out-degrees in G, and the i j-entry of A ^ { \prime } is the number of edges from v _ { j } to v_i. An out-tree is an orientation of a tree having a root of in-degree 0 and all other vertices of in-degree 1$. An in-tree is an out-tree with its edges reversed. W.T. Tutte [[#References|[a16]]] extended the matrix tree theorem by showing that the number of out-trees (respectively, in-trees) rooted at v_i is the value of any cofactor in the ith row of L^- (respectively, ith column of L ^ { + }). In fact, the principal minor of L obtained by deleting rows and columns indexed by v _ { i_1 } , \dots , v _ { i_k } equals the number of spanning forests of G having precisely k out-trees rooted at v _ { i_1 } , \dots , v _ { i_k }. | ||
+ | |||
+ | In all the approaches it is clear that the significant property of the Laplacian L is that \sum _ { j } l _ { ij } = 0 for 1 \leq i \leq \nu. By allowing l_{i j} to be indeterminates over the field of rational numbers, the generating function version of the matrix tree theorem is obtained [[#References|[a8]]], Sect. 3.3.25: The number of trees rooted at r on the vertex set \{ 1 , \dots , \nu \}, with m_{ij} occurrences of the edge \overset{\rightharpoonup} { i j } (directed away from the root), is the coefficient of the monomial $\prod _ { i , j } l _ { i j } ^ { m _ { i j } }$ in the ( r , r )th cofactor of the matrix [ \delta _ { i j } \alpha _ { i } - l_{i j} ] _ { \nu \times \nu }, where $m _ { i j } \in \{ 0,1 \}$ and \alpha_i is the sum of the entries in the ith row of L, for $i = 1 , \dots , \nu$. | ||
Several related identities can be found in work by J.W. Moon on labelled trees [[#References|[a13]]]. For various proofs of Cayley's formula, see [[#References|[a14]]]. | Several related identities can be found in work by J.W. Moon on labelled trees [[#References|[a13]]]. For various proofs of Cayley's formula, see [[#References|[a14]]]. | ||
Line 11: | Line 19: | ||
Another direction of generalization is to interpret all the minors of the Laplacian rather than just the principal ones. Such generalizations can be found in [[#References|[a5]]] and [[#References|[a2]]], where arbitrary minors are expressed as signed sums over non-singular substructures that are more complicated than trees. | Another direction of generalization is to interpret all the minors of the Laplacian rather than just the principal ones. Such generalizations can be found in [[#References|[a5]]] and [[#References|[a2]]], where arbitrary minors are expressed as signed sums over non-singular substructures that are more complicated than trees. | ||
− | The edge version of the Laplacian is defined to be the | + | The edge version of the Laplacian is defined to be the ( \epsilon \times \epsilon )-matrix $K = M ^ { T } M$. The connection of its cofactors with the Wiener index in applications to chemistry is presented in [[#References|[a11]]]. The combinatorial description of the arbitrary minors of K when G is a tree is studied in [[#References|[a1]]]. |
− | Applications are widespread. Variants of the matrix tree theorem are used in the topological analysis of passive electrical networks. The node-admittance matrix considered for this purpose is closely related to the Laplacian matrix (see [[#References|[a10]]], Chap. 7). Abundance of forests suggests greater accessibility in networks. Due to this connection, the matrix tree theorem is used in developing distance concepts in social networks (see [[#References|[a6]]]). The | + | Applications are widespread. Variants of the matrix tree theorem are used in the topological analysis of passive electrical networks. The node-admittance matrix considered for this purpose is closely related to the Laplacian matrix (see [[#References|[a10]]], Chap. 7). Abundance of forests suggests greater accessibility in networks. Due to this connection, the matrix tree theorem is used in developing distance concepts in social networks (see [[#References|[a6]]]). The C-matrix which occurs in the design of statistical experiments (cf. also [[Design of experiments|Design of experiments]]) is the Laplacian of a graph associated with the design. In this context the matrix tree theorem is used to study D-optimal designs (see [[#References|[a7]]], p. 67). Finally, the matrix tree theorem is closely related to the [[Perron–Frobenius theorem|Perron–Frobenius theorem]]. If A is the transition matrix of an irreducible [[Markov chain|Markov chain]], then by the Perron–Frobenius theorem it admits a unique stationary distribution. This fact is easily deduced from the matrix tree theorem, which in fact gives an interpretation of the components of the stationary distribution in terms of tree-counts. This observation is used to approximate the stationary distribution of a countable Markov chain (see [[#References|[a15]]], p. 222). |
An excellent survey of interesting developments related to Laplacians may be found in [[#References|[a12]]]. | An excellent survey of interesting developments related to Laplacians may be found in [[#References|[a12]]]. | ||
====References==== | ====References==== | ||
− | <table>< | + | <table><tr><td valign="top">[a1]</td> <td valign="top"> R.B. Bapat, J.W. Grossman, D.M. Kulkarni, "Edge version of the matrix tree theorem for trees" ''Linear and Multilinear Algebra'' , '''47''' (2000) pp. 217–229</td></tr><tr><td valign="top">[a2]</td> <td valign="top"> R.B. Bapat, J.W. Grossman, D.M. Kulkarni, "Generalized matrix tree theorem for mixed graphs" ''Linear and Multilinear Algebra'' , '''46''' (1999) pp. 299–312</td></tr><tr><td valign="top">[a3]</td> <td valign="top"> N. Biggs, "Algebraic graph theory" , Cambridge Univ. Press (1993) (Edition: Second)</td></tr><tr><td valign="top">[a4]</td> <td valign="top"> A. Cayley, "A theorem on trees" ''Quart. J. Math.'' , '''23''' (1889) pp. 376–378</td></tr><tr><td valign="top">[a5]</td> <td valign="top"> S. Chaiken, "A combinatorial proof of the all minors matrix tree theorem" ''SIAM J. Algebraic Discr. Math.'' , '''3''' : 3 (1982) pp. 319–329</td></tr><tr><td valign="top">[a6]</td> <td valign="top"> P.Yu. Chebotarev, E.V. Shamis, "The matrix-forest theorem and measuring relations in small social groups" ''Automat. Remote Control'' , '''58''' : 9:2 (1997) pp. 1505–1514</td></tr><tr><td valign="top">[a7]</td> <td valign="top"> G.M. Constantine, "Combinatorial theory and statistical design" , Wiley (1987)</td></tr><tr><td valign="top">[a8]</td> <td valign="top"> I.P. Goulden, D.M. Jackson, "Combinatorial enumeration" , Wiley (1983)</td></tr><tr><td valign="top">[a9]</td> <td valign="top"> G. Kirchhoff, "Über die Auflösung der Gleichungen, auf welche man bei der Untersuchung der linearen Verteilung galvanischer Ströme geführt wird" ''Ann. Phys. Chem.'' , '''72''' (1847) pp. 497–508</td></tr><tr><td valign="top">[a10]</td> <td valign="top"> W. Mayeda, "Graph theory" , Wiley (1972)</td></tr><tr><td valign="top">[a11]</td> <td valign="top"> R. Merris, "An edge version of the matrix-tree theorem and the Wiener index" ''Linear and Multilinear Algebra'' , '''25''' (1989) pp. 291–296</td></tr><tr><td valign="top">[a12]</td> <td valign="top"> R. Merris, "Laplacian matrices of graphs: a survey" ''Linear Alg. & Its Appl.'' , '''197/198''' (1994) pp. 143–176</td></tr><tr><td valign="top">[a13]</td> <td valign="top"> J.W. Moon, "Counting labeled trees" , ''Canad. Math. Monographs'' , '''1''' , Canad. Math. Congress (1970)</td></tr><tr><td valign="top">[a14]</td> <td valign="top"> J.W. Moon, "Various proofs of Cayley's formula for counting trees" F. Harary (ed.) , ''A Seminar on Graph Theory'' , Holt, Rinehart & Winston (1967) pp. 70–78</td></tr><tr><td valign="top">[a15]</td> <td valign="top"> E. Seneta, "Non-negative matrices and Markov chains" , Springer (1981) (Edition: Second)</td></tr><tr><td valign="top">[a16]</td> <td valign="top"> W.T. Tutte, "The disection of equilateral triangles into equilateral triangles" ''Proc. Cambridge Philos. Soc.'' , '''44''' (1948) pp. 463–482</td></tr><tr><td valign="top">[a17]</td> <td valign="top"> D.B. West, "Introduction to graph theory" , Prentice-Hall (1996)</td></tr></table> |
+ | |||
+ | [[Category:Graph theory]] |
Latest revision as of 08:14, 15 February 2024
Let G = ( V , E ) be a graph with \nu vertices \{ v _ { 1 } , \dots , v _ { \nu } \} and \epsilon edges \{ e _ { 1 } , \dots , e _ { \epsilon } \}, some of which may be oriented. The incidence matrix of G is the ( \nu \times \epsilon )-matrix M = [ m _ { i j } ] whose entries are given by m _ { i j } = 1 if e_{j} is a non-oriented link (i.e. an edge that is not a loop) incident to v_i or if e_{j} is an oriented link with head v_i, m _ { i j } = - 1 if e_{j} is an oriented link with tail v_i, m _ { i j } = 2 if e_{j} is a loop (necessarily non-oriented) at v_i, and m _ { i j } = 0 otherwise. The mixed Laplacian matrix of G is defined as L = [ l _ {i j } ] = M M ^ { T }. It is easy to see that the diagonal entries of L give the degrees of the vertices with, however, each loop contributing 4 to the count, and the off-diagonal entry l_{i j} gives the number of non-oriented edges joining v_i and v _ { j } minus the number of oriented edges joining them. Let \tau ( G ) denote the number of spanning trees of G, with orientation ignored.
The matrix tree theorem in its classical form, which is already implicit in the work of G. Kirchhoff [a9], states that if L is the Laplacian of any orientation of a loopless undirected graph G and L ^ { * } is the matrix obtained by deleting any row s and column t of L, then \tau ( G ) = ( - 1 ) ^ { s + t } \operatorname { det } ( L ^ { * } ); that is, each cofactor of L is equal to the tree-number of G. If \operatorname{adj}( L ) denotes the adjoint of the matrix L and J denotes the matrix with all entries equal to 1, then \operatorname { adj } ( L ) = \tau ( G ) J. The proof of this theorem uses the Binet–Cauchy theorem to expand the cofactor of L together with the fact that every non-singular ( \nu - 1 ) \times ( \nu - 1 )-minor of M (cf. also Minor) comes from a spanning tree of G having value \pm 1. In the case of the complete graph K _ { \nu } (with some orientation), L = \nu I - J, and it can be seen that \tau ( K _ { \nu } ) = \nu ^ { \nu - 2 }, which is Cayley's formula for the number of labelled trees on \nu vertices [a4]. Temperley's result [a3], Prop. 6.4, avoids using the cofactor notation in the following form: \nu ^ { 2 } \tau ( G ) = \operatorname { det } ( J + L ). It is interesting to note that this determinantal way of computing \tau ( G ) requires \nu ^ { 3 } operations rather than the 2 ^ { \nu } operations when using recursion [a17], p. 66.
For a loopless directed graph G, let L ^ { - } = D ^ { - } - A ^ { \prime } and L ^ { + } = D ^ { + } - A ^ { \prime }, where D ^ { - } and D ^ { + } are the diagonal matrices of in-degrees and out-degrees in G, and the i j-entry of A ^ { \prime } is the number of edges from v _ { j } to v_i. An out-tree is an orientation of a tree having a root of in-degree 0 and all other vertices of in-degree 1. An in-tree is an out-tree with its edges reversed. W.T. Tutte [a16] extended the matrix tree theorem by showing that the number of out-trees (respectively, in-trees) rooted at v_i is the value of any cofactor in the ith row of L^- (respectively, ith column of L ^ { + }). In fact, the principal minor of L obtained by deleting rows and columns indexed by v _ { i_1 } , \dots , v _ { i_k } equals the number of spanning forests of G having precisely k out-trees rooted at v _ { i_1 } , \dots , v _ { i_k }.
In all the approaches it is clear that the significant property of the Laplacian L is that \sum _ { j } l _ { ij } = 0 for 1 \leq i \leq \nu. By allowing l_{i j} to be indeterminates over the field of rational numbers, the generating function version of the matrix tree theorem is obtained [a8], Sect. 3.3.25: The number of trees rooted at r on the vertex set \{ 1 , \dots , \nu \}, with m_{ij} occurrences of the edge \overset{\rightharpoonup} { i j } (directed away from the root), is the coefficient of the monomial \prod _ { i , j } l _ { i j } ^ { m _ { i j } } in the ( r , r )th cofactor of the matrix [ \delta _ { i j } \alpha _ { i } - l_{i j} ] _ { \nu \times \nu }, where m _ { i j } \in \{ 0,1 \} and \alpha_i is the sum of the entries in the ith row of L, for i = 1 , \dots , \nu.
Several related identities can be found in work by J.W. Moon on labelled trees [a13]. For various proofs of Cayley's formula, see [a14].
Another direction of generalization is to interpret all the minors of the Laplacian rather than just the principal ones. Such generalizations can be found in [a5] and [a2], where arbitrary minors are expressed as signed sums over non-singular substructures that are more complicated than trees.
The edge version of the Laplacian is defined to be the ( \epsilon \times \epsilon )-matrix K = M ^ { T } M. The connection of its cofactors with the Wiener index in applications to chemistry is presented in [a11]. The combinatorial description of the arbitrary minors of K when G is a tree is studied in [a1].
Applications are widespread. Variants of the matrix tree theorem are used in the topological analysis of passive electrical networks. The node-admittance matrix considered for this purpose is closely related to the Laplacian matrix (see [a10], Chap. 7). Abundance of forests suggests greater accessibility in networks. Due to this connection, the matrix tree theorem is used in developing distance concepts in social networks (see [a6]). The C-matrix which occurs in the design of statistical experiments (cf. also Design of experiments) is the Laplacian of a graph associated with the design. In this context the matrix tree theorem is used to study D-optimal designs (see [a7], p. 67). Finally, the matrix tree theorem is closely related to the Perron–Frobenius theorem. If A is the transition matrix of an irreducible Markov chain, then by the Perron–Frobenius theorem it admits a unique stationary distribution. This fact is easily deduced from the matrix tree theorem, which in fact gives an interpretation of the components of the stationary distribution in terms of tree-counts. This observation is used to approximate the stationary distribution of a countable Markov chain (see [a15], p. 222).
An excellent survey of interesting developments related to Laplacians may be found in [a12].
References
[a1] | R.B. Bapat, J.W. Grossman, D.M. Kulkarni, "Edge version of the matrix tree theorem for trees" Linear and Multilinear Algebra , 47 (2000) pp. 217–229 |
[a2] | R.B. Bapat, J.W. Grossman, D.M. Kulkarni, "Generalized matrix tree theorem for mixed graphs" Linear and Multilinear Algebra , 46 (1999) pp. 299–312 |
[a3] | N. Biggs, "Algebraic graph theory" , Cambridge Univ. Press (1993) (Edition: Second) |
[a4] | A. Cayley, "A theorem on trees" Quart. J. Math. , 23 (1889) pp. 376–378 |
[a5] | S. Chaiken, "A combinatorial proof of the all minors matrix tree theorem" SIAM J. Algebraic Discr. Math. , 3 : 3 (1982) pp. 319–329 |
[a6] | P.Yu. Chebotarev, E.V. Shamis, "The matrix-forest theorem and measuring relations in small social groups" Automat. Remote Control , 58 : 9:2 (1997) pp. 1505–1514 |
[a7] | G.M. Constantine, "Combinatorial theory and statistical design" , Wiley (1987) |
[a8] | I.P. Goulden, D.M. Jackson, "Combinatorial enumeration" , Wiley (1983) |
[a9] | G. Kirchhoff, "Über die Auflösung der Gleichungen, auf welche man bei der Untersuchung der linearen Verteilung galvanischer Ströme geführt wird" Ann. Phys. Chem. , 72 (1847) pp. 497–508 |
[a10] | W. Mayeda, "Graph theory" , Wiley (1972) |
[a11] | R. Merris, "An edge version of the matrix-tree theorem and the Wiener index" Linear and Multilinear Algebra , 25 (1989) pp. 291–296 |
[a12] | R. Merris, "Laplacian matrices of graphs: a survey" Linear Alg. & Its Appl. , 197/198 (1994) pp. 143–176 |
[a13] | J.W. Moon, "Counting labeled trees" , Canad. Math. Monographs , 1 , Canad. Math. Congress (1970) |
[a14] | J.W. Moon, "Various proofs of Cayley's formula for counting trees" F. Harary (ed.) , A Seminar on Graph Theory , Holt, Rinehart & Winston (1967) pp. 70–78 |
[a15] | E. Seneta, "Non-negative matrices and Markov chains" , Springer (1981) (Edition: Second) |
[a16] | W.T. Tutte, "The disection of equilateral triangles into equilateral triangles" Proc. Cambridge Philos. Soc. , 44 (1948) pp. 463–482 |
[a17] | D.B. West, "Introduction to graph theory" , Prentice-Hall (1996) |
Matrix tree theorem. Encyclopedia of Mathematics. URL: http://encyclopediaofmath.org/index.php?title=Matrix_tree_theorem&oldid=14639