Oriented matroid

{{Short description|Abstraction of ordered linear algebra}} [[File:max-flow min-cut example.svg|frame|right|Oriented-matroid theory allows a combinatorial approach to the max-flow min-cut theorem. A network with the value of flow equal to the capacity of an s-t cut]] An '''oriented matroid''' is a mathematical structure that abstracts the properties of directed graphs, vector arrangements over ordered fields, and hyperplane arrangements over ordered fields.<ref>R. Tyrrell Rockafellar 1969. Anders Björner et alia, Chapters 1-3. Jürgen Bokowski, Chapter 1. Günter M. Ziegler, Chapter 7.</ref> 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''.<ref>Björner et alia, Chapters 1-3. Bokowski, Chapters 1-4.</ref> <ref>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 oriented-matroid ideas, and then to proceed to Ziegler's lectures on polytopes.</ref>

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).<ref>Björner et alia, Chapter 7.9.</ref> 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.

== History == The first appearance of oriented matroids was in a 1966 article by George J. Minty and was confined to regular matroids.<ref>G. J. Minty (1966), On the axiomatic foundations of the theories of directed linear graphs, electrical networks, and network programming. ''J. Math. Mech.'' 15: 485–520. Reprinted in D. R. Fulkerson, ed., ''Graph Theory'', M.A.A. Study No. 12, Mathematical Association of America. </ref>

Subsequently R.T. Rockafellar (1969) suggested the problem of generalizing Minty's concept to real vector spaces. His proposal helped lead to the development of the general theory.

== Background == {{main|Signed set}} 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''.

* A ''signed set'', <math>X</math>, combines a set of objects, <math>\underline{X}</math>, with an ordered ''bipartition'' <math>(X^+,X^-)</math> of that set into two disjoint subsets: <math>X^+</math> and <math>X^-</math>. : The members of <math>X^+</math> are called the ''positive elements''; members of <math>X^-</math> are the ''negative elements''. * The set <math>\underline{X} = X^+ \cup X^-</math> is called the ''support'' of <math>X</math>. * The ''empty signed set'', <math> \empty </math>, is defined as the empty set <math> \underline{\empty} </math> combined with an (ordered) bipartition of it into two empty sets: <math>\emptyset^+</math> and <math>\emptyset^-</math>. * The signed set <math>Y</math> is the ''opposite'' of <math>X</math>, written <math>Y = -X</math>, if <math>Y^+ = X^-</math> and <math>Y^- = X^+.</math>

Given an element <math>x</math> of the support, we will write <math>x</math> for a positive element and <math>-x</math> for a negative element. In this way, a signed set is just adding negative signs to distinguished elements. This will make sense as a "direction" only when we consider orientations of larger structures. Then the sign of each element will encode its direction relative to this orientation.

