Namespaces
Variants
Actions

Difference between revisions of "Matrix tree theorem"

From Encyclopedia of Mathematics
Jump to: navigation, search
m (link)
m (AUTOMATIC EDIT (latexlist): Replaced 100 formulas out of 101 by TEX code with an average confidence of 2.0 and a minimal confidence of 2.0.)
Line 1: Line 1:
Let <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/m/m130/m130130/m1301301.png" /> be a [[Graph|graph]] with <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/m/m130/m130130/m1301302.png" /> vertices <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/m/m130/m130130/m1301303.png" /> and <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/m/m130/m130130/m1301304.png" /> edges <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/m/m130/m130130/m1301305.png" />, some of which may be oriented. The incidence matrix of <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/m/m130/m130130/m1301306.png" /> is the <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/m/m130/m130130/m1301307.png" />-matrix <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/m/m130/m130130/m1301308.png" /> whose entries are given by <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/m/m130/m130130/m1301309.png" /> if <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/m/m130/m130130/m13013010.png" /> is a non-oriented link (i.e. an edge that is not a loop) incident to <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/m/m130/m130130/m13013011.png" /> or if <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/m/m130/m130130/m13013012.png" /> is an oriented link with head <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/m/m130/m130130/m13013013.png" />, <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/m/m130/m130130/m13013014.png" /> if <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/m/m130/m130130/m13013015.png" /> is an oriented link with tail <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/m/m130/m130130/m13013016.png" />, <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/m/m130/m130130/m13013017.png" /> if <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/m/m130/m130130/m13013018.png" /> is a loop (necessarily non-oriented) at <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/m/m130/m130130/m13013019.png" />, and <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/m/m130/m130130/m13013020.png" /> otherwise. The mixed Laplacian matrix of <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/m/m130/m130130/m13013021.png" /> is defined as <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/m/m130/m130130/m13013022.png" />. It is easy to see that the diagonal entries of <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/m/m130/m130130/m13013023.png" /> give the degrees of the vertices with, however, each loop contributing <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/m/m130/m130130/m13013024.png" /> to the count, and the off-diagonal entry <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/m/m130/m130130/m13013025.png" /> gives the number of non-oriented edges joining <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/m/m130/m130130/m13013026.png" /> and <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/m/m130/m130130/m13013027.png" /> minus the number of oriented edges joining them. Let <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/m/m130/m130130/m13013028.png" /> denote the number of [[spanning tree]]s of <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/m/m130/m130130/m13013029.png" />, with orientation ignored.
+
<!--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.
  
