A Combinatorial Proof of the All Minors Matrix Tree Theorem

Let (A₈₉), i, j V be the matrix with entries - a₈₉ if i j and diagonal entries such that all the column sums are zero. Let a₈₉ be a variable associated with arc ij in the complete digraph G on vertices V. Let | A (W|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 (W|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 (W|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.