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