Beiträge zur Algebra und Geometrie Contributions to Algebra and Geometry Volume 38 (1997), No. 2, 249-260.

Oriented Matroids in Terms of Order Functions

Renate Jaritz

Friedrich-Schiller-Universität Jena, Mathematisches Institut, D-07740 Jena e-mail: jaritz@minet.uni-jena.de

Abstract. An oriented matroid of rank r is described as a pair M = (E, χ) where E is a nonempty set and χ is a chirotope of rank r on E. Relating the chirotope to an order function ω : (H, a, b) ↦ (H|ab) according to the rule (H|ab) = χ(P, a) · χ(P, b) where H is a hyperplane, P is a base of H and a and b are points with a, b ∈ E \ H, ω is shown to be harmonic and strict. The presented theorem gives a geometric characterization of oriented matroids in terms of order functions.

1. Introduction

Oriented matroids appear in varied shapes in different branches of mathematics. They are seen, for example, under the aspect of signed bases, of collections of covectors, as arrangements of pseudospheres, or collections of cocircuits. The concept of an oriented matroid generalizes combinatorial properties of point and vector configurations, directed graphs, arrangements of hyperplanes, convex polytopes, or linear programs, see [2, 3, 6].

The definition in terms of chirotopes, which is used in this paper, has been developed over a long period. An idea of base orientation was presented for the first time in [16]. Later the connection to oriented matroids was discovered, see [27]. The term chirotope was coined by Dress and Dreiding to reflect geometric aspects of chirality in organic chemistry. It turned out that chirotopes are equivalent to oriented matroids. At the same time Bokowski independently initiated a similar approach from a geometric point of view, especially using the Grassmann–Plücker relations. In the next years the concept of chirotopes was used by several authors to investigate and describe oriented matroids [7, 8, 11, 13]. Further developments, compare [26, 3, 6], finally led to the definition which is used here.

0138-4821/93 $ 2.50 \begin{matrix}c \\ ◯ \end{matrix} 1997 Heldermann Verlag

Starting from the description of oriented matroids in terms of chirotopes, we will develope their geometric characterization. The motivation comes from the following observation:

Let E be a finite set of points in ℝ^{n} forming a combinatorial geometry M of dimension d on E (i.e. a simple matroid of rank r = d + 1). The oriented matroid M of the points can be given by a list of signs that encodes the orientation of all ordered bases of M. If B = (x_{0}, …, x_{d}) ∈ E^{d+1} is some ordered base this sign can be computed with the help of the function χ : (x_{0}, …, x_{d}) ↦ sgn det(\overrightarrow{x_{0}x_{1}} … \overrightarrow{x_{0}x_{n}}) which is called the chirotope on E. There is a natural connection between orientation given by the function sgn det and the geometric order: Let H be a hyperplane spanned by the points p_{0}, …, p_{d−1}. Points a, b ∈ E \ H are in the same side respectively in distinct sides of H, if χ(p_{0}, …, p_{d−1}, a) = χ(p_{0}, …, p_{d−1}, b) respectively χ(p_{0}, …, p_{d−1}, a) = −χ(p_{0}, …, p_{d−1}, b). Thus there is a side-dividing or order function ω : (H, a, b) ↦ χ(p_{0}, …, p_{d−1}, a) · χ(p_{0}, …, p_{d−1}, b) which describes orientation and hence the oriented matroid.

This idea will be transferred to matroids and oriented matroids in general, which are not necessarily representable as point configurations. The concept of order functions was introduced by Sperner [31], who developed the theory for desarguesian affine and projective spaces. Karzel transferred it to non-desarguesian spaces, see [20, 21] and compare [23, 24] for various models and concepts of geometric ordering. There exist also several geometric settings and descriptions of orientation, see [4, 5, 10, 15, 28], but no attention was paid there to discrete or finite structures.

Transferring the theory of order functions to matroids, or, more precisely, to combinatorial geometries, discovers new aspects of oriented matroids. Differently to the idea of the Topological Representation Theorem of Folkman and Lawrence [14] oriented matroids themselves are seen here as geometries: They are incidence structures equipped with an order function of certain kind. For the rank 3 case this relationship is pointed out in [19]. The investigations there base on the algebraic methods from [12], essentially utilizing the theory of Tutte groups. Independently from this results we prove that, for matroids of any rank, there is a bijection between chirotopes and special order functions. The method developed here discovers new aspects of describing the relations between matroids and oriented matroids and provides new tools for investigating the structure of oriented matroids in general as well as various examples. So it would be interesting to look for new ideas concerning the cube problem of Las Vergnas [9] by using order functions.

In the second section of this paper we start with the definitions of matroids and of oriented matroids in terms of chirotopes and continue to compile further facts. Next we present the basic ideas about order functions on (simple) matroids and derive characteristic properties of such order functions which are generated by chirotopes. Section four concerns with the reverse approach, the generation of a chirotope from a certain order function. Combining both directions we get our final result, which gives a characterization of oriented matroids in terms of order functions.

2. Preliminaries – Definitions and facts

Matroids, as introduced in 1935 by Whitney, can be considered as an abstraction of linear dependences of vector configurations in finite-dimensional vector spaces, see [29, 33]. This motivates the following definition of matroids in terms of bases:

Definition 1. A matroid is a pair M = (E, B), where E is a nonempty set and B is a nonempty family of finite subsets of E (called bases of M) that satisfies: (B) For all B_{1}, B_{2} ∈ B and e ∈ B_{1} \B_{2}, there exists an f ∈ B_{2} \B_{1} such that (B_{1} \e)∪f ∈ B.

It follows that all bases of M do have the same cardinality r, which is called the rank of the matroid. In this paper we always assume r ≥ 3.

