View source for Matrix tree theorem

<!--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, please remove this message and the {{TEX|semi-auto}} category.

Out of 101 formulas, 100 were replaced by TEX code.-->

{{TEX|semi-auto}}{{TEX|partial}}
Let $G = ( V , E )$ be a [[Graph|graph]] with $\nu$ vertices $\{ v _ { 1 } , \dots , v _ { \nu } \}$ and <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/m/m130/m130130/m1301304.png"/> 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 $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 [[#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 $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 [[#References|[a13]]]. For various proofs of Cayley's formula, see [[#References|[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 [[#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 $( \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 $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]]].

====References====
<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. &amp; 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 &amp; 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>