Matrix tree theorem

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 $i$th row of $L^-$ (respectively, $i$th 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 $i$th 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)