Binary matroid

Short description: Abstraction of mod-2 vector independence

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

Alternative characterizations

A matroid [math]\displaystyle{ M }[/math] is binary if and only if

• It is the matroid defined from a symmetric (0,1)-matrix.
• For every set [math]\displaystyle{ \mathcal{S} }[/math] of circuits of the matroid, the symmetric difference of the circuits in [math]\displaystyle{ \mathcal{S} }[/math] can be represented as a disjoint union of circuits.
• For every pair of circuits of the matroid, their symmetric difference contains another circuit.
• For every pair [math]\displaystyle{ C,D }[/math] where [math]\displaystyle{ C }[/math] is a circuit of [math]\displaystyle{ M }[/math] and [math]\displaystyle{ D }[/math] is a circuit of the dual matroid of [math]\displaystyle{ M }[/math], [math]\displaystyle{ |C\cap D| }[/math] is an even number.
• For every pair [math]\displaystyle{ B,C }[/math] where [math]\displaystyle{ B }[/math] is a basis of [math]\displaystyle{ M }[/math] and [math]\displaystyle{ C }[/math] is a circuit of [math]\displaystyle{ M }[/math], [math]\displaystyle{ C }[/math] is the symmetric difference of the fundamental circuits induced in [math]\displaystyle{ B }[/math] by the elements of [math]\displaystyle{ C\setminus B }[/math].
• No matroid minor of [math]\displaystyle{ M }[/math] is the uniform matroid [math]\displaystyle{ U{}^2_4 }[/math], the four-point line.
• In the geometric lattice associated to the matroid, every interval of height two has at most five elements.

Related matroids

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 (a seven-element non-regular binary matroid) 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 [math]\displaystyle{ K_5 }[/math] nor of [math]\displaystyle{ K_{3,3} }[/math]. 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 [math]\displaystyle{ M }[/math] is a binary matroid, then so is its dual, and so is every minor of [math]\displaystyle{ M }[/math]. Additionally, the direct sum of binary matroids is binary.

(Harary Welsh) 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 (not-necessarily-connected graphs in which all vertices have even degree), respectively. For planar graphs (and therefore also for the graphic matroids of 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.