Invariant theory-like theorems for matroids and oriented matroids (Q1342375): Difference between revisions

This paper continues the discussion of the authors and \textit{J. Richter- Gebert} [Adv. Math. 87, No. 2, 160-185 (1991; Zbl 0762.05030)], exploiting that the varieties of all \(n\)-element matroids (over GF(2)) and all \(n\)-element oriented matroids (over GF(3)) can be defined by the same family of polynomials, which are constructed via elementary symmetric functions from the Grassmann-Plücker polynomials that define the Grassmann varieties. The main result is the existence of final polynomials with coefficients in GF(3) that serve as algebraic certificates for non-orientability of matroids. Furthermore an algebraic characterization is given of those projective theorems (expressed as bracket polynomials) that are valid for all (not necessarily realizable) matroids. The key tool is a special version of the Nullstellensatz for prime order fields. Although the proofs are constructive, the polynomials appearing in this work in general have an exponential number of monomials, and thus lead to exponential algorithms. It is an interesting open problem whether for matroids of rank 3 an effective certificate (verifiable in polynomial time) exists for non-orientability, or whether even a polynomial algorithm exists to test orientability.