The information about the matroid structure can be encoded in a function μ : E^{r} → {0, 1} with certain properties by setting μ(x_{1}, …, x_{r}) = 1 if {x_{1}, …, x_{r}} ∈ B and otherwise μ(x_{1}, …, x_{r}) = 0. Thus a matroid equivalently is quoted as M = (E, μ).

Oriented matroids can be considered as a combinatorial model of the determinant values on vector configurations. This motivates the following definition in terms of chirotopes, see [9]:

Definition 2. Let E be a set and r ∈ ℕ with 3 ≤ r ≤ |E|. A chirotope of rank r on E is a map χ : E^{r} → {−1, 0, +1} that satisfies (C1) χ is an alternating sign map, i.e. for any permutation π ∈ Σ_{r} and (x_{1}, …, x_{r}) ∈ E^{r}

we have χ(x_{π(1)}, …, x_{π(r)}) = sgn(π)χ(x_{1}, …, x_{r}). (C2) The map |χ| : E^{r} → {0, 1} defines a matroid (E, |χ|). (C3) For every P ∈ E^{r−2} and a, b, c, d ∈ E \ P, the set

{χ(P, a, b)χ(P, c, d), −χ(P, a, c)χ(P, b, d), χ(P, a, d)χ(P, b, c)} either contains {+1, −1} or it equals {0}.

An oriented matroid of rank r is a pair M = (E, χ) where E is a nonempty set and χ is a chirotope of rank r on E. We call a matroid on E orientable if there exists a chirotope on E.

The underlying matroid M = (E, |χ|) always is simple (i.e. it has no loops and no parallel elements) and therefore it is called the underlying combinatorial geometry of M. The elements of E are called points.

Next we collect some facts and notations on matroids, which will be used in the following. Additional explanations and proofs can be found, e.g., in [1, 29, 30, 32].

