In mathematics, a regular matroid is a matroid that can be represented over all fields.
Contents
Definition
A matroid is defined to be a family of subsets of a finite set, satisfying certain axioms. The sets in the family are called "independent sets". One of the ways of constructing a matroid is to select a finite set of vectors in a vector space, and to define a subset of the vectors to be independent in the matroid when it is linearly independent in the vector space. Every family of sets constructed in this way is a matroid, but not every matroid can be constructed in this way, and the vector spaces over different fields lead to different sets of matroids that can be constructed from them.
A matroid
Properties
If a matroid is regular, so is its dual matroid, and so is every one of its minors. Every direct sum of regular matroids remains regular.
Every graphic matroid (and every co-graphic matroid) is regular. Conversely, every regular matroid may be constructed by combining graphic matroids, co-graphic matroids, and a certain ten-element matroid that is neither graphic nor co-graphic, using an operation for combining matroids that generalizes the clique-sum operation on graphs.
The number of bases in a regular matroid may be computed as the determinant of an associated matrix, generalizing Kirchhoff's matrix-tree theorem for graphic matroids.
Characterizations
The uniform matroid
If a matroid is regular, it must clearly be realizable over the two fields GF(2) and GF(3). The converse is true: every matroid that is realizable over both of these two fields is regular. The result follows from a forbidden minor characterization of the matroids realizable over these fields, part of a family of results codified by Rota's conjecture.
The regular matroids are the matroids that can be defined from a totally unimodular matrix, a matrix in which every square submatrix has determinant 0, 1, or −1. The vectors realizing the matroid may be taken as the rows of the matrix. For this reason, regular matroids are sometimes also called unimodular matroids. The equivalence of regular matroids and unimodular matrices, and their characterization by forbidden minors, are deep results of W. T. Tutte, originally proved by him using the Tutte homotopy theorem. Gerards (1989) later published an alternative and simpler proof of the characterization of unimodular matrices by forbidden minors.
Algorithms
There is a polynomial time algorithm for testing whether a matroid is regular, given access to the matroid through an independence oracle.