 Oriented matroid

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).^{[1]} In comparison, an ordinary (i.e., nonoriented) 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.^{[2]} ^{[3]}
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).^{[4]} 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.
Contents
Axiomatizations
Like ordinary matroids, several equivalent systems of axioms exist. (Such structures that possess multiple equivalent axiomatizations are called cryptomorphic.)
Circuit axioms
Signed sets
Before we list the circuit axioms a few terms must be defined.
 A signed set, X, combines a set of objects with a partition of that set into two subsets: X ^{+} and X ^{−} .
 The members of X ^{+} are called the positive elements; members of X ^{−} are the negative elements.
 The set is called the support of X.
 The empty signed set, is defined in the obvious way.
 The signed set Y is the opposite of X, i.e., Y = − X, if and only if Y ^{+} = X ^{−} and Y ^{−} = X ^{+}
The concept of signed sets is key to distinguishing oriented from ordinary matroids.
Axioms
Let E be any set. We refer to E as the ground set. Let be a collection of signed sets, each of which is supported by a subset of E. If the following axioms hold for , then equivalently is the set of signed circuits for an oriented matroid on E.
 (C0)
 (C1) (symmetric)
 (C2) (incomparable)
 (C3) (weak elimination)
Examples
Oriented matroids are often introduced (e.g., Bachem and Kern) as an abstraction for directed graphs or systems of linear inequalities. Thus, it may be helpful to first be knowledgeable of the structures for which oriented matroids are an abstraction. Several of these topics are listed below.
Directed graphs
Main article: Directed graphSee also: Flow networkLinear optimization
Main articles: Linear programming and Crisscross algorithmSee also: Simplex algorithm and Bland's ruleThe 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 studies of such sign patterns in "Tucker tableaux".^{[5]} Much of the theory of oriented matroids (OMs) was developed to study the combinatorial invariants of linearoptimization, particularly those visible in the basisexchange pivoting of the simplex algorithm.^{[6]}
Convex polytope
Main article: Convex polytopeFor example, Ziegler introduces oriented matroids via convex polytopes.
Results
Algebra: duality and polarity
See also: Matroid#Matroid duality, Duality (projective geometry), Pole and polar, Duality (mathematics), and Involution (mathematics)Oriented matroids have a satisfying theory of duality.^{[7]}
Geometry
Main article: Combinatorial geometrySee also: Convex polytope and AntimatroidThe 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).^{[8]} 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.^{[9]}
Rank 3 oriented matroids are equivalent to arrangements of pseudolines.^{[10]}
Similarly, matroid theory is useful for developing combinatorial notions of dimension, rank, etc.
In combinatorial convexity, the notion of an antimatroid is also useful.
Optimization
The theory of oriented matroids (OM) has led to breakthroughs in combinatorial optimization. In linear programming, OM theory was the language in which Bland formulated his pivoting rule by which the simplex algorithm avoids cycles; similarly, OM theory was used by Terlakey and Zhang to prove that their crisscross algorithms have finite termination for linear programming problems. Similar results were made in convex quadratic programming by Todd and Terlaky.^{[11]} The crisscross algorithm is often studied using the theory of oriented matroids (OMs), which is a combinatorial abstraction of linearoptimization theory.^{[6]}^{[12]}
Historically, an OM algorithm for quadraticprogramming problems and linearcomplementarity problems was published by Michael J. Todd, before Terlaky and Wang published their crisscross algorithms.^{[6]}^{[13]} However, Todd's pivotingrule cycles on nonrealizable oriented matroids (and only on nonrealizable oriented matroids). Such cycling does not stump the OM crisscross algorithms of Terlaky and Wang, however.^{[6]} There are orientedmatroid variants of the crisscross algorithm for linear programming, for quadratic programming, and for the linearcomplementarity problem.^{[6]}^{[6]}^{[14]}^{[14]} Oriented matroid theory is used in many areas of optimization, besides linear programming. OM theory has been applied to linearfractional programming^{[15]} quadraticprogramming problems, and linear complementarity problems.^{[14]}^{[16]}^{[17]}
Outside of combinatorial optimization, OM theory also appears in convex minimization in Rockafellar's theory of "monotropic programming" and related notions of "fortified descent".^{[18]}
Similarly, matroid theory has influenced the development of combinatorial algorithms, particularly the greedy algorithm.^{[19]} More generally, a greedoid is useful for studying the finite termination of algorithms.
References
 ^ Rockafellar 1969. Björner et alia, Chapters 13. Bokowski, Chapter 1. Ziegler, Chapter 7.
 ^ Björner et alia, Chapters 13. Bokowski, Chapters 14.
 ^ Because matroids and oriented matroids are abstractions of other mathematical abstractions, nearly all the relevant books are written for mathematical scientists rather than for the general public. For learning about oriented matroids, a good preparation is to study the textbook on linear optimization by Nering and Tucker, which is infused with orientedmatroid ideas, and then to proceed to Ziegler's lectures on polytopes.
 ^ Björner et alia, Chapter 7.9.
 ^ (Rockafellar 1969):