The matrix tree theorem in its classical form, which is already implicit in the work of G. Kirchhoff [[#References|[a9]]], states that if <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/m/m130/m130130/m13013030.png" /> is the Laplacian of any orientation of a loopless undirected graph <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/m/m130/m130130/m13013031.png" /> and <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/m/m130/m130130/m13013032.png" /> is the matrix obtained by deleting any row <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/m/m130/m130130/m13013033.png" /> and column <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/m/m130/m130130/m13013034.png" /> of <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/m/m130/m130130/m13013035.png" />, then <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/m/m130/m130130/m13013036.png" />; that is, each [[Cofactor|cofactor]] of <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/m/m130/m130130/m13013037.png" /> is equal to the tree-number of <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/m/m130/m130130/m13013038.png" />. If <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/m/m130/m130130/m13013039.png" /> denotes the adjoint of the matrix <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/m/m130/m130130/m13013040.png" /> and <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/m/m130/m130130/m13013041.png" /> denotes the matrix with all entries equal to <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/m/m130/m130130/m13013042.png" />, then <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/m/m130/m130130/m13013043.png" />. The proof of this theorem uses the Binet–Cauchy theorem to expand the cofactor of <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/m/m130/m130130/m13013044.png" /> together with the fact that every non-singular <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/m/m130/m130130/m13013045.png" />-minor of <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/m/m130/m130130/m13013046.png" /> (cf. also [[Minor|Minor]]) comes from a spanning tree of <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/m/m130/m130130/m13013047.png" /> having value <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/m/m130/m130130/m13013048.png" />. In the case of the complete graph <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/m/m130/m130130/m13013049.png" /> (with some orientation), <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/m/m130/m130130/m13013050.png" />, and it can be seen that <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/m/m130/m130130/m13013051.png" />, which is Cayley's formula for the number of labelled trees on <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/m/m130/m130130/m13013052.png" /> vertices [[#References|[a4]]]. Temperley's result [[#References|[a3]]], Prop. 6.4, avoids using the cofactor notation in the following form: <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/m/m130/m130130/m13013053.png" />. It is interesting to note that this determinantal way of computing <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/m/m130/m130130/m13013054.png" /> requires <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/m/m130/m130130/m13013055.png" /> operations rather than the <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/m/m130/m130130/m13013056.png" /> operations when using recursion [[#References|[a17]]], p. 66.
+
Out of 101 formulas, 100 were replaced by TEX code.-->
  
For a loopless directed graph <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/m/m130/m130130/m13013057.png" />, let <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/m/m130/m130130/m13013058.png" /> and <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/m/m130/m130130/m13013059.png" />, where <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/m/m130/m130130/m13013060.png" /> and <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/m/m130/m130130/m13013061.png" /> are the diagonal matrices of in-degrees and out-degrees in <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/m/m130/m130130/m13013062.png" />, and the <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/m/m130/m130130/m13013063.png" />-entry of <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/m/m130/m130130/m13013064.png" /> is the number of edges from <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/m/m130/m130130/m13013065.png" /> to <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/m/m130/m130130/m13013066.png" />. An out-tree is an orientation of a tree having a root of in-degree <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/m/m130/m130130/m13013067.png" /> and all other vertices of in-degree <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/m/m130/m130130/m13013068.png" />. 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 <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/m/m130/m130130/m13013069.png" /> is the value of any cofactor in the <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/m/m130/m130130/m13013070.png" />th row of <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/m/m130/m130130/m13013071.png" /> (respectively, <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/m/m130/m130130/m13013072.png" />th column of <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/m/m130/m130130/m13013073.png" />). In fact, the principal minor of <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/m/m130/m130130/m13013074.png" /> obtained by deleting rows and columns indexed by <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/m/m130/m130130/m13013075.png" /> equals the number of spanning forests of <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/m/m130/m130130/m13013076.png" /> having precisely <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/m/m130/m130130/m13013077.png" /> out-trees rooted at <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/m/m130/m130130/m13013078.png" />.
+
{{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.
  
In all the approaches it is clear that the significant property of the Laplacian <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/m/m130/m130130/m13013079.png" /> is that <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/m/m130/m130130/m13013080.png" /> for <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/m/m130/m130130/m13013081.png" />. By allowing <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/m/m130/m130130/m13013082.png" /> 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 <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/m/m130/m130130/m13013083.png" /> on the vertex set <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/m/m130/m130130/m13013084.png" />, with <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/m/m130/m130130/m13013085.png" /> occurrences of the edge <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/m/m130/m130130/m13013086.png" /> (directed away from the root), is the coefficient of the monomial <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/m/m130/m130130/m13013087.png" /> in the <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/m/m130/m130130/m13013088.png" />th cofactor of the matrix <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/m/m130/m130130/m13013089.png" />, where <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/m/m130/m130130/m13013090.png" /> and <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/m/m130/m130130/m13013091.png" /> is the sum of the entries in the <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/m/m130/m130130/m13013092.png" />th row of <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/m/m130/m130130/m13013093.png" />, for <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/m/m130/m130130/m13013094.png" />.
+
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]]].
 
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 <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/m/m130/m130130/m13013095.png" />-matrix <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/m/m130/m130130/m13013096.png" />. 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 <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/m/m130/m130130/m13013097.png" /> when <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/m/m130/m130130/m13013098.png" /> is a tree is studied in [[#References|[a1]]].
+
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 <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/m/m130/m130130/m130130100.png" />-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 <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/m/m130/m130130/m130130102.png" />-optimal designs (see [[#References|[a7]]], p. 67). Finally, the matrix tree theorem is closely related to the [[Perron–Frobenius theorem|Perron–Frobenius theorem]]. If <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/m/m130/m130130/m130130103.png" /> 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).
+
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><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>
+
<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>

Revision as of 17:02, 1 July 2020

Let $G = ( V , E )$ be a graph with $\nu$ vertices $\{ v _ { 1 } , \dots , v _ { \nu } \}$ and 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)
How to Cite This Entry:
Matrix tree theorem. Encyclopedia of Mathematics. URL: http://encyclopediaofmath.org/index.php?title=Matrix_tree_theorem&oldid=50438
This article was adapted from an original article by Ravindra B. BapatJerrold W. GrossmanDevadatta M. Kulkarni (originator), which appeared in Encyclopedia of Mathematics - ISBN 1402006098. See original article