25
$\begingroup$

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)...

$\endgroup$
4
  • $\begingroup$ This previous question of mine was basically about Lindström-Gessel-Viennot without the matrix mathoverflow.net/questions/37603/… $\endgroup$ Aug 22, 2011 at 9:54
  • 1
    $\begingroup$ @Daniel: Kirchhoff's original papers on the Matrix-Tree Theorem are available online (and in English translation). He proved it before linear algebra was invented! You may want to take a look. Try googling: On the Solution of the Equations Obtained from the Investigation of the Linear Distribution of Galvanic Currents $\endgroup$
    – John Klein
    Sep 7, 2015 at 19:45
  • $\begingroup$ Coming late to the party, but just wanted to say there is a direct connection between the Alexander polynomial and the matrix tree theorem. See "A new matrix-tree theorem" by Masbaum and Vaintrob academic.oup.com/imrn/article-abstract/2002/27/1397/708385 $\endgroup$ Aug 10, 2021 at 19:15
  • $\begingroup$ I just did this stuff in class and realized that there's an easy enough proof of Cauchy-Binet, assuming the most basic properties of determinants, that it shouldn't be considered an obstruction. Compute the determinant of the matrix [Id_n B, A 0_k] where A is kxn and B is nxk. By row and column reduction, it's (-1)^k det(AB). By direct expansion, of the (n+k)! terms, only (n choose k)*k!^2 of them are not obviously zero, and those sum to (-1)^{k^2} times the RHS of Cauchy-Binet. $\endgroup$ Mar 17, 2022 at 13:24

5 Answers 5

28
$\begingroup$

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.

$\endgroup$
1
  • 1
    $\begingroup$ This is exactly what I was hoping for (and it to me to be entirely suitable for an introductory graph theory course). Thanks! $\endgroup$ Aug 24, 2011 at 6:25
29
$\begingroup$

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?)

$\endgroup$
1
  • $\begingroup$ Hi Chris Godsil. Section 13.2 of which book? $\endgroup$
    – Qmechanic
    Oct 2, 2023 at 15:04
14
$\begingroup$

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. :)

$\endgroup$
5
  • $\begingroup$ Thanks! This looks extremely interesting, for me if not for the students! $\endgroup$ Aug 22, 2011 at 10:39
  • $\begingroup$ I am skeptical with regard to this proof: If you are using Smith's normal form, it only shows that the cardinality of the critical group is THE ABSOLUTE VALUE OF the determinant of the Laplacian. Now have fun proving that it is $\geq 0$ without linear algebra (such as properties of diagonally dominant matrices). $\endgroup$ Oct 3, 2011 at 1:17
  • $\begingroup$ @Darij: You are right, but I was only commenting on the Critical group/spanning trees bijection. I guess I'm saying that from a "combinatorics without linear algebra" perspective, the determinant of the Laplacian should be replaced by the cardinality of the critical group. $\endgroup$ Oct 3, 2011 at 1:30
  • $\begingroup$ Well, I prefer having signed quantities. I personally find nothing wrong with Sylvester-sieve direct proofs of the matrix-tree theorem, without the detour through the sandpile group. A proof using Smith's normal form cannot be considered combinatorial anyway. $\endgroup$ Oct 3, 2011 at 2:57
  • $\begingroup$ Smith's normal form shows it's advantages especially in q-enumeration. Why do you say it is not combinatorial? $\endgroup$ Oct 3, 2011 at 4:17
5
$\begingroup$

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.

$\endgroup$
1
  • $\begingroup$ There is a minor flaw in the argument: The directed graph in which $i$ points at $\alpha\left(i\right)$ will not always consist of a collection of cycles and a tree rooted at $n$. It will consist of a collection of cycles and some arcs from vertices outside this collection to vertices lying either outside or inside it. These latter arcs might not always form a tree rooted at $n$; they will form a forest whose roots are the vertices of the cycles and $n$. I think the proof is not hard to fix, though. $\endgroup$ Aug 19, 2015 at 12:12
5
$\begingroup$

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.

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.