Coboundaries, Flows, and Tutte Polynomials of Matrices

Using matroid duality and the critical problem, we show that certain evaluations of the Tutte polynomial of a matroid represented as a matrix over a finite field GF(q) can be interpreted as weighted sums over pairs f , g of functions defined from the ground set to GF(q) whose difference f – g is the restriction of a linear functional on the column space of the matrix. Similar interpretations are given for the characteristic polynomial evaluated at q. These interpretations extend and elaborate interpretations for Tutte and chromatic polynomials of graphs due to Goodall and Matiyasevich. Received July 14, 2006