5
$\begingroup$

could someone provide me/refer me to a intuitive idea/proof behind Kirchhoff's Matrix Tree Theorem that uses as little technical details involving matrices/linear algebra as possible? I'm trying to give a group of talented high schoolers who haven't seen matrices before a sketch/cursory proof of the result, but I couldn't think of a good way to explain it.

$\endgroup$
  • 4
    $\begingroup$ Given that Kirchhoff's matrix tree theorem has a determinant in the statement, I'm not sure what you can expect. $\endgroup$ – Yuval Filmus Jul 9 '15 at 17:30
  • $\begingroup$ wikipedia Kirchoff thm with few-paragraph proof outline $\endgroup$ – vzn Jul 9 '15 at 21:31
  • $\begingroup$ Wikipedia's proof outline (which is missing a central part) is heavy on linear algebra. The combinatorial proof is instead heavy on combinatorics. $\endgroup$ – Yuval Filmus Jul 9 '15 at 21:44
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). \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$ monomials, 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 cycles $\pi_1,\ldots,\pi_{\ell(\pi)}$ 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), ans 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 $T(\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$ great, but probably well outside the range of "talented high schoolers" & likely even most undergraduates! $\endgroup$ – vzn Jul 9 '15 at 21:30
  • $\begingroup$ @vzn Not necessarily. You can add lots of pictures to make it clearer, consider only the case of 0 or 1 cycles (of $\alpha$) to make it simpler, and use concrete examples involving small $n$ to make it tangible. Of course, since a determinant is involved, the students (or undergraduates) need to have some background, in this case they need to understand the concept of sign of a permutation. $\endgroup$ – Yuval Filmus Jul 9 '15 at 21:42

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

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