For a matroid M = (E, B), let cl : \{ \begin{matrix}2^{E}→ & 2^{E} \\ A → & \overline{A} \end{matrix} be the closure operator of M. It follows that

a subset X of E is closed if and only if \overline{X} = X. The submatroid M_{X} = (X, B_{X}) generated by X ⊆ E (sometimes called the reduction of M on X) is referred to as subspace generated by X. Setting r(X) := |B| for B ∈ B_{X} we get the rank function of M_{X}.

A subspace H of rank r(M) − 1 is called a hyperplane of M and H denotes the set of all hyperplanes of M. The members of the family B^{o} := {(x_{1}, …, x_{r}) ∈ E^{r} : {x_{1}, …, x_{r}} ∈ B} will be called ordered bases.

Finally we present a conclusion of the chirotope condition (C3), which can be seen as a special oriented version of the Steinitz Exchange Theorem:

Proposition 2.1. Let M = (E, χ) be an oriented matroid of rank r, P ∈ E^{r−2} and x_{1}, x_{2}, a, b ∈ E \ P such that (P, x_{1}, a), (P, x_{2}, a), (P, x_{1}, b), (P, x_{2}, b) ∈ B^{o} but (P, x_{1}, x_{2}) ∉ B^{o}. Then χ(P, x_{1}, a)χ(P, x_{1}, b) = χ(P, x_{2}, a)χ(P, x_{2}, b).

Proof. Set ε_{1} := χ(P, x_{1}, a)χ(P, x_{2}, b), ε_{2} := χ(P, x_{1}, x_{2})χ(P, a, b) and ε_{3} := χ(P, x_{1}, b)χ(P, a, x_{2}). Because of (P, x_{1}, a), (P, x_{2}, b) ∈ B^{o} we have ε_{1} ≠ 0 and from (P, x_{1}, x_{2}) ∉ B^{o} we deduce ε_{2} = 0. Applying (C3) we get ε_{1} = −ε_{3}. Thus χ(P, x_{1}, a)χ(P, x_{2}, b) = χ(P, x_{1}, b)χ(P, x_{2}, a), which obviously yields our proposition. □

3. Order functions in oriented matroids

The theory of order functions provides new tools for the investigation of orientation. The basic properties of order functions derive from the idea, that in the 3-dimensional euclidean space each line is devided by each of its points into two halflines, each plane by each of its lines into two halfplanes and the space by each plane into two halfspaces. We transfer the basic characteristics of order functions from [24] to matroids:

Definition 3. Let M be a simple matroid of rank r on E (r ≥ 3), H the family of hyperplanes of M and (H × E × E)^{∗} = {(H, a, b) ∈ (H × E × E) : a, b ∉ H}.

A mapping ω : \{ \begin{matrix}(H × E × E)^{∗} ⟶ & \{1, −1\} \\ (H, a, b) ⟶ & (H|ab) \end{matrix}

is called an order function on M if it fulfills the following condition:

(O) ∀H ∈ H ∀a, b, c ∈ E \ H : (H|ab)(H|bc) = (H|ac)

Conclusions.

1. ∀H ∈ H ∀a ∈ E \ H : (H|aa) = 1

2. ∀H ∈ H ∀a, b ∈ E \ H : (H|ab) = (H|ba)

3. ∀H ∈ H ∀a, b ∈ E \ H : (H|ab)(H|ab) = 1

Remarks. Order functions as defined here coincide with the derivated order functions of first kind from [31]. Halfordered planes, ordered planes and ordered spaces, respectively, which describe richer structures of geometric ordering (compare [24, 25]) can be defined in terms of order functions (see [17]).

Let M = (E, χ) an oriented matroid of rank r with underlying combinatorial geometry M. We consider some subspace M_{Y} = (Y, B_{Y}) of M with Y ⊆ E and r(Y) := k (k ≤ r). A hyperplane of M_{Y} then is a subspace of M_{Y} (and hence of M) of rank k−1. We introduce the following notations: If B = (b_{1}, …, b_{k}) ∈ B_{Y}^{o} is some ordered base of M_{Y}, then the related unordered base is written as B^{∗} = {b_{1}, …, b_{k}} ∈ B_{Y}. Ordered bases A, B ∈ B_{Y}^{o} are called bases with common hyperplane H of M_{Y} ( shorthand A ≍ B or, more precisely, A ≍_{H} B), if there exists A′ ⊆ A^{∗} and B′ ⊆ B^{∗} with |A′| = k − 1 = |B′| fulfilling \overline{A′} = \overline{B′} = H.

Proposition 3.1. Let A, B ∈ B_{Y}^{o} be two ordered bases of a subspace M_{Y} of rank k. Then there exist ordered bases X_{1}, …, X_{k} ∈ B_{Y}^{o} such that A ≍ X_{1}, X_{1} ≍ X_{2}, …, X_{k} ≍ B.

Proof. Assume A = (a_{1}, …, a_{k}) and B = (b_{1}, …, b_{k}) and write singletons {x} shortly by x. We take X_{0} := A and argue by moving i step by step from 0 to k − 1 and thereby replacing a_{i+1} ∈ X_{i}^{∗} by a suitable b_{l_{i+1}} ∈ B^{∗} and defining X_{i+1} and the common hyperplane H_{i+1}.

Fix some i ∈ {0, …, k − 1} and assume X_{i} = (b_{l_{1}}, …, b_{l_{i}}, a_{i+1}, …, a_{k}) ∈ B_{Y}^{o}. First case: a_{i+1} ∈ X_{i}^{∗} ∩ B^{∗}. Then there exists b_{l_{i+1}} ∈ B^{∗} such that b_{l_{i+1}} = a_{i+1}. Second case: a_{i+1} ∈ X_{i}^{∗} \B^{∗}. Because the matroid M_{Y} obeys the base exchange property (B) (compare definition 1), there exists an element b_{l_{i+1}} ∈ B^{∗}\X_{i}^{∗} such that (X_{i}^{∗}\a_{i+1})∪b_{l_{i+1}} ∈ B_{Y}. We put X_{i+1} = (b_{l_{1}}, …, b_{l_{i}}, b_{l_{i+1}}, a_{i+2}, …, a_{k}) and H_{i+1} = \overline{X_{i}^{∗} \ a_{i+1}}. Hence X_{i+1}^{∗} = (X_{i}^{∗} \ a_{i+1}) ∪ b_{l_{i+1}} = (A^{∗} \ {a_{1}, …, a_{i+1}}) ∪ {b_{l_{1}}, …, b_{l_{i+1}}} and H_{i+1} is a common hyperplane of X_{i}^{∗} and X_{i+1}^{∗}. Finally we have X_{k}^{∗} = (A^{∗} \ \{a_{1}, …, a_{k}\}) ∪ \{b_{l_{1}}, …, b_{l_{k}}\} = B^{∗} and H_{k} = \overline{X_{k}^{∗} \ a_{k}} = \overline{b_{l_{1}}, …, b_{l_{k}}} is a common hyperplane of X_{k−1} und B. □

Remark. In general, the ordered bases X_{1}, …, X_{k} depend on the choice of the b_{l_{i}} and therefore are not uniquely determined. Whenever sequences A ≍ X_{1}, X_{1} ≍ X_{2}, …, X_{k} ≍ B occur in the following they are assumed to be produced according to the given order of A = (a_{1}, …, a_{k}).

Next we repeat that any permutation π ∈ Σ_{k} acts at an ordered base B = (x_{1}, …, x_{k}) ∈ B_{Y}^{o} by the rule π(B) = (x_{π(1)}, …, x_{π(k)}). Thus, if A, B ∈ B_{Y}^{o} and A ≍ X_{1}, …, X_{k} ≍ B as we got in proposition 3.1, there exists a permutation π obeying π(B) = X_{k}.

Proposition 3.2. For any hyperplane H of M, points a, b ∈ E \ H and any two ordered bases P and Q of H we have χ(P, a)χ(P, b) = χ(Q, a)χ(Q, b).

Proof. By applying proposition 3.1 to P = (p_{1}, …, p_{r−1}) and Q = (q_{1}, …, q_{r−1}) ∈ B_{H}^{o} we get ordered bases X_{i} (i = 1, …, r − 1) satisfying P ≍ X_{1}, …, X_{r−1} ≍ Q. Hence (P, a) ≍ (X_{1}, a), (X_{1}, a) ≍ (X_{2}, a), …, (X_{r−1}, a) ≍ (Q, a) and (P, b) ≍ (X_{1}, b), …, (X_{r−1}, b) ≍ (Q, b), respectively. Thereby the bases in each pair differ in at most one element (at position i) and we have π(X_{r−1}, a) = (Q, a) and π(X_{r−1}, b) = (Q, b) assuming π ∈ Σ_{k} to be that permutation whose restriction to H maps X_{r−1} onto Q and lets the r-th position unchanged. Now it is straightforward to see from proposition 2.1 that χ(P, a)χ(P, b) = χ(X_{1}, a)χ(X_{1}, b), χ(X_{1}, a)χ(X_{1}, b) = χ(X_{2}, a)χ(X_{2}, b), …, χ(X_{r−2}, a)χ(X_{r−2}, b) = χ(X_{r−1}, a)χ(X_{r−1}, b). Because χ is an alternating map, we have χ(X_{r−1}, a)χ(X_{r−1}, b) = sgn(π)χ(Q, a)sgn(π)χ(Q, b). This implies χ(P, a)χ(P, b) = χ(Q, a)χ(Q, b) finishing the proof. □

Now we relate an order function ω_{χ} to the given chirotope χ on E. For a hyperplane H and two points a, b ∈ E \ H we define: (H|ab) := χ(p_{1}, …, p_{r−1}, a)χ(p_{1}, …, p_{r−1}, b). Proposition 3.2 shows, that the value (H|ab) does not depend on the choice of the points p_{1}, …, p_{r−1} from H.

Proposition 3.3. Let χ be a chirotope on E, and define ω_{χ}(H, a, b) := (H|ab) for some hyperplane H and a, b ∈ E \H. Then ω_{χ} is an order function on the underlying combinatorial geometry M.

Proof.

1. For each hyperplane H = \overline{p_{1}, …, p_{r−1}} and points a, b ∈ E \ H the sets \{p_{1}, …, p_{r−1}, a\} and {p_{1}, …, p_{r−1}, b} are bases of E. Thus χ(p_{1}, …, p_{r−1}, a) ≠ 0 and χ(p_{1}, …, p_{r−1}, b) ≠ 0 and therefore we get ω_{χ} : (H × E × E)^{∗} ⟶ {1, −1}.

2. For each hyperplane H = \overline{p_{1}, …, p_{r−1}} and a, b, c ∈ E \ H we get: (H|a, b) · (H|b, c) = χ(p_{1}, …, p_{r−1}, a) · χ(p_{1}, …, p_{r−1}, b) · χ(p_{1}, …, p_{r−1}, b) · χ(p_{1}, …, p_{r−1}, c)

= χ(p_{1}, …, p_{r−1}, a) · χ(p_{1}, …, p_{r−1}, c)

= (H|a, c), which proves (O). □

We call ω_{χ} the order function generated by χ.

For the rest of the chapter let (E, χ) be an oriented matroid of rank r and ω_{χ} the order function generated by χ. Generation of ω_{χ} from a chirotope causes special properties.

Proposition 3.4. Each order function generated from a chirotope satiesfies: (OC1) For any three different hyperplanes A, B, C with r(A ∩ B ∩ C) = r − 2 and a, b, c ∈ E

with a ∈ A\(B∪C), b ∈ B\(A∪C), c ∈ C\(A∪B), we have (A|bc)(B|ac)(C|ab) = −1.

Illustration: (plane case; r(M) = 3, A ∩ B ∩ C = {p})

[figure: a; b; c; p; A; B; C; a; b; c; p; A; B; C]

(A|bc) = −1, (B|ac) = −1, (C|ab) = −1 (A|bc) = −1, (B|ac) = +1, (C|ab) = +1

Remark. Following [31] order functions with property (OC1) are called harmonic.

Proof of proposition 3.4. Because of r(A ∩ B ∩ C) = r(E) − 2 = r − 2 there exist points p_{1}, …, p_{r−2} ∈ A ∩ B ∩ C such that A = \overline{\{p_{1}, …, p_{r−2}, a\}}, B = \overline{\{p_{1}, …, p_{r−2}, b\}} and C = \overline{\{p_{1}, …, p_{r−2}, c\}}. Since A, B, C are three distinct hyperplanes, the sets \{p_{1}, …, p_{r−2}, a, b\}, {p_{1}, …, p_{r−2}, a, c} and {p_{1}, …, p_{r−2}, b, c} form bases of E and we conclude: (A|bc)(B|ac)(C|ab) = χ(p_{1}, …, p_{r−2}, a, b) · χ(p_{1}, …, p_{r−2}, a, c)

·χ(p_{1}, …, p_{r−2}, b, a) · χ(p_{1}, …, p_{r−2}, b, c)

·χ(p_{1}, …, p_{r−2}, c, a) · χ(p_{1}, …, p_{r−2}, c, b)
= −1

since by (C1), χ is alternating. □

Proposition 3.5. Each order function generated from a chirotope satiesfies: (OC2) For any four different hyperplanes A, B, C, D with r(A ∩ B ∩ C ∩ D) = r − 2 and

a, b, c, d ∈ E \ (A ∩ B ∩ C ∩ D) with a ∈ A, b ∈ B, c ∈ C, d ∈ D, exactly one of the

values (A|bc)(D|bc), (B|ac)(D|ac), or (C|ab)(D|ab) equals −1.

Illustration: (plane case; r(M) = 3, A ∩ B ∩ C ∩ D = {p})

[figure: a; c; d; b; p; A; B; C; D; a; d; c; b; p; A; D; C; B]
(A|bc)(D|bc) = +1 · +1 = +1 ; (B|ac)(D|ac) = −1 · +1 = −1 ; (C|ab)(D|ab) = +1 · +1 = +1  (A|bc)(D|bc) = −1 · −1 = +1 ; (B|ac)(D|ac) = +1 · +1 = +1 ; (C|ab)(D|ab) = +1 · −1 = −1

Remark. Property (OC2) is similar to a property which was used in [22] to describe order structures in projective spaces. Joussen [18] named such order functions strict.

Proof of proposition 3.5. From (OC1) we deduce that at least one of the values (A|bc)(D|bc), (B|ac)(D|ac), (C|ab)(D|ab) equals −1. Assume (A|bc)(D|bc) = −1 and put A ∩ B ∩ C ∩ D = \overline{p_{1}, …, p_{r−2}} and W := (p_{1}, …, p_{r−2}). Then (W, a, b), (W, a, c), (W, b, c), (W, a, d), (W, b, d) and (W, c, d) form ordered bases of M. We put ε_{1} := χ(W, a, b) · χ(W, c, d), ε_{2} := −χ(W, a, c) · χ(W, b, d) and ε_{3} := χ(W, a, d) · χ(W, b, c) and this gives (A|bc)(D|bc) = −ε_{1} · ε_{2}, (B|ac)(D|ac) = −ε_{1} · ε_{3} and (C|ab)(D|ab) = −ε_{2} · ε_{3}. Our assumption (A|bc)(D|bc) = −1 implies ε_{1} · ε_{2} = 1 and so we have ε_{1} = ε_{2}. Applying (C3) we get ε_{3} = −ε_{1} = −ε_{2} and thus (B|ac)(D|ac) = 1 and (C|ab)(D|ab) = 1. □

4. Orientation generated by an order function

In the previous section we proved that an order function always is harmonic and strict, if it comes from a chirotope. Now we reverse the direction of asking questions. We start from a matroid, equipped with a harmonic and strict order function and produce a chirotope and therefore an orientation from it.

Let M be a combinatorial geometry of rank r on E und let ω be an order function on M fulfilling (OC1) and (OC2). First we make the following observation:

Proposition 4.1 (Modular hyperplane relation). (H*) If F, G, H are three distinct hyperplanes with r(F ∩ G ∩ H) = r − 2 and a and b are points with a, b ∈ H und a, b ∉ F ∪ G, then (F |ab) = (G|ab).

Remark. If r(M) = 3, so (H*) corresponds to the ’line relation’ (Geradenrelation) for order functions in an exchange space; compare [24].

Proof. Let D := F ∩ G ∩ H, which is a subspace of rank r − 2 of M. Then there exist points f ∈ F \(H ∪G) and g ∈ G\(H ∪F) such that F = \overline{D ∪ \{f\}} and G = \overline{D ∪ \{g\}}. As, moreover, \overline{D ∪ \{a\}} = H = \overline{D ∪ \{b\}}, by applying (OC1) we conclude (F |ag)(G|af)(H|gf) = −1 and (F |bg)(G|bf)(H|gf) = −1. This implies (F |ag)(G|af) = (F |bg)(G|bf) and together with (O) we finally get (F |ab) = (G|ab). □

We regard the family B^{o} of ordered bases of M and introduce an equivalence relation ∼ with exactly two classes.

Let A = (a_{1}, …, a_{r}), B = (b_{1}, …, b_{r}) ∈ B^{o} be ordered bases. There exist ordered bases X_{1}, …, X_{r} ∈ B^{o} and hyperplanes H_{1}, …, H_{r} ∈ H produced according to proposition 3.1 such that A ≍_{H_{1}} X_{1}, X_{1} ≍_{H_{2}} X_{2}, …, X_{r−1} ≍_{H_{r}} X_{r} and π(B) = X_{r}, where π ∈ Σ_{r} is a suitable permutation. We define [A, X_{1}, …, X_{r}, B] := sgn(π)(H_{1}|a_{1}b_{π(1)})(H_{2}|a_{2}b_{π(2)}) ⋯ (H_{r}|a_{r}b_{π(r)}) ∈ {1, −1}. Then we observe: If B = π(A), so X_{r} = A and (H_{i}|a_{i}b_{π(i)}) = (H_{i}|a_{i}a_{i}) = 1 for all i = 1, …, r. Thus [A, X_{1}, …, X_{r}, B] = [A, X_{1}, …, X_{r}, π(A)] = sgn(π)(H_{1}|a_{1}a_{1}) ⋯ (H_{r}|a_{r}a_{r}) = sgn(π).

Proposition 4.2. For some fixed number i ∈ {1, …, r − 1}, let A = (a_{1}, …, a_{r}), B = (b_{1}, …, b_{r}) and B′ = (b′_{1}, …, b′_{r}) = (b_{1}, …, b_{i−1}, b_{i+1}, b_{i}, b_{i+2}, …, b_{r}) ∈ B^{o} be ordered bases with A ≍ X_{1}, X_{1} ≍ X_{2}, …, X_{r−1} ≍ X_{r} = B and A ≍ Y_{1}, Y_{1} ≍ Y_{2}, …, Y_{r−1} ≍ Y_{r} = B′. Then [A, X_{1}, …, X_{r}, B] = −[A, Y_{1}, …, Y_{r}, B′].

Proof. Since X_{1}, …, X_{r}, Y_{1}, …, Y_{r} are produced according to proposition 3.1, we have A ≍_{H_{1}} X_{1}, X_{1} ≍_{H_{2}} X_{2}, …, X_{r−1} ≍_{H_{r}} X_{r} = B where H_{k} = \overline{X_{k−1}^{∗} \ a_{k}} and X_{k} = (b_{1}, …, b_{k}, a_{k+1}, …, a_{r}) for k = 1, …, r, and A ≍_{G_{1}} Y_{1}, Y_{1} ≍_{G_{2}} Y_{2}, …, Y_{r−1} ≍_{G_{r}} Y_{r} = B′ where G_{k} = \overline{Y_{k−1}^{∗} \ a_{k}} for k = 1, …, r, Y_{k} = X_{k} if k = 1, …, i − 1, Y_{i} = (b_{1}, …, b_{i−1}, b_{i+1}, a_{i+1}, …, a_{r}), Y_{i+1} = (b_{1}, …, b_{i−1}, b_{i+1}, b_{i}, a_{i+2}, …, a_{r}) and Y_{k} = (b_{1}, …, b_{i−1}, b_{i+1}, b_{i}, …, b_{k}, a_{k+1}, …, a_{r}) if i + 2 ≤ k ≤ r. If k ∈ {1, …, r}\{i, i+1}, then clearly holds Y_{k}^{∗} = X_{k}^{∗}, G_{k} = H_{k} and (H_{k}|a_{k}b_{k}) = (G_{k}|a_{k}b′_{k}). We obtain [A, X_{1}, …, X_{r}, B][A, Y_{1}, …, Y_{r}, B′] = (H_{i}|a_{i}b_{i})(H_{i+1}|a_{i+1}b_{i+1})(G_{i}|a_{i}b′_{i})(G_{i+1}|a_{i+1}b′_{i+1}) = (H_{i}|a_{i}b_{i})(H_{i+1}|a_{i+1}b_{i+1})(G_{i}|a_{i}b_{i+1})(G_{i+1}|a_{i+1}b_{i}). We see: H_{i} = \overline{X_{i−1}^{∗} \ a_{i}}, X_{i}^{∗} = (X_{i−1}^{∗} \ a_{i}) ∪ b_{i}, H_{i+1} = \overline{X_{i}^{∗} \ a_{i+1}} = \overline{((X_{i−1}^{∗} \ a_{i}) ∪ b_{i}) \ a_{i+1}} and moreover G_{i} = \overline{Y_{i−1}^{∗} \ a_{i}} = \overline{X_{i−1}^{∗} \ a_{i}} = H_{i}, Y_{i}^{∗} = (Y_{i−1}^{∗} \ a_{i}) ∪ b′_{i} = (X_{i−1}^{∗} \ a_{i}) ∪ b_{i+1} and G_{i+1} = \overline{Y_{i}^{∗} \ a_{i+1}} = \overline{((X_{i−1}^{∗} \ a_{i}) ∪ b_{i+1}) \ a_{i+1}}. This yields: [A, X_{1}, …, X_{r}, B][A, Y_{1}, …, Y_{r}, B′] =

= (H_{i}|a_{i}b_{i})(\overline{((X_{i−1}^{∗} \ a_{i}) ∪ b_{i}) \ a_{i+1}}|a_{i+1}b_{i+1})(H_{i}|a_{i}b_{i+1})(\overline{((X_{i−1}^{∗} \ a_{i}) ∪ b_{i+1}) \ a_{i+1}}|a_{i+1}b_{i}) = (H_{i}|b_{i}b_{i+1})(\overline{X_{i−1}^{∗} \ a_{i} \ a_{i+1} ∪ b_{i}}|a_{i+1}b_{i+1})(\overline{X_{i−1}^{∗} \ a_{i} \ a_{i+1} ∪ b_{i+1}}|a_{i+1}b_{i})

=^{(OC1)} (H_{i}|b_{i}b_{i+1})(−1)(\overline{((X_{i−1}^{∗} \ a_{i}) \ a_{i+1}) ∪ a_{i+1}}|b_{i}b_{i+1})

= (−1)(H_{i}|b_{i}b_{i+1})(H_{i}|b_{i}b_{i+1}) = −1, and this completes the proof. □

Proposition 4.3. Let A, B, X_{1}, …, X_{r}, Y_{1}, …, Y_{r} ∈ B^{o} be ordered bases such that A ≍_{H_{1}} X_{1}, …, X_{r−1} ≍_{H_{r}} X_{r} and A ≍_{G_{1}} Y_{1}, …, Y_{r−1} ≍_{G_{r}} Y_{r} where H_{1}, …, H_{r}, G_{1}, …, G_{r} ∈ H are hyperplanes and π, σ ∈ S_{r} are the related permutations satisfying π(B) = X_{r} and σ(B) = Y_{r}. Then sgn(π)(H_{1}|a_{1}b_{π(1)}) ⋯ (H_{r}|a_{r}b_{π(r)}) = sgn(σ) · (G_{1}|a_{1}b_{σ(1)}) ⋯ (G_{r}|a_{r}b_{σ(r)}).

Proof. By setting ρ := σ · π^{−1} we get Y_{r} = ρ(X_{r}). The permutation ρ can be divided into a product ρ = τ_{n} ∘ ⋯ ∘ τ_{1} of n transpositions τ_{1}, …, τ_{n} ∈ Σ_{r}, each exchanging consecutive elements. We set τ_{1}(X_{r}) = T_{1}, τ_{2}(T_{1}) = T_{2}, … τ_{n}(T_{n−1}) = Y_{r} = ρ(X_{r}) and thereby obtain ordered bases T_{1}, …, T_{n−1} ∈ B^{o}. According to Proposition 3.1, for all i = 1, …, n − 1, there exist B_{i1}, …, B_{ir} ∈ B^{o} such that A ≍ B_{i1}, …, B_{ir} ≍ T_{i}. From proposition 4.2 we conclude [A, B_{i1}, …, B_{ir}, T_{i}] = −[A, B_{i+11}, …, B_{i+1r}, T_{i+1}] and thus [A, B_{i1}, …, B_{ir}, T_{i}][A, B_{i+11}, …, B_{i+1r}, T_{i+1}] = −1. Hence [A, X_{1}, …, X_{r}, X_{r}][A, B_{11}, …, B_{1r}, T_{1}][A, B_{11}, …, B_{1r}, T_{1}][A, B_{21}, …, B_{2r}, T_{2}] ⋯ ⋯ [A, B_{n−11}, …, B_{n−1r}, T_{n−1}][A, Y_{1}, …, Y_{r}, Y_{r}] = (−1)^{n} and consequently [A, X_{1}, …, X_{r}, X_{r}][A, Y_{1}, …, Y_{r}, Y_{r}] = sgn(ρ). Finally we obtain (H_{1}|a_{1}b_{π(1)}) ⋯ (H_{r}|a_{r}b_{π(r)})(G_{1}|a_{1}b_{σ(1)}) ⋯ (G_{r}|a_{r}b_{σ(r)}) = sgn(σ)sgn(π^{−1}), which proves our assertion. □

According to proposition 4.3. the value [A, X_{1}, …, X_{r}, B]=sgn(π)(H_{1}|a_{1}b_{π(1)})⋯(H_{r}|a_{r}b_{π(r)}) can be considered as a characteristic invariant of the pair (A, B) of ordered bases. We denote it by [A, B]. Obviously the mapping [., .] : B^{o} × B^{o} → {1, −1} is surjective.

For all A = (a_{1}, …, a_{r}), B = (b_{1}, …, b_{r}) ∈ B^{o} we define: A ∼ B :⇔ [A, B] = 1.

Then as an immediate consequence of the previous propositions we conclude:

Proposition 4.4. ∼ is an equivalence relation at B^{o} with exactly two nonempty classes.

Let λ be the canonical homomorphism from B^{o} onto B^{o}/_{∼}, which assigns each ordered base to its class. For all X = (x_{1}, …, x_{r}) ∈ E^{r} a mapping χ_{ω} is defined by

χ_{ω}(X) := \{ \begin{matrix}0 if & X ∉ B^{o} \\ λ(X) if & X ∈ B^{o} \end{matrix}

We observe:

Proposition 4.5. If H is a hyperplane spanned by p_{1}, …, p_{r−1} and a, b ∈ E \ H, then χ_{ω}(a, p_{1}, …, p_{r−1}) = (\overline{p_{1}, …, p_{r−1}}|ab) · χ_{ω}(b, p_{1}, …, p_{r−1}).

Proposition 4.6. χ_{ω} is a chirotope on M.

Proof. The fact that (E, |χ_{ω}|) is a matroid, is immediate from the definition. If B_{0} is an arbitrary but fixed ordered base and B and B′ are ordered bases with B′ = π(B) where π is a permutation, then by proposition 4.2 and 4.3 we conclude [B_{0}, B] = sgn(π)[B_{0}, B′]. Hence χ_{ω} is alternating.

Now, to show that (C3) holds, suppose that P ∈ E^{r−2} and a, b, c, d ∈ E \ P. We put ε_{1} := χ_{ω}(P, a, b)χ_{ω}(P, c, d), ε_{2} := −χ_{ω}(P, a, c)χ_{ω}(P, b, d) and ε_{3} := χ_{ω}(P, a, d)χ_{ω}(P, b, c). For proving (C3) we have to show that the set S := {ε_{1}, ε_{2}, ε_{3}} either contains +1 and −1 or equals {0}. Without loss of generality, we may assume that a, b, c, d are pairwise distinct.

(1) If two elements of S are equal to 0, so is the third. Equivalent: If one of the elements of S is unequal 0, so is a second one.

Assume ε_{3} ≠ 0. Then B_{1} = {P, a, d} and B_{2} = {P, b, c} are bases of M. Since a ∈ B_{1}\B_{2}, there exists an element x ∈ B_{2} \ B_{1} = {b, c} such that (B_{1} \ a) ∪ x ∈ B. Thus

(a) {P, d, b} ∈ B or {P, d, c} ∈ B and by similar arguments for d, b and c

(b) {P, a, b} ∈ B or {P, a, c} ∈ B and

(c) {P, c, a} ∈ B or {P, c, d} ∈ B and

(d) {P, b, a} ∈ B or {P, b, d} ∈ B. If ε_{1} equals 0, so {P, a, b} ∉ B or {P, c, d} ∉ B. In the first case we apply (b) and (d) and get {P, a, c} ∈ B and {P, b, d} ∈ B, which implies ε_{2} ≠ 0. In the second case we apply (a) and (c) and get {P, b, d} ∈ B and {P, a, c} ∈ B, which also implies ε_{2} ≠ 0.

If ε_{2} ≠ 0 or ε_{1} ≠ 0 an analogous argument shows that at least one of the other elements of S does not equal 0.

(2) If ε_{i_{1}} ≠ 0 and ε_{i_{2}} = 0, so ε_{i_{3}} = −ε_{i_{1}} where {i_{1}, i_{2}, i_{3}} = {1, 2, 3}. Because of similar arguments in the other cases we can assume ε_{3} ≠ 0 and ε_{2} = 0. Application of (1.) yields ε_{1} ≠ 0. This implies that {P, a, b}, {P, c, d}, {P, a, d} and {P, b, c} are bases, whereas \{P, a, c\} ∉ B or \{P, b, d\} ∉ B. We regard the hyperplanes A := \overline{P ∪ a}, B := \overline{P ∪ b}, C := \overline{P ∪ c} and D := \overline{P ∪ d}.

If {P, a, c} ∉ B, so A and C coincide (A = C =: H) and the hyperplanes additionally fulfill B ∩ D ∩ H = \overline{P}, r(B ∩ D ∩ H) = r − 2, a, c ∉ B ∪ D and a, c ∈ H. Using (H*) we deduce (B|ac) = (D|ac). Now we see: ε_{1} = χ_{ω}(P, a, b) · χ_{ω}(P, c, d)

= (B|ac) · χ_{ω}(P, c, b) · (D|ac) · χ_{ω}(P, a, d)

=^{(Prop.4.5)} −χ_{ω}(P, b, c) · χ_{ω}(P, a, d)

= −ε_{3} If {P, b, d} ∉ B, a similar argument works.

(3) Finally we assume ε_{3}, ε_{2}, ε_{1} ≠ 0. Then A := \overline{P ∪ a}, B := \overline{P ∪ b}, C := \overline{P ∪ c} and D := \overline{P ∪ d} are hyperplanes and in addition a, c ∉ B, D and b, c ∉ A, D hold. Thus we get the following equations ε_{1} = χ_{ω}(P, a, b) · χ_{ω}(P, c, d) = (A|bc) · χ_{ω}(P, a, c) · (D|bc) · χ_{ω}(P, b, d) = −(A|bc) · (D|bc) · ε_{2} ε_{1} = χ_{ω}(P, a, b) · χ_{ω}(P, c, d) = (B|ac) · χ_{ω}(P, c, b) · (D|ac) · χ_{ω}(P, a, d) = −(B|ac) · (D|ac) · ε_{3} ε_{2} = −χ_{ω}(P, a, c)·χ_{ω}(P, b, d) = −(C|ab)·χ_{ω}(P, b, c)·(D|ab)·χ_{ω}(P, a, d) = −(C|ab)·(D|ab)·ε_{3} Suppose that two of the terms are equal, say ε_{1} = ε_{2}. Consequently (A|bc)·(D|bc) = −ε_{1}·ε_{2} = −1. Now we apply (OC2) and get 1 = (B|ac) · (D|ac) = −ε_{1} · ε_{3} which yields ε_{1} = −ε_{3}. Similar argumentations in the other cases conclude the proof of the proposition. □

5. Geometrical characterization theorem

In section 3 we saw that in every oriented matroid the chirotope produces a harmonic and strict order function on the underlying combinatorial geometry (proposition 3.4 and 3.5). In section 4 we started vice versa from a harmonic and strict order function and generated a chirotope (proposition 4.6). Summarizing both we get our final result:

Theorem. Let M be a combinatorial geometry on E. Then M is orientable if and only if there exists an order function on E which is harmonic and strict.

Remark. There exist combinatorial geometries M which are not orientable, what means that there does not exist any harmonic and strict order function on M. For example, finite affine planes of order q > 2 as well as finite projective planes are never orientable (cf. [3]).

References

[1] Aigner, M.: Kombinatorik, Teil II: Matroide und Transversaltheorie. Springer–Verlag Berlin Heidelberg NewYork 1976.

[2] Bachem, A.; Kern, W.: Linear Programming Duality: An Introduction to Oriented Matroids. Springer–Verlag Berlin Heidelberg 1992.

[3] Björner, A.; Las Vergnas, M.; Sturmfels, B.; White, N.; Ziegler, G. M.: Oriented Matroids. Cambridge University Press 1993.

[4] Böhm, J. et al.: Geometrie I. Deutscher Verlag der Wissenschaften, 5.Aufl. Berlin 1988.

[5] Börner, W.: Orientierung in angeordneten affinen Räumen. Beiträge zur Algebra und Geometrie 5 (1976), 23–32.

[6] Bokowski, J.: Oriented Matroids. In: Handbook of Convex Geometry, ed. by P.M. Gruber and J.M. Wills, Elsevier Science Publishers B.V. 1993.

[7] Bokowski, J.; Sturmfels, B.: Computational Synthetic Geometry. Lecture Notes in Mathematics 1355, Springer–Verlag Berlin 1989.

[8] Bokowski, J.; Guedes de Oliveira, A.; Richter, J.: Algebraic varieties characterizing matroids and oriented matroids. Advances in Mathematics 87 (1991), 160–185.

[9] Bokowski, J.; Guedes de Oliveira, A.; Thiemann, U.; Veoso da Costa, A.: On the cube problem of Las Vergnas. Geometriae Dedicata 63 (1996), 25–43.

[10] tom Dieck, T.: Topologie. Walter de Gruyter, Berlin NewYork 1991.

[11] Dress, A. W. M.: Chirotopes and oriented matroids. Bayreuther Math. Schriften 21 (1986), 14–68.

[12] Dress, A. W. M.; Wenzel, W.: Geometric Algebra for Combinatorial Geometries. Advances in Mathematics 77 (1989), 1–36.

[13] Dress, A. W. M.; Wenzel, W.: Grassmann–Plücker relations and matroids with coefficients. Advances in Mathematics 86 (1991), 68–110.

[14] Folkman, J.; Lawrence, J.: Oriented matroids. J. Combinatorial Theory, Ser. B 25 (1978), 199–236.

[15] Glock, E.: Die Orientierungsfunktionen eines affinen Raumes. Math. Zeitschr. 78 (1962), 319–360.

[16] Gutierrez Novoa, L.: On n-ordered sets and order-completeness. Pacific J. Math. 15 (1965), 1337–1345.

[17] Jaritz, R.: Seiteneinteilungen und Konvexität in halbgeordneten Ebenen. Beiträge zur Geometrie und Algebra d. TU München Nr.23 (1993), 1–8.

[18] Joussen, J.: Projektive Einbettung angeordneter Ebenen. Vortrag Geometrietagung TU München 1994.

[19] Kalhoff, F. B.: Oriented rank three matroids and projective planes. In preparation.

[20] Karzel, H.: Ordnungsfunktionen in nichtdesarguesschen projektiven Geometrien. Math. Zeitschr. 62 (1955), 268–291.

[21] Karzel, H.: Anordnungsfragen in ternären Ringen und allgemeinen projektiven und affinen Ebenen. Algebraical and topological foundations of geometry. Proceedings of a colloquium held in Utrecht August 1959. Oxford–London–NewYork–Paris 1962.

[22] Karzel, H.: Konvexität in halbgeordneten projektiven und affinen Räumen. Abh. Math. Sem. Univ. Hamburg 33 (1969), 231–242.

[23] Karzel, H.; Kroll, H.-J.: Geschichte der Geometrie seit Hilbert. Wiss. Buchgesellschaft Darmstadt 1988.

[24] Karzel, H.; Sörensen, K.; Windelberg, D.: Einführung in die Geometrie. Vandenhoeck & Ruprecht, Göttingen 1973.

[25] Kreuzer, A.: Zur Abhängigkeit von Anordnungsaxiomen. Journal of Geometry 31 (1988), 125–130.

[26] Las Vergnas, M.: Oriented matroids as signed geometries real in corank 2. In: Finite and infinite sets (Proc. 6th Hungarian Combinatorial Conf. Eger 1981), North–Holland 1984, 555–565.

[27] Lawrence, J.: Oriented matroids and Multiply Ordered Sets. Linear Algebra and its Applications 48 (1982), 1–12.

[28] Lenz, H.: Grundlagen der Elementarmathematik. Deutscher Verlag der Wissenschaften, Berlin 1967.

[29] Oxley, J. G.: Matroid Theory. Oxford University Press 1992.

[30] Recski, A.: Matroid Theory and its Applications. Springer–Verlag, Berlin Heidelberg NewYork 1989.

[31] Sperner, E.: Die Ordnungsfunktionen einer Geometrie. Math. Ann. 121 (1949), 107–130.

[32] Welsh, D. J. A.: Matroid Theory. Academic Press, London NewYork SanFrancisco 1976.

[33] White, N. (ed.): Theory of matroids. Cambridge University Press 1986.

Received August 29, 1996