== Axiomatizations == {{See also|Matroid#Bases and circuits|Axiomatic system|Cryptomorphism}}

Like ordinary matroids, several equivalent systems of axioms exist. (Such structures that possess multiple equivalent axiomatizations are called cryptomorphic.)

=== Circuit axioms === Let <math>E</math> be any set. We refer to <math>E</math> as the ''ground set''. Let <math>\mathcal{C}</math> be a collection of ''signed sets'', each of which is ''supported'' by a subset of <math>E</math>. If the following axioms hold for <math>\mathcal{C}</math>, then equivalently <math>\mathcal{C}</math> is the set of ''signed circuits'' for an ''oriented matroid'' on <math>E</math>.

* (C0) <math>\empty \notin \mathcal{C}</math> * (C1) (symmetric) <math>\text{ For all } X \in \mathcal{C},~ -\!X \in \mathcal{C}.</math> * (C2) (incomparable) <math>\text{ For all } X,Y \in \mathcal{C},~~ \text{ if } \underline X\subseteq \underline Y\text{ then } (X=Y \text{ or } X = -Y).</math> * (C3) (weak elimination) <math>\text{ For all } X,Y \in \mathcal{C}, X \neq -Y \text{ with an } e \in X^+ \cap Y^- \text{ there is a } Z \in \mathcal{C} \text{ such that }</math> ** <math> Z^+ \subseteq (X^+ \cup Y^+)\setminus\{e\} \text{ and }</math> ** <math> Z^- \subseteq (X^- \cup Y^-)\setminus\{e\}.</math>

=== Vector Axioms === The ''composition'' of signed sets <math>X</math> and <math>Y</math> is the signed set <math>X\circ Y</math> defined by <math>\underline{X\circ Y}= {\underline X} \cup {\underline Y}</math>, <math>(X\circ Y)^+ = X^+ \cup \left(Y^+ \setminus X^-\right)</math>, and <math>(X\circ Y)^- = X^- \cup \left(Y^- \setminus X^+\right)</math>. The ''vectors'' of an oriented matroid are the compositions of circuits. The vectors <math>\mathcal V</math> of an oriented matroid satisfy the following axioms:

* <math>\emptyset \in \mathcal V</math> * <math>\mathcal V = -\mathcal V</math> * for all <math>X, Y\in \mathcal V</math>, <math>X\circ Y \in \mathcal V</math> * for all <math>X, Y\in \mathcal V</math>, <math>e\in X^+ \cap Y^- </math>and <math>f\in (\underline X \setminus \underline Y)\cup (\underline Y \setminus \underline X) \cup (X^+\cap Y^+) \cup (X^- \cap Y^-)</math> , there is a <math>Z\in \mathcal V</math>, such that ** <math>Z^+ \subset X^+ \cup Y^+ \setminus e</math>, ** <math>Z^- \subset X^- \cup Y^- \setminus e</math>, and ** <math>f\in \underline Z</math>.

The ''covectors'' of an oriented matroid are the vectors of its dual oriented matroid.

=== Chirotope axioms === Let <math>E</math> be as above. For each non-negative integer <math>r</math>, a ''chirotope of rank <math>r</math>'' is a function <math>\chi\colon E^r\to \{-1,0,1\}</math> that satisfies the following axioms:

* (B0) ''(non-trivial)'': <math>\chi</math> is not identically zero * (B1) ''(alternating)'': For any permutation <math>\sigma</math> and <math>x_1,\dots,x_r\in E</math>, <math>\chi\left(x_{\sigma(1)},\dots,x_{\sigma(r)}\right)=\operatorname{sgn}(\sigma)\chi\left(x_1,\dots,x_r\right)</math>, where <math>\operatorname{sgn}(\sigma)</math> is the sign of the permutation. * (B2) ''(exchange)'': For any <math>x_1,\dots,x_r,y_1,\dots,y_r\in E</math> such that <math>\chi(y_i,x_2,\dots,x_r)\chi(y_1,\dots,y_{i-1},x_1,y_{i+1},\dots,y_r)\ge 0</math> for each <math>i</math>, then we also have <math> \chi\left(x_1,\dots,x_r\right)\chi\left(y_1,\dots,y_r\right)\ge0</math>.

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 <math>r</math> gives rise to a set of bases of a matroid on <math>E</math> consisting of those <math>r</math>-element subsets that <math>\chi</math> assigns a nonzero value.<ref>Björner et alia, Chapter 3.5</ref> The chirotope can then sign the circuits of that matroid. If <math> C</math> is a circuit of the described matroid, then <math>C\subset \{x_1,\dots,x_r,x_{r+1}\}</math> where <math>\{x_1,\dots,x_r\}</math> is a basis. Then <math>C</math> can be signed with positive elements :<math>C^+=\{x_i: (-1)^i\chi(x_1,\dots,x_{i-1},x_{i+1},\dots,x_{r+1})=1\}</math> 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 === {{Main|Directed graph}} {{See also|Flow network}} 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 <math>\textstyle \underline{X}</math> is the standard set of edges in a minimal cycle. We go along the cycle in the clockwise or anticlockwise direction assigning those edges whose orientation agrees with the direction to the positive elements <math>\textstyle X^+</math> and those edges whose orientation disagrees with the direction to the negative elements <math>\textstyle X^-</math>. If <math>\textstyle \mathcal{C} </math> is the set of all such <math>\textstyle X</math>, then <math>\textstyle \mathcal{C} </math> is the set of signed circuits of an oriented matroid on the set of edges of the directed graph.

right|100px|thumb|A directed graph If we consider the directed graph on the right, then we can see that there are only two (graph) circuits, namely <math>\textstyle \{(1,2),(1,3),(3,2)\}</math> and <math>\textstyle \{(3,4),(4,3)\}</math>. Then there are only four possible signed circuits corresponding to clockwise and anticlockwise orientations, namely <math>\textstyle\{ (1,2),-(1,3),-(3,2)\}</math>, <math>\textstyle\{ -(1,2),(1,3),(3,2)\}</math>, <math>\textstyle\{(3,4),(4,3)\}</math>, and <math>\textstyle\{-(3,4),-(4,3)\}</math>. These four sets form the set of signed circuits of an oriented matroid on the set <math>\textstyle \{ (1,2),(1,3),(3,2),(3,4),(4,3)\}</math>.

This is opposed to the ordinary directed graphic matroid for the same graph, whose only circuit is <math>\textstyle\{(3,4),(4,3)\}</math>, as the other edges cannot form a directed cycle without flipping the direction of some of them.

=== Linear algebra === {{See also|Matroid#Matroids from linear algebra}} If <math>\textstyle E</math> is any finite subset of <math>\textstyle\mathbb{R}^n</math>, then the set of minimal linearly dependent sets forms the circuit set of a matroid on <math>\textstyle E</math>. To extend this construction to oriented matroids, for each circuit <math>\textstyle \{v_1,\dots,v_m\}</math> there is a minimal linear dependence :<math>\sum_{i=1}^m \lambda_i v_i =0</math> with <math>\textstyle \lambda_i\in\mathbb{R}</math>. Then the signed circuit <math>\textstyle X=\{X^+,X^-\}</math> has positive elements <math>\textstyle X^+=\{v_i:\lambda_i>0\}</math> and negative elements <math>\textstyle X^-=\{v_i:\lambda_i<0\}</math>. The set of all such <math>\textstyle X</math> forms the set of signed circuits of an oriented matroid on <math>\textstyle E</math>. Oriented matroids that can be realized this way are called representable.

Given the same set of vectors <math>E</math>, we can define the same oriented matroid with a chirotope <math>\chi:E^r\rightarrow\{-1,0,1\}</math>. For any <math>x_1,\dots,x_r\in E</math> let :<math>\chi(x_1,\dots,x_r)=\operatorname{sgn}(\det(x_1,\dots,x_r))</math> where the right hand side of the equation is the sign of the determinant. Then <math> \chi</math> is the chirotope of the same oriented matroid on the set <math>E</math>.

=== Hyperplane arrangements === {{Main|Arrangement of hyperplanes}}A real hyperplane arrangement <math>\mathcal A = \{H_1, \ldots, H_n\}</math> is a finite set of hyperplanes in <math>\R^d </math>, each containing the origin. By picking one side of each hyperplane to be the positive side, we obtain an arrangement of half-spaces. A half-space arrangement breaks down the ambient space into a finite collection of cells, each defined by which side of each hyperplane it lands on. That is, assign each point <math>x\in \R^d</math>to the signed set <math>X = (X^+, X^-)</math>with <math>i \in X^+</math> if <math>x</math> is on the positive side of <math>H_i</math>and <math>i\in X^-</math>if <math>x</math> is on the negative side of <math>H_i</math>. This collection of signed sets defines the set of covectors of the oriented matroid, which are the vectors of the dual oriented matroid.<ref>* {{cite book | last1=Björner | first1=Anders | author-link1=Anders Björner | last2=Las Vergnas | first2=Michel | author2-link = Michel Las Vergnas | last3=Sturmfels | first3=Bernd | author-link3=Bernd Sturmfels | last4=White | first4=Neil | last5=Ziegler | first5=Günter | author-link5=Günter M. Ziegler | title=Oriented Matroids | publisher=Cambridge University Press | year=1999 | isbn=978-0-521-77750-6 | zbl=0944.52006 | series=Encyclopedia of Mathematics and Its Applications | volume=46 | edition=2nd |oclc=776950824}}</ref>

Each rank-3 oriented matroid is equivalent to an arrangement of pseudolines, and each oriented matroid which is also ''uniform'' is equivalent to a '''simple''' pseudoline arrangement (where every 2 lines cross exactly once, and no 3 lines cross at the same point). Tools for dealing with one form can therefore be used to analyze its equivalent form for either study.<ref name="Felsner"> {{cite book | last1 = Felsner | first1 = Stefan | last2 = Goodman | first2 = Jacob E. | title = Handbook of Discrete and Computational Geometry | edition = 3rd | date = 2017 | publisher = Chapman and Hall/CRC | chapter = Pseudoline Arrangements | chapter-url = https://www.csun.edu/~ctoth/Handbook/chap5.pdf | isbn = 9781315119601 }} </ref>

=== Convex polytope === {{Main|Convex polytope}} Günter M. Ziegler introduces oriented matroids via convex polytopes.

== Results ==

=== 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.<ref>Björner et alia, Chapter 7.9</ref> In this sense, oriented matroids is a much stricter formalization than regular matroids.

=== Duality === {{See also|Matroid#Duality}} Just as a matroid has a unique duals, an oriented matroid has a unique dual, often called its "orthogonal dual". What this means is that 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.<ref>Björner et alia, Chapter 3.4</ref>

To see why orthogonality is necessary for uniqueness one needs only to look to the digraph example above. We know that for planar graphs the dual of the circuit matroid is the circuit matroid of the graph's planar dual. Thus there are as many different dual pairs of oriented matroids based on the matroid of the graph as there are ways to orient the graph and in a corresponding way its dual.

To see the explicit construction of this unique orthogonal dual oriented matroid, consider an oriented matroid's chirotope <math>\chi:E^r\rightarrow\{-1,0,1\}</math>. If we consider a list of elements of <math> x_1,\dots,x_k \in E</math> as a cyclic permutation then we define <math>\operatorname{sgn}(x_1,\dots,x_k)</math> to be the sign of the associated permutation. If <math>\chi^*:E^{|E|-r}\rightarrow\{-1,0,1\}</math> is defined as :<math>\chi^*(x_1,\dots,x_r)\mapsto \chi(x_{r+1},\dots,x_{|E|})\operatorname{sgn}(x_1,\dots,x_r,x_{r+1},\dots,x_{|E|}),</math> then <math>\chi^*</math> is the chirotope of the unique orthogonal dual oriented matroid.<ref>Björner et alia, Chapter 3.6</ref>

=== Topological representation === [[File:Pappos pseudo.svg|thumb|200px| This is an example of a pseudoline arrangement that is distinct from any line arrangement.]] Not all oriented matroids are representable—that is, not all have realizations as point configurations, or, equivalently, hyperplane arrangements. However, in some sense, all oriented matroids come close to having realizations as hyperplane arrangements. In particular, the '''Folkman–Lawrence topological representation theorem''' states that any oriented matroid has a realization as an arrangement of pseudospheres. A <math>d</math>-dimensional ''pseudosphere'' is an embedding of <math>e:S^d\hookrightarrow S^{d+1}</math> such that there exists a homeomorphism <math>h:S^{d+1}\rightarrow S^{d+1}</math> so that <math>h \circ e </math> embeds <math>S^d</math> as an equator of <math>S^{d+1}</math>. In this sense a pseudosphere is just a tame sphere (as opposed to wild spheres). A ''pseudosphere arrangement in <math>S^d</math>'' is a collection of pseudospheres that intersect along pseudospheres. Finally, the Folkman–Lawrence topological representation theorem states that every oriented matroid of rank <math>d+1</math> can be obtained from a pseudosphere arrangement in <math>S^d</math>.<ref>Björner et alia, Chapter 5.2</ref> It is named after Jon Folkman and Jim Lawrence, who published it in 1978.

=== Geometry === [[File:Shapley–Folkman lemma.svg|thumb|300px|alt=Minkowski addition of four line-segments. The left-hand pane displays four sets, which are displayed in a two-by-two array. Each of the sets contains exactly two points, which are displayed in red. In each set, the two points are joined by a pink line segment, which is the convex hull of the original set. Each set has exactly one point that is indicated with a plus symbol. In the top row of the two-by-two array, the plus symbol lies in the interior of the line segment; in the bottom row, the plus symbol coincides with one of the red points. This completes the description of the left-hand pane of the diagram. The right-hand pane displays the Minkowski sum of the sets, which is the union of the sums having exactly one point from each summand set; for the displayed sets, the sixteen sums are distinct points, which are displayed in red: The right-hand red sum points are the sums of the left-hand red summand points. The convex hull of the sixteen red points is shaded in pink. In the pink interior of the right-hand sumset lies exactly one plus-symbol, which is the (unique) sum of the plus-symbols from the right-hand side. The right-hand plus symbol is indeed the sum of the four plus-symbols from the left-hand sets, precisely two points from the original non-convex summand sets and two points from the convex hulls of the remaining summand sets.|A zonotope, which is a Minkowski sum of line segments, is a fundamental model for oriented matroids. The sixteen dark red points (on the right) form the Minkowski sum of the four non-convex sets (on the left), each of which consists of a pair of red points. Their convex hulls (shaded pink) contain plus signs (+): The right plus sign is the sum of the left plus signs.]] {{Main|Combinatorial geometry}} {{See also|Convex polytope|Zonotope}} The theory of oriented matroids has influenced the development of combinatorial geometry, especially the theory of convex polytopes, zonotopes, and configurations of vectors (equivalently, arrangements of hyperplanes).<ref>Bachem and Kern, Chapters 1–2 and 4–9. Björner et alia, Chapters 1–8. Ziegler, Chapter 7–8. Bokowski, Chapters 7–10.</ref> 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.<ref>Bachem and Wanka, Chapters 1–2, 5, 7–9. Björner et alia, Chapter 8.</ref>

=== Optimization === thumb|240px|In convex geometry, the simplex algorithm for linear programming is interpreted as tracing a path along the vertices of a convex polyhedron. Oriented matroid theory studies the combinatorial invariants that are revealed in the sign patterns of the matrices that appear as pivoting algorithms exchange bases. {{See also|Linear programming|Quadratic programming|Criss-cross algorithm}}

The development of an axiom system for 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". <ref>{{cite book |first=R. Tyrrell |last=Rockafellar |author-link=R. Tyrrell Rockafellar |chapter=The elementary vectors of a subspace of <math>R^N</math> (1967) |pages=104–127 |editor1=R. C. Bose |editor-link=R. C. Bose |editor2=Thomas A. Dowling |year=1969 |title=Combinatorial Mathematics and its Applications |series=The University of North Carolina Monograph Series in Probability and Statistics |location=Chapel Hill, North Carolina |publisher=University of North Carolina Press. |issue=4 |mr=278972 |chapter-url=http://www.math.washington.edu/~rtr/papers/rtr-ElemVectors.pdf |archive-date=2011-09-27 |access-date=2011-03-23 |archive-url=https://web.archive.org/web/20110927012757/http://www.math.washington.edu/~rtr/papers/rtr-ElemVectors.pdf |url-status=dead }}</ref>

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.<ref>Björner et alia, Chapters 8–9. Fukuda and Terlaky. Compare Ziegler.</ref> It has been applied to linear-fractional programming,<ref name="LF99Hyperbolic">{{harvtxt|Illés|Szirmai|Terlaky|1999}}</ref> quadratic-programming problems, and linear complementarity problems.<ref name="FukudaTerlaky">{{harvtxt|Fukuda|Terlaky|1997}}</ref><ref name="FTNamiki">{{harvtxt|Fukuda|Terlaky|1997|p=385}}</ref><ref name="FukudaNamiki">{{harvtxt|Fukuda|Namiki|1994|p=367}}</ref>

Outside of combinatorial optimization, oriented matroid theory also appears in convex minimization in Rockafellar's theory of "monotropic programming" and related notions of "fortified descent".<ref>Rockafellar 1984 and 1998.</ref> Similarly, matroid theory has influenced the development of combinatorial algorithms, particularly the greedy algorithm.<ref>Lawler. Rockafellar 1984 and 1998.</ref> More generally, a greedoid is useful for studying the finite termination of algorithms.

== References == {{Reflist|30em}}

== Further reading ==

=== Books === * {{cite book|first1=Achim |last1=Bachem |first2= Walter|last2= Kern|title=Linear Programming Duality: An Introduction to Oriented Matroids|series= Universitext|publisher= Springer-Verlag|year= 1992|mr=1230380|doi=10.1007/978-3-642-58152-6|isbn=978-3-540-55417-2 }} * {{cite book | last1=Björner | first1=Anders | author-link1=Anders Björner | last2=Las Vergnas | first2=Michel | author2-link = Michel Las Vergnas | last3=Sturmfels | first3=Bernd | author-link3=Bernd Sturmfels | last4=White | first4=Neil | last5=Ziegler | first5=Günter | author-link5=Günter M. Ziegler | title=Oriented Matroids | publisher=Cambridge University Press | year=1999 | isbn=978-0-521-77750-6 | zbl=0944.52006 | series=Encyclopedia of Mathematics and Its Applications | volume=46 | edition=2nd }} * {{cite book | last=Bokowski | first=Jürgen | title=Computational oriented matroids. Equivalence classes of matrices within a natural framework | publisher=Cambridge University Press | year=2006 | isbn=978-0-521-84930-2 | zbl=1120.52011}} * {{cite book | first=Eugene | last=Lawler | author-link=Eugene Lawler | title = Combinatorial Optimization: Networks and Matroids | year = 2001 | publisher = Dover | isbn = 978-0-486-41453-9 | zbl=1058.90057 }} * Evar D. Nering and Albert W. Tucker, 1993, ''Linear Programs and Related Problems'', Academic Press. (elementary) * {{cite book|first=R. Tyrrell|last= Rockafellar|author-link=R. Tyrrell Rockafellar|title=Network Flows and Monotropic Optimization|publisher= Wiley-Interscience|year= 1984}} republished by Athena Scientific of Dimitri Bertsekas, 1998. * {{cite book|first=Günter M.|last= Ziegler|author-link=Günter M. Ziegler | title=Lectures on Polytopes|publisher= Springer-Verlag|location= New York|year= 1994}} * {{cite book|first1=Jürgen|last1=Richter-Gebert|first2= Günter M.|last2= Ziegler|author2-link=Günter M. Ziegler | contribution=Oriented Matroids|title= Handbook of Discrete and Computational Geometry|url=https://archive.org/details/handbookofdiscre00jaco|url-access=registration|editor1-first= Jacob E.|editor1-last= Goodman|editor1-link=Jacob E. Goodman|editor2-first= Joseph |editor2-last=O'Rourke|publisher= CRC Press|location= Boca Raton|year= 1997| pages=[https://archive.org/details/handbookofdiscre00jaco/page/111 111–132]|isbn=9780849385247}}

=== Articles === * A. Bachem, A. Wanka, Separation theorems for oriented matroids, ''Discrete Math.'' 70 (1988) 303–310. * {{cite journal | last1=Bland | first1=Robert G. | authorlink1=Robert G. Bland | title=New finite pivoting rules for the simplex method | journal=Mathematics of Operations Research | volume=2 | issue=2 | date=1977 | pages=103–107 | doi=10.1287/moor.2.2.103}} * {{cite journal | first1=Jon | last1=Folkman | author-link1=Jon Folkman | first2=Jim | last2=Lawrence | author-link2=Jim Lawrence (mathematician) | title=Oriented Matroids | journal=Journal of Combinatorial Theory | series=Series B | volume=25 | issue=2 | date=October 1978 | pages=199–236 | doi=10.1016/0095-8956(78)90039-4 | doi-access=free}} * {{cite journal|first1=Komei|last1=Fukuda|author-link1=Komei Fukuda|first2=Tamás|last2=Terlaky|title=Criss-cross methods: A fresh view on pivot algorithms |journal=Mathematical Programming, Series B|volume=79|number=1–3|pages=369–395|editor1=Thomas M. Liebling |editor2=Dominique de Werra|publisher=North-Holland Publishing Co. |location=Amsterdam|year=1997|doi=10.1007/BF02614325|mr=1464775|s2cid=2794181|url=https://infoscience.epfl.ch/record/77270/files/10107_2007_Article_BF02614325.pdf}} * {{cite journal|last1=Fukuda|first1=Komei|author-link1=Komei Fukuda|last2=Namiki|first2=Makoto|title=On extremal behaviors of Murty's least index method|journal=Mathematical Programming|date=March 1994|pages=365–370|volume=64|doi=10.1007/BF01582581|mr=1286455|issue=1|s2cid=21476636}} * {{cite journal|title=The finite criss-cross method for hyperbolic programming|journal=European Journal of Operational Research|volume=114|pages=198–214|year=1999|issn=0377-2217|doi=10.1016/S0377-2217(98)00049-6|first1=Tibor|last1=Illés|first2=Ákos|last2=Szirmai|first3=Tamás|last3=Terlaky|url=http://www.cas.mcmaster.ca/~terlaky/files/dut-twi-96-103.ps.gz|issue=1|citeseerx=10.1.1.36.7090|archive-date=2011-07-21|access-date=2011-03-23|archive-url=https://web.archive.org/web/20110721062100/http://www.cas.mcmaster.ca/~terlaky/files/dut-twi-96-103.ps.gz|url-status=dead}} * R. Tyrrell Rockafellar (1969). The elementary vectors of a subspace of <math>R^n</math>, in ''Combinatorial Mathematics and its Applications'', R. C. Bose and T. A. Dowling (eds.), Univ. of North Carolina Press, pp. 104–127. * {{cite journal|last=Roos|first=C.|title=An exponential example for Terlaky's pivoting rule for the criss-cross simplex method|journal=Mathematical Programming|volume=46|year=1990|series=Series A|doi=10.1007/BF01585729|mr=1045573|issue=1|pages=79–84|s2cid=33463483}} * {{cite journal|last=Terlaky|first=T.|title=A convergent criss-cross method|journal=Optimization: A Journal of Mathematical Programming and Operations Research|volume=16|year=1985|pages=683–690|issn=0233-1934|doi=10.1080/02331938508843067|mr=798939|issue=5}} * {{cite journal | last1=Terlaky | first1=Tamás | authorlink1=Tamás Terlaky | title=A finite crisscross method for oriented matroids | volume=42 | date=1987 | pages=319–327 | journal=Journal of Combinatorial Theory| series=Series B | issn=0095-8956 | doi=10.1016/0095-8956(87)90049-9 |doi-access=free | mr=888684 | issue=3}} * {{cite journal|last1=Terlaky|first1=Tamás|last2=Zhang|first2=Shu Zhong|title=Pivot rules for linear programming: A Survey on recent theoretical developments|journal=Annals of Operations Research|volume=46–47|year=1993|number=1|pages=203–233|doi=10.1007/BF02096264|mr=1260019|citeseerx = 10.1.1.36.7658 |s2cid=6058077|issn=0254-5330}} * {{cite journal | last1=Todd | first1=Michael J. | title=Linear and quadratic programming in oriented matroids | journal=Journal of Combinatorial Theory | series=Series B | volume=39 | issue=2 | date=1985 | pages=105–133 | doi=10.1016/0095-8956(85)90042-5 | doi-access=free}} * {{cite journal|last=Wang|first=Zhe Min|title=A finite conformal-elimination free algorithm over oriented matroid programming|journal=Chinese Annals of Mathematics (Shuxue Niankan B Ji)|series=Series B|volume=8|year=1987|pages=120–125|issn=0252-9599|mr=886756|issue=1}}

=== On the web === *{{cite journal|url=https://www.combinatorics.org/ojs/index.php/eljc/article/view/DS4|title=Oriented Matroids Today|year=1998|last=Ziegler|first=Günter|author-link= Günter Ziegler|journal=The Electronic Journal of Combinatorics|pages=DS4: Sep 10–1998|doi=10.37236/25|url-access=subscription}}  *{{cite web|url=https://www.ams.org/featurecolumn/archive/oriented1.html|title=Oriented Matroids: The Power of Unification|last=Malkevitch|first=Joseph|work=Feature Column|publisher=American Mathematical Society|access-date=2009-09-14}}

Category:Oriented matroids