A Combinatorial Proof of the All Minors Matrix Tree Theorem 论文

摘要

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.