Rockafellar, R. T. (1969). "The elementary vectors of a subspace of R^{N} (1967)". In R. C. Bose and T. A. Dowling. Combinatorial Mathematics and its Applications. The University of North Carolina Monograph Series in Probability and Statistics. Chapel Hill, North Carolina: University of North Carolina Press.. pp. 104–127. MR278972. PDF reprint. http://www.math.washington.edu/~rtr/papers/rtrElemVectors.pdf.
 ^ ^{a} ^{b} ^{c} ^{d} ^{e} ^{f} Björner, Anders; Las Vergnas, Michel; Sturmfels, Bernd; White, Neil; Ziegler, Günter (1999). "10 Linear programming". Oriented Matroids. Cambridge University Press. pp. 417–479. doi:10.1017/CBO9780511586507. ISBN 9780521777506. MR1744046. http://ebooks.cambridge.org/ebook.jsf?bid=CBO9780511586507.
 ^ In orientedmatroid theory, duality differs from polarity; see Bachem and Kern, Chapters 5.11, 6, 7.2.
 ^ Bachem and Kern, Chapters 1–2 and 4–9. Björner et alia, Chapters 1–8. Ziegler, Chapter 7–8. Bokowski, Chapters 7–10.
 ^ Bachem and Wanka, Chapters 1–2, 5, 7–9. Björner et alia, Chapter 8.
 ^ Björner et alia, Chapter 6.
 ^ Björner et alia, Chapters 89. Fukuda and Terlaky. Compare Ziegler.
 ^ 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 studies of such sign patterns in "Tucker tableaux". (Rockafellar 1969):
Rockafellar, R. T. (1969). "The elementary vectors of a subspace of R^{N} (1967)". In R. C. Bose and T. A. Dowling. Combinatorial Mathematics and its Applications. The University of North Carolina Monograph Series in Probability and Statistics. Chapel Hill, North Carolina: University of North Carolina Press.. pp. 104–127. MR278972. PDF reprint. http://www.math.washington.edu/~rtr/papers/rtrElemVectors.pdf.
 ^ Todd, Michael J. (1985). "Linear and quadratic programming in oriented matroids". Journal of Combinatorial Theory. Series B 39 (2): 105–133. doi:10.1016/00958956(85)900425. MR811116.
 ^ ^{a} ^{b} ^{c} Fukuda & Terlaky (1997)
 ^ Illés, Szirmai & Terlaky (1999)
 ^ Fukuda & Terlaky (1997, p. 385)
 ^ Fukuda & Namiki (1994, p. 367)
 ^ Rockafellar 1984 and 1998.
 ^ Lawler. Rockafellar 1984 and 1998.
Further reading
Books
 A. Bachem and W. Kern. Linear Programming Duality: An Introduction to Oriented Matroids. Universitext. SpringerVerlag, 1992.
 Björner, Anders; Las Vergnas, Michel; Sturmfels, Bernd; White, Neil; Ziegler, Günter (1999). Oriented Matroids. Cambridge University Press. ISBN 9780521777506.
 Bokowski, Jürgen (2006). Computational oriented matroids. Cambridge University Press. ISBN 9780521849302.
 Eugene Lawler (2001). Combinatorial Optimization: Networks and Matroids. Dover. ISBN 0486414531.
 Evar D. Nering and Albert W. Tucker, 1993, Linear Programs and Related Problems, Academic Press. (elementary)
 R. T. Rockafellar. Network Flows and Monotropic Optimization, WileyInterscience, 1984 (610 pages); republished by Athena Scientific of Dimitri Bertsekas, 1998.
 Ziegler, Günter M., Lectures on Polytopes, SpringerVerlag, New York, 1994.
 RichterGebert, J. and G. Ziegler, Oriented Matroids, In Handbook of Discrete and Computational Geometry, J. Goodman and J.O'Rourke, (eds.), CRC Press, Boca Raton, 1997, p. 111132.
