A Square Basis Theorem for Matroids

For every matroid of rank at least one, the basis-exchange square relations e_{B+i} − e_{B+j} − e_{B′+i} + e_{B′+j}, the exponent vectors of the symmetric exchange binomials, contain a ℤ-basis of the integer kernel of the basis incidence matrix. This strengthens the fact that the squares generate the kernel, since a generating set need not contain a basis. Equivalently, after inverting the variables, the toric ideal of the matroid is a complete intersection of codim I_M symmetric exchange binomials, the least possible number of generators. White's conjecture asserts that the symmetric exchange binomials generate the toric ideal, and it fails in general. The Square Basis Theorem shows that at the level of the lattice a square basis always exists. The proof is constructive and combinatorial and uses no computer calculation. For uniform matroids it gives an explicit unitriangular square basis that involves no choices. As an application, the paper characterizes when two real matrices differ by an invertible row transformation and an invertible column scaling, by square conditions on the signs and absolute values of their Plücker ratios, one for each element of a square basis.