Before discussing oriented matroids, we first recall the definition of a matroid. A matroid abstracts the notion of independence that appears in many settings, such as linear independence in a vector space and acyclicity in a graph.
Formally, a matroid is a pair , where is a ground set and is a family of subsets of , called the independent sets. The family must satisfy the following three axioms:
First, the empty set is independent: .
Second, every subset of an independent set is independent. That is, if and , then .
Third, if two independent sets have different cardinalities, the smaller one can be enlarged by an element of the larger one. More precisely, if and , then there exists an element such that .
These axioms allow us to define the rank of any subset as the maximum size of an independent subset of :
Any subset of that does not belong to is called dependent. A minimal dependent set is called a circuit. Thus, a matroid can be described equivalently by either its independent sets or its circuits.
1.1 Oriented matroids from directed graphs
Consider a directed graph with vertex set and arc set . Each simple cycle, being a minimal dependent set, can be regarded as a signed subset of . After choosing a direction in which to traverse the cycle, we place each arc in the positive or negative part according to whether its orientation agrees or disagrees with the direction of traversal. The resulting signed subset is called a signed circuit of .
An oriented matroid obtained from a digraph can be described by its signed circuits. The collection of all signed circuits of is
We denote the resulting oriented matroid by . Note that contains both signed circuits in every opposite pair . By forgetting the signs, we obtain the underlying matroid , where .
A second description uses minimal cuts. Given a partition of the vertex set, the arcs between and form a minimal cut if removing them increases the number of connected components of the underlying undirected graph by one. Let consist of the arcs directed from to , and let consist of those directed from to . The resulting signed sets are called the signed cocircuits of . We write
Properties of can be expressed in terms of the collections and . For example, the digraph is acyclic—that is, it contains no directed cycle—if and only if contains no positive circuit, where a circuit is positive if . The same property can be characterized in terms of cocircuits: is acyclic if and only if every arc belongs to a positive cocircuit. In other words, for every , there exists a cocircuit such that .
Sketch of Proof.
Suppose that is acyclic, and fix an arc . Let be the set of vertices from which is reachable. Since is acyclic, ; otherwise, a path from to , together with the arc , would form a directed cycle. Hence, belongs to the cut induced by the partition . Moreover, no arc enters : if were an arc with and , then would imply , contradicting . Thus, this cut is positive. By restricting it to a minimal cut containing , we obtain a positive cocircuit with .
We now introduce the dual oriented matroid, whose collection of circuits is . To motivate this definition, suppose that is a planar digraph. There is a canonical way to orient its dual graph such that the circuits of the dual graph correspond exactly to the cocircuits of the original graph, and conversely.
The next important property is orthogonality: if a directed cycle crosses a cut in one direction, then it must also cross the cut in the opposite direction.
If is a circuit and is a cocircuit of an oriented matroid, then
For two signed sets and , let
denote their separation set. The orthogonality condition can then be written as for every and every .
1.2 Point configurations and hyperplane arrangements
Vector configurations
Linear dependence and independence in vector spaces provide alternative ways to view oriented matroids. Given a finite set of vectors that spans a vector space of dimension over an arbitrary field, the minimal linear dependences yield the circuits of a matroid of rank . Over , a minimal linear dependence may be written as
with , not all zero. Here the sets are the circuits of the underlying matroid. For the associated oriented matroid, we consider the signed sets .
This yields the oriented matroid of a vector configuration in terms of its collection of signed circuits.
If provides the same list of signed circuits for a given oriented matroid , we say is a realization of .
The basis orientation or chirotope of a vector configuration is given by the signs of the determinants of ordered -subsets of .
The function is antisymmetric.
In addition to antisymmetry, the determinants of a configuration of vectors also satisfy Grassmann-Plücker relations. To describe these relations, consider the Plücker embedding of the Grassmannian of -dimensional subspaces of an -dimensional vector space into the projectivization of the -th exterior power of .
Here form a basis of the chosen subspace. The homogeneous coordinates of the image under this embedding satisfy a simple set of homogeneous quadratic relations. After choosing a basis of , let be the matrix whose columns are the coordinates of , and define to be the determinant of the submatrix obtained by selecting rows in that order. Then for any two ordered sequences
we have
For example, in rank , with and , and writing determinants in brackets, we have
The corresponding oriented matroid axiom thus requires that the six signs of the brackets on the left-hand side allow the equality to hold, even when the actual scalars are not given. In other words, the three terms , , and must either all be zero or include both a positive and a negative term.
We can also interpret the cocircuits of a vector configuration: consider any linear hyperplane spanned by a subset of , and let and be the sets of vectors in on either side of . These signed sets are the cocircuits of the configuration. However, this is hard to visualize, which motivates the passage to affine space to reduce the dimension by one.
Point configurations
Every vector configuration in corresponds to an affine point configuration in an -dimensional affine space. We choose a linear form such that for all , define
as our affine space of dimension , and associate with every vector the point .
For example, let be the vectors in given by the columns of the matrix . From we get an oriented matroid of rank with signed circuits , and so on. This vector configuration has the same signed circuits as the digraph shown above, with column corresponding to arc . Thus, is a realization of the oriented matroid of this digraph.
With , we get the point configuration in the affine plane, , which is obtained by deleting the first coordinates from the vectors .
Note that signed circuits have a simple geometric interpretation in the affine plane. Every circuit is a minimal signed set of points such that the convex hull of the positive elements intersects the convex hull of the negative elements. Mathematically speaking, the signed circuits of an affine point configuration are exactly the minimal Radon partitions of the point set. For example, from we see that point must lie on the open line segment . Similarly, from we see that the open line segments and must intersect (in the ambient real affine plane, not necessarily in the oriented matroid itself).
The sign patterns of arbitrary (not necessarily minimal) dependences can be derived by composing circuits. The composition of two signed sets is defined as
For example, if and , then . The signed sets obtained by repeated composition of circuits are called the vectors of this oriented matroid. Note that a dependent set may correspond to different vectors: has the same support as , but a different sign pattern.
