The Matrix-Tree Theorem without the matrix

Question

I'm teaching an introductory graph theory course in the Fall, which I'm excited about because it gives me the chance to improve my understanding of graphs (my work is in topology). A highlight for me will be to teach the Matrix-Tree Theorem, which I think is the only place that linear algebra is used in the course.

Let κ(G) denote the number of spanning trees of G (the complexity of G), and let L(G) denote the Laplacian matrix of G. Finally, for a vertex v of G, let L(v|v) denote the Laplacian matrix with the row and column corresponding to v deleted.

Matrix-Tree Theorem: κ(G)= det L(v|v).

It seems a shame for Linear Algebra to be a prerequisite for my course. Anyway, I don't expect most of my students to be great Linear Algebra experts. Because my students might not remember things like Cauchy-Binet, but mainly so that I myself feel that I can really understand what I'm teaching, I wonder how the Matrix-Tree Theorem could be proven without ever mentioning matrices. On a planet with strong combinatorics and where linear algebra had not been discovered, how would they prove the Matrix-Tree Theorem?

The RHS of the Matrix-Tree Theorem makes sense without ever mentioning matrices, via the Lindström-Gessel-Viennot(-Karlin-MacGregor) Lemma. Construct a graph H, with a source and a sink corresponding to each vertex of G, so that the signed sum of edge weights gives the entries of the Lagrangian matrix for G (surely there's a clever standard way to do this!) and define the determinant of H to be the signed sum of all n-tuples of non-intersecting paths from the sources to the sinks. This interpretation of the determinant seems a nice topic to teach. Maybe there's even an easier way.

Cauchy-Binet becomes an elementary property of sets of non-intersecting paths in H, but I can't see how to free the rest of the proof of the Matrix-Tree Theorem from linear algebra.

Question: Is there a proof of the Matrix-Tree Theorem which makes no mention of matrices? Is it simple enough that one could teach it in an introductory graph theory course?

Note 1: If the purpose of the Matrix-Tree Theorem is to efficiently calculate the complexity of a graph, then dodging linear algebra is surely counterproductive, because a determinant can efficiently be calculated in polynomial time. But, quite beside from my interest in "correctly-tooled" proofs and my teaching goals, I have vague dreams which are almost certainly nonsense about better understanding the Alexander polynomial as a quantum invariant along the lines of this question which might conceivably factor through the Matrix-Tree Theorem (or rather some version of Kirchhoff's formula), and I think I clearly want to stay in the diagrammatic world.

Note 2: This excellent post by Qiaochu Yuan suggests that the answer to my question is in Aigner. I'm travelling right now, and the relevant section isn't on Google Books, so I don't have access to Aigner for the next few weeks. If memory serves, Aigner still uses linear algebra, but maybe I'm wrong... anyway, if the answer turns out to be "look in Aigner" then please downvote this question, or if you could summarize how it's done, I would be happier. The answer will surely turn out to be "look in [somewhere]" anyway, because surely this is easy and well-known (just I don't know it)...

Answer 1

A combinatorial proof of the matrix-tree theorem can be found in the paper by D. Zeilberger A combinatorial approach to matrix algebra, Discrete Math. 56 (1985), 61–72. The proof uses only the interpretation of the determinant as an alternating sum over permutations. Each term corresponds to a digraph, and the digraphs that do not correspond to trees cancel.

Answer 2

You can do without Cauchy-Binet.

If $e \in E(G)$, let $G/e$ denote the graph you get by contracting $e$ to a vertex. Let $t(G)$ denote the number of spanning trees in $G$. Then $$ t(G) = t(G\setminus e) + t(G/e). $$ If $Q$ denotes the Laplacian of $G$ and $M[u]$ the matrix we get from the Laplacian by deleting the row and column with index $u$ from $M$, it is straightforward (using standard determinental operations) to show that $$ \det Q(G)[u] = \det Q(G\setminus e)[u] +\det Q(G/e)[u] $$ So the result follows by induction.

This proof is presented in Section 13.2 of one of my favorite books on algebraic graph theory :-) I am sure many other people have come up with it. It provides an excuse to talk about some of the other interesting graph parameters thatn can be computed by deletion-contraction (or is it deletion/contraction?)

Answer 3

Interesting question! There is an elementary way to prove the matrix tree theorem using only combinatorial reasoning and bijections. The result I'm referring to is: the number of spanning trees in a graph $G$ is the same as the number of $G$-parking functions. There is a bijective proof of this fact in "A family of bijections between G-parking functions and spanning trees" by D. Chebikin and P. Pylyavskyy. Now what do these $G$-parking functions have to do with the determinant of the laplacian $L(G)$?

It turns out that $G$-parking functions are representatives of the elements in the cokernel of the map $\mathbb Z^{n}\to \mathbb Z^n$ given by multiplication by $L(G)$, where $n$ is the number of vertices in $G$. This cokernel pops up in a lot of places and it's usually called the Critical group of $G$ or the sandpile group of $G$ (or by some authors, the Jacobian group or Picard group) and it is well known to have the same cardinality as the number of spanning trees of $G$. Any bijection between these will not be canonical because there is no canonical choice of spanning tree on $G$, so all bijections must make choices at some point.

As far as bijections with other cokernels, like LGV or Kasteleyn-Percus, I don't know if it can be done neatly in great generality. I know that counting spanning trees can be translated to counting perfect matchings for planar graphs, for instance. Perhaps it extends to other nice classes.

