A Combinatorial Proof of the All Minors Matrix Tree Theorem

TLDR

Let A be the matrix with entries –a_{ij} for i≠j and diagonal entries chosen so that column sums are zero, and the all‑minors matrix‑tree theorem states that |A(¯W|¯U)| enumerates forests in the complete digraph with k trees, each containing exactly one vertex in U and one in W, and arcs directed away from the U vertex. The authors aim to give an elementary combinatorial proof of the all‑minors matrix‑tree theorem. They show that each term in |A(¯W|¯U)| corresponding to an enumerated forest occurs exactly once while the other terms cancel. The sign of each term is determined by the parity of the linking from U to W in the forest, the results extend to signed graphs, and the theorem provides a natural coordinatization of gammoids.

Abstract

Let $( A_{ij} )$, i, $j \in V$ be the matrix with entries $ - a_{ij} $ if $i \ne j$ and diagonal entries such that all the column sums are zero. Let $ a_{ij} $ be a variable associated with arc $ij$ in the complete digraph G on vertices V. Let $| A ( \bar{W}|\bar{U} ) |$ be the matrix that results from deleting sets of k rows W and columns U from A. The all minors matrix tree theorem states that $ | A ( \bar{W}|\bar{U} ) |$ enumerates the forests in G that have (a) k trees, (b) each tree contains exactly one vertex in U and exactly one vertex in W, and (c) each arc is directed away from the vertex in U of the tree containing the arc. We give an elementary combinatorial proof in which we show that each of the terms in $| A ( \bar{W}|\bar{U} ) |$ that corresponds to an enumerated forest occurs just once and the other terms cancel. The sign of each term is determined by the parity of the linking from U to W contained in the forest, and is easy to calculate explicitly in the proof. The results are extended to signed graphs. The theorem provides a coordinatization (linear representation) of gammoids that is in a certain sense natural.