Binary matroid


In matroid theory, a binary matroid is a matroid that can be represented over the finite field GF. That is, up to isomorphism, they are the matroids whose elements are the columns of a -matrix and whose sets of elements are independent if and only if the corresponding columns are linearly independent in GF.

Alternative characterizations

A matroid is binary if and only if
Every regular matroid, and every graphic matroid, is binary. A binary matroid is regular if and only if it does not contain the Fano plane or its dual as a minor. A binary matroid is graphic if and only if its minors do not include the dual of the graphic matroid of nor of. If every circuit of a binary matroid has odd cardinality, then its circuits must all be disjoint from each other; in this case, it may be represented as the graphic matroid of a cactus graph.

Additional properties

If is a binary matroid, then so is its dual, and so is every minor of. Additionally, the direct sum of binary matroids is binary.
define a bipartite matroid to be a matroid in which every circuit has even cardinality, and an Eulerian matroid to be a matroid in which the elements can be partitioned into disjoint circuits. Within the class of graphic matroids, these two properties describe the matroids of bipartite graphs and Eulerian graphs, respectively. For planar graphs these two properties are dual: a planar graph or its matroid is bipartite if and only if its dual is Eulerian. The same is true for binary matroids. However, there exist non-binary matroids for which this duality breaks down.
Any algorithm that tests whether a given matroid is binary, given access to the matroid via an independence oracle, must perform an exponential number of oracle queries, and therefore cannot take polynomial time.