Articles
 A. Bachem, A. Wanka, Separation theorems for oriented matroids, Discrete Math. 70 (1988) 303—310.
 R.G. Bland, New finite pivoting rules for the simplex method, Math. Oper. Res. 2 (1977) 103–107.
 Jon Folkman and James Lawrence, Oriented Matroids, J. Combin. Theory Ser. B 25 (1978) 199—236.
 Fukuda, Komei; Terlaky, Tamás (1997). "Crisscross methods: A fresh view on pivot algorithms". Mathematical Programming: Series B (Amsterdam: NorthHolland Publishing Co.) 79 (Papers from the 16th International Symposium on Mathematical Programming held in Lausanne, 1997): pp. 369–395. doi:10.1016/S00255610(97)000622. MR1464775. http://www.cas.mcmaster.ca/~terlaky/files/crisscross.ps.
 Fukuda, Komei; Namiki, Makoto (March 1994). "On extremal behaviors of Murty's least index method". Mathematical Programming 64 (1): 365–370. doi:10.1007/BF01582581. MR1286455.
 Illés, Tibor; Szirmai, Ákos; Terlaky, Tamás (1999). "The finite crisscross method for hyperbolic programming". European Journal of Operational Research 114 (1): 198–214. doi:10.1016/S03772217(98)000496. ISSN 03772217. PDF preprint. http://www.sciencedirect.com/science/article/B6VCT3W3DFHBM/2/4b0e2fcfc2a71e8c14c61640b32e805a.
 Fukuda, Komei; Terlaky, Tamás (1997). Thomas M. Liebling and Dominique de Werra. ed. "Crisscross methods: A fresh view on pivot algorithms". Mathematical Programming: Series B (Amsterdam: NorthHolland Publishing Co.) 79 (Papers from the 16th International Symposium on Mathematical Programming held in Lausanne, 1997): 369–395. doi:10.1016/S00255610(97)000622. MR1464775. Postscript preprint.
 R. T. Rockafellar. The elementary vectors of a subspace of R^{n}, in Combinatorial Mathematics and its Applications, R. C. Bose and T. A. Dowling (eds.), Univ. of North Carolina Press, 1969, 104127.
 Roos, C. (1990). "An exponential example for Terlaky's pivoting rule for the crisscross simplex method". Mathematical Programming. Series A 46 (1): 79. doi:10.1007/BF01585729. MR1045573.
 Terlaky, T. (1985). "A convergent crisscross method". Optimization: A Journal of Mathematical Programming and Operations Research 16 (5): 683–690. doi:10.1080/02331938508843067. ISSN 02331934. MR798939.
 Terlaky, Tamás (1987). "A finite crisscross method for oriented matroids". Journal of Combinatorial Theory. Series B 42 (3): 319–327. doi:10.1016/00958956(87)900499. ISSN 00958956. MR888684.
 Terlaky, Tamás; Zhang, Shu Zhong (1993). "Pivot rules for linear programming: A Survey on recent theoretical developments". Annals of Operations Research (Springer Netherlands) 46–47 (Degeneracy in optimization problems): 203–233. doi:10.1007/BF02096264. ISSN 02545330. MR1260019. PDF file of (1991) preprint.
 Michael J. Todd, Linear and quadratic programming in oriented matroids, J. Combin. Theory Ser. B 39 (1985) 105—133.
 Wang, Zhe Min (1987). "A finite conformalelimination free algorithm over oriented matroid programming". Chinese Annals of Mathematics (Shuxue Niankan B Ji). Series B 8 (1): 120–125. ISSN 02529599. MR886756.
On the web
 Ziegler, Günter (1998). "Oriented Matroids Today". The Electronic Journal of Combinatorics. http://www.combinatorics.org/Surveys/ds4.pdf.
 Malkevitch, Joseph. "Oriented Matroids: The Power of Unification". Feature Column. American Mathematical Society. http://www.ams.org/featurecolumn/archive/oriented1.html. Retrieved 20090914.
External links
Categories: Matroid theory
 Convex geometry
 Combinatorics
 Discrete geometry
 Dimension
 Duality theories
 Oriented matroids
Wikimedia Foundation. 2010.