Matrix tree theorem
Let be a graph with
vertices
and
edges
, some of which may be oriented. The incidence matrix of
is the
-matrix
whose entries are given by
if
is a non-oriented link (i.e. an edge that is not a loop) incident to
or if
is an oriented link with head
,
if
is an oriented link with tail
,
if
is a loop (necessarily non-oriented) at
, and
otherwise. The mixed Laplacian matrix of
is defined as
. It is easy to see that the diagonal entries of
give the degrees of the vertices with, however, each loop contributing
to the count, and the off-diagonal entry
gives the number of non-oriented edges joining
and
minus the number of oriented edges joining them. Let
denote the number of spanning trees of
, 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 is the Laplacian of any orientation of a loopless undirected graph
and
is the matrix obtained by deleting any row
and column
of
, then
; that is, each cofactor of
is equal to the tree-number of
. If
denotes the adjoint of the matrix
and
denotes the matrix with all entries equal to
, then
. The proof of this theorem uses the Binet–Cauchy theorem to expand the cofactor of
together with the fact that every non-singular
-minor of
(cf. also Minor) comes from a spanning tree of
having value
. In the case of the complete graph
(with some orientation),
, and it can be seen that
, which is Cayley's formula for the number of labelled trees on
vertices [a4]. Temperley's result [a3], Prop. 6.4, avoids using the cofactor notation in the following form:
. It is interesting to note that this determinantal way of computing
requires
operations rather than the
operations when using recursion [a17], p. 66.
For a loopless directed graph , let
and
, where
and
are the diagonal matrices of in-degrees and out-degrees in
, and the
-entry of
is the number of edges from
to
. An out-tree is an orientation of a tree having a root of in-degree
and all other vertices of in-degree
. 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
is the value of any cofactor in the
th row of
(respectively,
th column of
). In fact, the principal minor of
obtained by deleting rows and columns indexed by
equals the number of spanning forests of
having precisely
out-trees rooted at
.
In all the approaches it is clear that the significant property of the Laplacian is that
for
. By allowing
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
on the vertex set
, with
occurrences of the edge
(directed away from the root), is the coefficient of the monomial
in the
th cofactor of the matrix
, where
and
is the sum of the entries in the
th row of
, for
.
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 -matrix
. 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
when
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 -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
-optimal designs (see [a7], p. 67). Finally, the matrix tree theorem is closely related to the Perron–Frobenius theorem. If
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=50438