That said, even though this approach avoids mentioning matrices, Cauchy-Binet and all that, it would be awful for a first proof of the matrix tree theorem. I think this is similar to trying to teach the elementary proof of the prime number theorem in a first course of analytic number theory. Using less tools doesn't necessarily lead to more enlightenment. :)

Answer 4

The algebraic proof goes like this. Fix a number of vertices $n$, and consider the "formal Laplacian" $n \times n$ matrix defined by $$ \begin{align*} L(i,i) &= \sum_{j \neq i} X(i,j) \\ L(i,j) &= - X(i,j) \qquad \text {for } i\neq j. \end{align*} $$ Here the $X(i,j)$ are commuting indeterminates. For every spanning tree $T$ of the complete graph $K_n$ we can associate a degree $n-1$ monomial $X(T)$ as follows. Root the tree at the vertex $n$. For every non-root vertex $i$ with parent $j$, we include the variable $X(i,j)$ in the monomial. In total $X(T)$ is a product of $n-1$ indeterminates, one for every edge in the tree.

Let $M$ be the $(n,n)$ minor of $L$. We will show that $\det M = \sum_T X(T)$. You can derive the matrix-tree theorem from this statement by substituting the actual graph for the indeterminates $X(i,j)$. If you wish, you can run the entire proof after doing the substitution, and then you don't have to talk about indeterminates.

Recall that $$\det M = \sum_{\pi \in S_{n-1}} (-1)^\pi \prod_{i=1}^{n-1} M(i,\pi(i)).$$ We can write every permutation $\pi$ as a product of nontrivial cycles $\pi_1,\ldots,\pi_{\ell(\pi)}$ (where $\ell (\pi) $ is the number of nontrivial cycles) and of fixed points $F(\pi)$, and then we get $$ \begin{align*} \det M &= \sum_\pi (-1)^\pi \prod_{t=1}^{\ell(\pi)} \prod_{i \in \pi_t} (-X(i,\pi(i))) \prod_{i \in F(\pi)} \left(\sum_{j \neq i} X(i,j)\right) \\ &= \sum_\pi (-1)^{\ell(\pi)} \prod_{t=1}^{\ell(\pi)} \prod_{i \in \pi_t} X(i,\pi(i)) \prod_{i \in F(\pi)} \left(\sum_{j \neq i} X(i,j)\right), \end{align*} $$ using the formula $(-1)^\pi = \prod_{t=1}^{\ell(\pi)} (-1)^{|\pi_t|+1}$. We can rewrite this as $$ \det M = \sum_\pi D(\pi), $$ where $D(\pi)$ is the expression appearing above.

If we open up all the sums, we find that $\det M$ is a (weighted) sum of monomials of the form $X(\alpha) = \prod_{i=1}^{n-1} X(i,\alpha(i))$. For each $\alpha$, we can look at the directed graph in which $i$ points at $\alpha(i)$. It's not hard to see that each such graph consists of a (possibly empty) collection of cycles $\alpha_1,\ldots,\alpha_{\ell(\alpha)}$ and a tree $T(\alpha)$ rooted at $n$. We will show that the coefficient of $X(\alpha)$ equals $1$ if $\ell(\alpha) = 0$, and vanishes otherwise. This will complete the proof.

Consider first the case that $\ell(\alpha) = 0$. In this case the only permutation $\pi$ for which $X(\alpha)$ appears in $D(\pi)$ is the identity permutation (since every $X(\beta)$ appearing in any other $D(\pi)$ contains some cycle), and so the coefficient of $X(\alpha)$ in $\det M$ is indeed $1$.

Next, consider the case in which $\ell = \ell(\alpha) \neq 0$. In this case, for every subset $S$ of the cycles of the directed graph corresponding to $\alpha$, $X(\alpha)$ appears in $D(\pi)$ for $\pi = \pi(S)$ which consists of the cycles in $S$, and it only appears in these $D(\pi)$. For every $S$, the coefficient of $X(\alpha)$ in $D(\pi(S))$ is $(-1)^{|S|}$. Therefore the total coefficient of $X(\alpha)$ in $\det M$ is $$ \sum_{S \subseteq \{\alpha_1,\ldots,\alpha_\ell\}} (-1)^{|S|} = \sum_{S_1 \subseteq \{\alpha_1\}} \cdots \sum_{S_\ell \subseteq \{\alpha_\ell\}} (-1)^{|S_1| + \cdots + |S_\ell|} = \\ \sum_{S_1 \subseteq \{\alpha_1\}} (-1)^{|S_1|} \cdots \sum_{S_\ell \subseteq \{\alpha_\ell\}} (-1)^{|S_\ell|} = (1-1)^\ell = 0. $$ (This is just inclusion-exclusion. The previous case is the case $\ell=0$.) This completes the proof.

This proof is taken from lecture notes by Jacques Verstraete. See also Mark Muldoon's lecture notes, which presents this argument as a version of inclusion-exclusion.

Answer 5

I asked Daniel Spielman a related question, which was what the most conceptual proof of the matrix-tree theorem is, without appealing to the real numbers. He suggested these notes by Nikhil Srivastava.

Matrices are used, but really the linear algebra looks to me like it can be turned into combinatorics on graphs in a straightforward manner, so his answer constitutes a nice answer to this question as well. In any event, it's a nice short conceptual proof of the matrix-tree theorem which I hadn't known about.