![]() | ||
An oriented matroid is a mathematical structure that abstracts the properties of directed graphs and of arrangements of vectors in a vector space over an ordered field (particularly for partially ordered vector spaces). In comparison, an ordinary (i.e., non-oriented) matroid abstracts the dependence properties that are common both to graphs, which are not necessarily directed, and to arrangements of vectors over fields, which are not necessarily ordered.
Contents
- Background
- Axiomatizations
- Circuit axioms
- Chirotope axioms
- Equivalence
- Examples
- Directed graphs
- Linear algebra
- Convex polytope
- Orientability
- Duality
- Topological representation
- Geometry
- Optimization
- References
All oriented matroids have an underlying matroid. Thus, results on ordinary matroids can be applied to oriented matroids. However, the converse is false; some matroids cannot become an oriented matroid by orienting an underlying structure (e.g., circuits or independent sets). The distinction between matroids and oriented matroids is discussed further below.
Matroids are often useful in areas such as dimension theory and algorithms. Because of an oriented matroid's inclusion of additional details about the oriented nature of a structure, its usefulness extends further into several areas including geometry and optimization.
Background
In order to abstract the concept of orientation on the edges of a graph to sets, one needs the ability to assign "direction" to the elements of a set. The way this achieved is with the following definition of signed sets.
Given an element of the support
Axiomatizations
Like ordinary matroids, several equivalent systems of axioms exist. (Such structures that possess multiple equivalent axiomatizations are called cryptomorphic.)
Circuit axioms
Let
Chirotope axioms
Let
The term chirotope is derived from the mathematical notion of chirality, which is a concept abstracted from chemistry, where it is used to distinguish molecules that have the same structure except for a reflection.
Equivalence
Every chirotope of rank
and negative elements the complement. Thus a chirotope gives rise to the oriented bases of an oriented matroid. In this sense, (B0) is the nonempty axiom for bases and (B2) is the basis exchange property.
Examples
Oriented matroids are often introduced (e.g., Bachem and Kern) as an abstraction for directed graphs or systems of linear inequalities. Below are the explicit constructions.
Directed graphs
Given a digraph, we define a signed circuit from the standard circuit of the graph by the following method. The support of the signed circuit
If we consider the directed graph on the right, then we can see that there are only two circuits, namely
Linear algebra
If
with
Given the same set of vectors
where the right hand side of the equation is the sign of the determinant. Then
Convex polytope
Ziegler introduces oriented matroids via convex polytopes.
Orientability
A standard matroid is called orientable if its circuits are the supports of signed circuits of some oriented matroid. It is known that all real representable matroids are orientable. It is also known that the class of orientable matroids is closed under taking minors, however the list of forbidden minors for orientable matroids is known to be infinite. In this sense, oriented matroids is a much stricter formalization than regular matroids.
Duality
Much like matroids have unique dual, oriented matroids have unique orthogonal dual. What this means is the underlying matroids are dual and that the cocircuits are signed so that they are orthogonal to every circuit. Two signed sets are said to be orthogonal if the intersection of their supports is empty or if the restriction of their positive elements to the intersection and negative elements to the intersection form two nonidentical and non-opposite signed sets. The existence and uniqueness of the dual oriented matroid depends on the fact that every signed circuit is orthogonal to every signed cocircuit. To see why orthogonality is necessary for uniqueness one needs only to look to the digraph example above. We know that for planar graphs, that the dual of the circuit matroid is the circuit matroid of the graph's planar dual. Thus there are as many different oriented matroids that are dual as there are ways to orient a graph and its dual.
To see the explicit construction of this unique orthogonal dual oriented matroid, consider an oriented matroid's chirotope
then
Topological representation
Oriented matroids are abstractions of geometric constructs. The exact constructs are arrangements of pseudospheres. A
Geometry
The theory of oriented matroids has influenced the development of combinatorial geometry, especially the theory of convex polytopes, zonotopes, and of configurations of vectors (arrangements of hyperplanes). Many results—Carathéodory's theorem, Helly's theorem, Radon's theorem, the Hahn–Banach theorem, the Krein–Milman theorem, the lemma of Farkas—can be formulated using appropriate oriented matroids.
Optimization
The theory of oriented matroids was initiated by R. Tyrrell Rockafellar to describe the sign patterns of the matrices arising through the pivoting operations of Dantzig's simplex algorithm; Rockafellar was inspired by Albert W. Tucker's studies of such sign patterns in "Tucker tableaux".
The theory of oriented matroids has led to breakthroughs in combinatorial optimization. In linear programming, it was the language in which Robert G. Bland formulated his pivoting rule, by which the simplex algorithm avoids cycles. Similarly, it was used by Terlaky and Zhang to prove that their criss-cross algorithms have finite termination for linear programming problems. Similar results were made in convex quadratic programming by Todd and Terlaky. It has been applied to linear-fractional programming, quadratic-programming problems, and linear complementarity problems.
Outside of combinatorial optimization, OM theory also appears in convex minimization in Rockafellar's theory of "monotropic programming" and related notions of "fortified descent". Similarly, matroid theory has influenced the development of combinatorial algorithms, particularly the greedy algorithm. More generally, a greedoid is useful for studying the finite termination of algorithms.