Oriented matroid

From Wikipedia, the free encyclopedia

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., 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.^[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.

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.

A signed set, $X$ , combines a set of objects $\underline {X}$ 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 $\underline {X}=X^{+}\cup X^{-}$ is called the support of $X$ .

The empty signed set, $\emptyset$ 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^{+}$

Given an element of the support $x$ , we will write $x$ for a positive element and $-x$ for a negative element. In this way, a signed set is just adding negative signs to distinguish 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, and Cryptomorphism

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

Circuit axioms

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

(C0) $\emptyset \notin {\mathcal {C}}$

(C1) (symmetric) ${\mathcal {C}}=-{\mathcal {C}}$

(C2) (incomparable) ${\mbox{ for all }}X,Y\in {\mathcal {C}}{\mbox{ if }}\underline {X}\subseteq \underline {Y},{\mbox{ then }}X=Y{\mbox{ or }}X=-Y$

(C3) (weak elimination)
- $Z^{+}\subseteq (X^{+}\cup Y^{+})\setminus \{e\}{\mbox{ and }}$
- $Z^{-}\subseteq (X^{-}\cup Y^{-})\setminus \{e\}.$

Chirotope axioms

Let $E$ be as above. A chirotope of rank $r$ is a function $\chi :E^{r}\rightarrow \{-1,0,1\}$ that satisfies the following axioms.

(B0) $\chi$ is not identically zero

(B1) (alternating) For any permutation $\sigma$ and $x_{1},\dots ,x_{r}\in E$ , $\chi (x_{{\sigma (1)}},\dots ,x_{{\sigma (r)}})={\text{sign}}(\sigma )\chi (x_{1},\dots ,x_{r})$ , where ${\text{sign}}(\sigma )$ is the sign of the permutation.

(B2) (exchange) For any $x_{1},\dots ,x_{r},y_{1},\dots ,y_{r}\in E$ such that $\chi (y_{i},x_{2},\dots ,x_{r})\chi (y_{1},\dots ,y_{{i-1}},x_{1},y_{{i+1}},\dots ,y_{r})\geq 0$ for each $i$ , then we also have $\chi (x_{1},\dots ,x_{r})\chi (y_{1},\dots ,y_{r})\geq 0$ .

The term chirotope is derived from the mathematical notion of chirality, which is a concept abstracted from chemistry used to distinguish molecules.

Equivalence

Every chirotope of rank $r$ gives rise to a set of bases of a matroid on $E$ consisting of those $r$ -element subsets that $\chi$ assigns a nonzero value.^[5] The chirotope can then sign the circuits of that matroid. If $C$ is a circuit of the described matroid, then $C\subset \{x_{1},\dots ,x_{r},x_{{r+1}}\}$ where $\{x_{1},\dots ,x_{r}\}$ is a basis. Then $C$ can be signed with positive elements

$C^{+}=\{x_{i}:(-1)^{i}\chi (x_{1},\dots ,x_{{i-1}},\dots ,x_{{i+1}},\dots ,x_{{r+1}})=1\}$

and negative elements the compliment. 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 article: Directed graph

Linear algebra

If $\textstyle E$ is any finite subset of $\textstyle {\mathbb {R}}^{n}$ , then the set of minimal linearly dependent sets forms the circuit set of a matroid on $\textstyle E$ . To extend this construction to oriented matroids, for each circuit $\textstyle \{v_{1},\dots ,v_{m}\}$ there is a minimal linear dependence

$\sum _{{i=1}}^{m}\lambda _{i}v_{i}=0$

with $\textstyle \lambda _{i}\in {\mathbb {R}}$ . Then the signed circuit $\textstyle X=\{X^{+},X^{-}\}$ has positive elements $\textstyle X^{+}=\{v_{i}:\lambda _{i}>0\}$ and negative elements $\textstyle X^{-}=\{v_{i}:\lambda _{i}<0\}$ . The set of all such $\textstyle X$ forms the set of signed circuits of an oriented matroid on $\textstyle E$ . Oriented matroids that can be realized this way are called representable.

Given the same set of vectors $E$ , we can define the same oriented matroid with a chirotope $\chi :E^{r}\rightarrow \{-1,0,1\}$ . For any $x_{1},\dots ,x_{r}\in E$ let

$\chi (x_{1},\dots ,x_{r})={\text{sign}}(\det(x_{1},\dots ,x_{r}))$

where the right hand side of the equation is the sign of the determinant. Then $\chi$ is the chirotope of the same oriented matroid on the set $E$ .

Convex polytope

Main article: Convex polytope

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.^[6] 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.^[7] 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 $\chi :E^{r}\rightarrow \{-1,0,1\}$ . If we consider a list of elements of $x_{1},\dots ,x_{k}\in E$ as a cyclic permutation then we define ${\text{sign}}(x_{1},\dots ,x_{k})$ to be the sign of the associated permutation. If $\chi ^{*}:E^{{|E|-r}}\rightarrow \{-1,0,1\}$ is defined as

$\chi ^{*}(x_{1},\dots ,x_{r})\mapsto \chi (x_{{r+1}},\dots ,x_{{|E|}}){\text{sign}}(x_{1},\dots ,x_{r},x_{{r+1}},\dots ,x_{{|E|}}),$

then $\chi ^{*}$ is the chirotope of the unique orthogonal dual oriented matroid.^[8]

Topological representation

This is an example of a pseudoline arrangement that is distinct from any line arrangement.

Oriented matroids are abstractions of geometric constructs. The exact constructs are arrangements of pseudospheres. A $d$ -dimensional pseudosphere is an embedding of $e:S^{d}\hookrightarrow S^{{d+1}}$ such that there exists a homeomorphism $h:S^{{d+1}}\rightarrow S^{{d+1}}$ so that $h\circ e$ embeds $S^{d}$ as an equator of $S^{{d+1}}$ . In this sense a pseudosphere is just a tame sphere (as opposed to wild spheres). A pseudosphere arrangement in $S^{d}$ is a collection of pseudospheres that intersect along pseudospheres. The Folkman Lawrence topological representation theorem states that every oriented matroid of rank $d+1$ can be obtained from a pseudosphere arrangement in $S^{d}$ .^[9]

Geometry

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.

Optimization

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.

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". ^[12]

The theory of oriented matroids has led to break-throughs 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.^[13] It has been applied to linear-fractional programming^[14] quadratic-programming problems, and linear complementarity problems.^[15]^[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 1-3. Bokowski, Chapter 1. Ziegler, Chapter 7.
↑ Björner et alia, Chapters 1-3. Bokowski, Chapters 1-4.
↑ 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.
↑ Björner et alia, Chapter 7.9.
↑ Björner et alia, Chapter 3.5
↑ Björner et alia, Chapter 7.9
↑ Björner et alia, Chapter 3.4
↑ Björner et alia, Chapter 3.6
↑ Björner et alia, Chapter 5.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.
↑ Rockafellar, R. T. (1969). $R^{N}$ . In R. C. Bose and T. A. Dowling. Combinatorial Mathematics and its Applications. The University of North Carolina Monograph Series in Probability and Statistics (4). Chapel Hill, North Carolina: University of North Carolina Press. pp. 104–127. MR 278972. PDF reprint.
↑ Björner et alia, Chapters 8-9. Fukuda and Terlaky. Compare Ziegler.
↑ Illés, Szirmai & Terlaky (1999)
↑ Fukuda & Terlaky (1997)
↑ Fukuda & Terlaky (1997, p. 385)
↑ Fukuda & Namiki (1994, p. 367)
↑ Rockafellar 1984 and 1998.
↑ Lawler. Rockafellar 1984 and 1998.

External links

This article is issued from Wikipedia. The text is available under the Creative Commons Attribution/Share Alike; additional terms may apply for the media files.