Two Interesting Oriented Matroids

Jürgen Richter-Gebert^{1}

Received: February 2, 1996 Revised: February 19, 1996

Communicated by Günter M. Ziegler

Abstract. Oriented matroids are a combinatorial model for configurations in real vector spaces. A central role in the theory is played by the realizability problem: Given an oriented matroid, find an associated vector configuration. In this paper we present two closely related oriented matroids Ω_{14}^{+} and Ω_{14}^{−} of rank 3 with 14 elements that have interesting properties with respect to realizability. Ω_{14}^{+} and Ω_{14}^{−} differ in exactly one basis orientation.

The realizable oriented matroid Ω_{14}^{+} has at least two interesting properties: First it has a combinatorial symmetry that has no metric realization, and second it has a disconnected realization space. In other words, there are different realizations of Ω_{14}^{+} that cannot be continuously deformed into each other while staying in the same isotopy class. The oriented matroid Ω_{14}^{−} is non-realizable but it has no bi-quadratic final polynomial. In other words, the only known effective algorithmic method fails to prove the nonrealizability of Ω_{14}^{−}.

1991 Mathematics Subject Classification: Primary 52B40; Secondary 14P10, 51A25, 52B30.

1 Introduction

Oriented matroids are combinatorial models for vector configurations in vector spaces over ordered fields. They form a basic combinatorial concept for treating many different objects on the borderline of combinatorics and geometry — such as convex polytopes, simplicial complexes, hyperplane-arrangements, quasi-crystals, etc. The realizability question is of fundamental importance in this theory: When does a discrete structure have a geometric representation? What does the space of all representations look like? Questions of this type occur in many different mathematical contexts (e.g. embedding of polyhedral manifolds, the theory of moduli spaces, Cairns’ smoothing theory, etc.). The basic effects that arise here are often due to the properties of the underlying oriented matroids, and they can be profitably studied in this model. A systematic study of “small” oriented matroids that have interesting behavior with respect to realizability is a fruitful source for producing examples and counterexamples in many different mathematical disciplines. Here we present two new such oriented matroids.

1Supported by a DFG Gerhardt-Hess-Forschungsförderungspreis awarded to G.M. Ziegler

Documenta Mathematica 1 (1996) 137–148

Every vector configuration has an associated oriented matroid, but the converse is not true: there are oriented matroids that have no corresponding vector configuration. An oriented matroids is realizable if it corresponds to a vector configuration, and nonrealizable otherwise. In this paper we present two closely related oriented matroids Ω_{14}^{+} and Ω_{14}^{−} of rank 3 with 14 elements that are interesting because of their properties with respect to realizability.

The oriented matroid Ω_{14}^{+} is realizable, but its realization space is not connected. The realization space of an oriented matroid χ is the set of all vector configurations X that have the associated oriented matroid χ, modulo linear equivalence. (For a more formal definition of realization spaces see Section 2). For a long time it was an outstanding open question whether oriented matroids with disconnected realization space exist. This problem was solved by N.E. Mnëv in a surprising way [6, 7]. He proved that for any basic semi-algebraic set V (defined over the rationals) there is an oriented matroid whose realization space is stably equivalent (in the sense of [9]) to V. Thus realization spaces can be homotopy equivalent to any finite simplicial complex (in particular they may have an arbitrary number of connected components). The examples produced by Mnëv’s method in general involve a large number of points. At the same time P.Y. Suvorov [12] constructed an example of rank 3 with disconnected realization space that contains only 14 elements.

The oriented matroid Ω_{14}^{+} shares these properties with Suvorov’s example, but it has the following additional nice properties:

• Ω_{14}^{+} is constructible. (After fixing the position of the points x_{1}, …, x_{4} that form a projective basis and choosing a point x_{5} = (t + 1)x_{3} + (t − 1)x_{4} each point x_{i} for i = 6, …, 14 is of the form (x_{a} ∨ x_{b}) ∧ (x_{c} ∨ x_{d}) where “∨” is the join operator and “∧” is the meet operator and a, b, c, d are indices that are smaller than i.)

• up to stable equivalence (see [9]) the realization space of Ω_{14}^{+} is an open interval from which one point has been deleted.

• Ω_{14}^{+} has rational realizations.

• Ω_{14}^{+} has a combinatorial symmetry of order two that has no metric realization. (The smallest example with this property, known so far, with 90 points, was constructed by P. Shor [11].)

It is still an open question whether there exists an oriented matroid with disconnected realization space and less than 14 points.

If we switch the orientation of one particular basis in Ω_{14}^{+} we obtain the nonrealizable oriented matroid Ω_{14}^{−}. This oriented matroid has a remarkable property. It is the first known example of a non-realizable oriented matroid for which nonrealizability cannot be proved by a bi-quadratic final polynomial.

Final polynomials [3, 5] are certificates for the non-realizability of matroids and oriented matroids. However, no algorithmic method for computing final polynomials is known to be both generally applicable and effective. Indeed, this is not surprising since the realizability problem is known to be NP-hard [11]. Bi-quadratic final polynomials (as introduced in [2] and [8]) are special kinds of final polynomials which can be computed very efficiently. The method of bi-quadratic final polynomials for the oriented matroid case was originally inspired by J. Bokowski [5], who suggested that one consider only inequalities of the form […][…] < […][…] which are consequences of three-term Graßmann-Plücker polynomials and the signature of the oriented matroid. These inequalities have to be satisfied in the realizable case. If this system of these inequalities is inconsistent one has a bi-quadratic final polynomial. Deciding whether an oriented matroid has a bi-quadratic final polynomial can be translated into an LP-feasibility-problem and therefore solved in polynomial time. This is the first example of a non-realizable oriented matroid which cannot be certified to be non-realizable by a bi-quadratic final polynomial.

2 Realization spaces

Oriented matroids are combinatorial models for vector configurations in linear vector spaces over ordered fields. For an extensive introduction into oriented matroid theory we recommend [1] and [10]. Throughout the paper we will restrict ourselves to the case of vector configurations in IR^{3}, the case of oriented matroids of rank 3. Let X = (x_{1}, …, x_{n}) ∈ IR^{3n} be a configuration consisting of n vectors in IR^{3}. We set E = {1, …, n}. To every triple of indices (i, j, k) ∈ E^{3} we assign a sign

χ_{X} (i, j, k) = sign det(x_{i}, x_{j}, x_{k}).

The map χ_{X}: E^{3} → {−1, 0, +1} is called the oriented matroid of X. We omit the general definition of an oriented matroid (it can be found in [1] and [10]).

For us it is sufficient to know that an oriented matroid χ: E^{3} → {−1, 0, +1} is a sign map that models the combinatorial behavior of signs of determinants. In particular χ always satisfies the alternating determinant rules:

χ(i, j, k) = χ(k, i, j) = χ(j, k, i) = −χ(j, i, k) = −χ(k, j, i) = −χ(i, k, j).

Since χ is alternating it is sufficient to specify χ on the set

Λ(E, 3) = {(i, j, k) ∈ E^{3} | i < j < k}.

An oriented matroid χ is realizable if there is a vector configuration X with χ_{X} = χ. If there is no such vector configuration, then χ is called non-realizable. Deciding the question whether an oriented matroid is realizable or not algorithmically is known to be an NP-hard problem [11].

For a realizable oriented matroid one is often interested not only in a particular realization, but also in the space of all realizations. There are various ways of describing this space, depending on how much of the actions on IR^{3n} that preserve the oriented matroid of X are factored out. If at least a linear basis is fixed all these descriptions turn out to be isomorphic up to stable equivalence (compare [9]). We here use the version where a projective basis is fixed. Reorientation of a point i (i.e. reversing all signs χ(a, b, c) with i ∈ {a, b, c}) does not change the behavior of χ with respect to realizability: if X = (x_{1}, …, x_{n}) is a realization of χ then we get a realization of the reversed situation if we replace x_{i} by −x_{i}. Hence, we may (up to relabeling, reorientation of points 1, 2, 3 or 4 and the assumption that χ has at least four points in general position) assume that we have χ(1, 2, 3) = χ(1, 2, 4) = χ(1, 3, 4) = χ(2, 3, 4) = 1.

Definition 2.1. Let χ: E^{3} → {−1, 0, +1} be a rank 3 oriented matroid that satisfies χ(1, 2, 3) = χ(1, 2, 4) = χ(1, 3, 4) = χ(2, 3, 4) = 1. Let x_{1} = (1, 0, 0), x_{2} = (0, 1, 0), x_{3} = (1, 0, 1), and x_{4} = (0, 1, 1). The realization space of χ is the set of all (x_{5}, …, x_{n}) ∈ IR^{3(n−4)} with χ_{X} = χ for X = (x_{1}, …, x_{n}).

3 Ω_{14}^{+} has disconnected realization space

The configuration that we will study here is defined by the following construction sequence. The oriented matroid Ω_{14}^{+} is the underlying oriented matroid for choices of the parameter t in (−3 + \sqrt{8}, 0) ∪ (0, 3 − \sqrt{8}).

x_{1} = (1, 0, 0),
x_{2} = (0, 1, 0),
x_{3} = (1, 0, 1),
x_{4} = (0, 1, 1),
x_{5} = (1 − t)x_{3} + (1 + t)x_{4},
x_{6} = x_{5}x_{2} ∧ x_{1}x_{4} = (1 − t, 2, 2),
x_{7} = x_{5}x_{1} ∧ x_{2}x_{3} = (−2, −1 − t, −2),
x_{8} = x_{6}x_{3} ∧ x_{5}x_{1} = (3 − 2 t − t^{2}, 2 + 2 t, 4),
x_{9} = x_{7}x_{4} ∧ x_{5}x_{2} = (2 − 2 t, 3 + 2 t − t^{2}, 4),
x_{10} = x_{3}x_{4} ∧ x_{8}x_{2} = (−3 + 2 t + t^{2}, −1 − 2 t − t^{2}, −4),
x_{11} = x_{3}x_{4} ∧ x_{9}x_{1} = (−1 + 2 t − t^{2}, −3 − 2 t + t^{2}, −4),
x_{12} = x_{7}x_{10} ∧ x_{11}x_{2} = (1 − 2 t^{2} + t^{4}, −1 + 4 t + 10 t^{2} + 4 t^{3} − t^{4}, 4 + 8 t + 4 t^{2}),
x_{13} = x_{6}x_{11} ∧ x_{10}x_{1} = (−1 − 4 t + 10 t^{2} − 4 t^{3} − t^{4}, 1 − 2 t^{2} + t^{4}, 4 − 8 t + 4 t^{2}),
x_{14} = x_{1}x_{3} ∧ x_{2}x_{4} = (0, 0, 1)

Here x_{α}x_{β} denotes the “join” of x_{α} and x_{β}, and a ∧ b denotes the “meet”. Both operations can be computed in terms of the standard cross-product in IR^{3}.

After fixing a projective basis consisting of the points x_{1}, …, x_{4} the whole construction only depends on the choice of the parameter t. The following matrix gives coordinates for the situation t = 0 (the situation where x_{5} is in the middle of x_{3} and x_{4}).

X_{0} = ( \begin{matrix}1 & 0 & 1 & 0 & 1 & 1 & 2 & 3 & 2 & 3 & 1 & 1 & −1 & 0 \\ 0 & 1 & 0 & 1 & 1 & 2 & 1 & 2 & 3 & 1 & 3 & −1 & 1 & 0 \\ 0 & 0 & 1 & 1 & 2 & 2 & 2 & 4 & 4 & 4 & 4 & 4 & 4 & 1 \end{matrix} )

We can visualize the situation if we normalize the last coordinate for x_{3}, …, x_{14} to 1 by multiplying each vector with a suitable positive scalar. The situation in the plane {(x, y, 1) | x, y ∈ IR} gives an affine image of our vector configuration in IR^{3}. Figure 1 shows the affine situation for a value t slightly smaller than zero. The points x_{1} and x_{2} are the points at infinity that lie on the x-axis and y-axis. The little displacement of x_{5} away from the symmetric position forces that the lines (1, 3), (2, 4) and (12, 13) not to be concurrent (as in the case t = 0).

→ 1 2 ↑ 3 4  5 6  7 8 9 10 11 12 1314 Figure 1

The whole construction sequence has a combinatorial symmetry that is induced by the permutation

π = ( \begin{matrix}1 & 2 & 3 & 4 & 5 & 6 & 7 & 8 & 9 & 10 & 11 & 12 & 13 & 14 \\ 2 & 1 & 4 & 3 & 5 & 7 & 6 & 9 & 8 & 11 & 10 & 13 & 12 & 14 \end{matrix} ) .

Evaluating the determinant det(x_{12}, x_{13}, x_{14}) we get

det(x_{12}, x_{13}, x_{14}) = 32 t^{2} − 64 t^{4} + 32 t^{6} = 32t^{2}(t^{2} − 1)^{2},

a polynomial that has a root which is actually a minimum at t = 0.

Figure 2

The fact that this polynomial is symmetric in t is already a consequence of the symmetry of the underlying construction of the configuration and of the symmetric choice of our basis x_{1}, …, x_{4}. A graph of this polynomial is given in Figure 2.

We now define for all (i, j, k) ∈ Λ({1, …, 14}, 3) and σ ∈ {−1, 0, +1}

Ω_{14}^{σ}(i, j, k) := \{ \begin{matrix}σ & if (i, j, k) = (12, 13, 14), \\ χ_{X_{0}} (i, j, k) & otherwise. \end{matrix}

The oriented matroids Ω_{14}^{σ} have a combinatorial symmetry which is induced by π. For all (i, j, k) ∈ Λ({1, …, 14}, 3) and σ ∈ {−1, 0, +1} we have

Ω_{14}^{σ}(π(i), π(j), π(k)) = −Ω_{14}^{σ}(i, j, k).

A realization X of Ω_{14}^{σ} is symmetric if there is a linear involution R: IR^{3} → IR^{3} with R(x_{i}) = x_{π(i)} for i ∈ {1, …, 14}.

Theorem 3.1. The oriented matroids Ω_{14}^{σ} have the following properties:

(i) There is a polynomial function f from ((0, 1) \ \{\frac{1}{2}\}) × (0, ∞)^{10} to the realization space of Ω_{14}^{+} that is an isomorphism of semi-algebraic sets.

(ii) Ω_{14}^{+} has no symmetric realization.

(iii) Ω_{14}^{+} has rational realizations.

(iv) Ω_{14}^{−} is not realizable.

Proof. The construction sequence at the beginning of this section shows that after the choice of the parameter t all points are determined up to multiplication by a positive number. The signs that are identical in Ω_{14}^{+}, Ω_{14}^{0}, and Ω_{14}^{−} are exactly taken for values of t in the open interval (−3 + \sqrt{8}, 3 − \sqrt{8}). (The basis that collapse at the end points of this open interval are (x_{1}, x_{3}, x_{12}) and (x_{2}, x_{4}, x_{13}).) We get realizations of Ω_{14}^{+} exactly for all choices of t in I = (−3 + \sqrt{8}, 0) ∪ (0, 3 − \sqrt{8}). For t = 0 we get a realization of Ω_{14}^{0}. The factor (0, ∞)^{10} in (i) is due to the fact that multiplication of any of the points x_{5}, …, x_{14} by a positive scalar does not change the underlying oriented matroid. This proves (i).

Assume that there was a symmetric realization X of Ω_{14}^{+}. After a suitable projective transformation we may assume that x_{1}, …, x_{4} are located at (1, 0, 0), (0, 1, 0), (1, 0, 1), (0, 1, 1), respectively, and that the reflection R is given by R(x, y, z) = (y, x, z). Since x_{5} is a fix-point of R it must be of the form (x, x, z) ≠ (0, 0, 0). Up to a positive multiple the only possible choice for x_{5} is induced by t = 0 in our construction sequence. For t = 0 the determinant det(x_{12}, x_{13}, x_{14}) evaluates to zero. Hence, there is no symmetric realization. This proves (ii).

If we choose t as a rational number in (−3 + \sqrt{8}, 0) ∪ (0, 3 − \sqrt{8}) we get a rational realization, as stated in (iii). Fact (iv) is a direct consequence of the fact that for t ∈ (−3 + \sqrt{8}, 3 − \sqrt{8}) the determinant det(x_{12}, x_{13}, x_{14}) is always positive or zero.

4 Final polynomials

Bi-quadratic final polynomials [2, 8] are special final polynomials that can be found by linear programming. They provide an effective tool to prove non-realizability for a large class of oriented matroids. Here we restrict ourselves to the case of realizability over IR and to the case of oriented matroids in rank 3 on a ground set E = {1, …, n}. Our starting point is the structure of three-term Graßmann-Plücker polynomials. For this the brackets [i, j, k] with i, j, k ∈ E are considered as formal variables. We identify brackets according to the alternating determinant rules:

[i, j, k] = [k, i, j] = [j, k, i] = −[j, i, k] = −[k, j, i] = −[i, k, j].

The polynomial ring in all brackets IR[{[λ] | λ ∈ E^{3}}] modulo these identifications is abbreviated B_{3,n}. (This is a polynomial ring in \binom{n}{3} generators.) For an oriented matroid χ and a bracket monomial [λ^{1}] · [λ^{2}] · . . . · [λ^{k}] we write

χ([λ^{1}] · [λ^{2}] · . . . · [λ^{k}]) := χ(λ^{1}) · χ(λ^{2}) · . . . · χ(λ^{k}).

For a vector configuration X = (x_{1}, …, x_{n}) ∈ IR^{3n} and (i, j, k) ∈ E^{3} we write

[i, j, k]_{X} = det(x_{i}, x_{j}, x_{k}).

Definition 4.1. Let χ be a rank 3 oriented matroid on a finite set E of cardinality n > 3, let τ ∈ E, λ = (a, b, c, d) ∈ E^{4} with |{τ, a, b, c, d}| = 5 and let

\begin{matrix}A := (τ, a, b), & B := (τ, c, d), \\ C := (τ, a, c), & D := (τ, b, d), \\ E := (τ, a, d), & F := (τ, b, c). \end{matrix}

(1) The pair (τ, λ) is called χ-normalized if

χ([A][B]) ≥ 0, χ([C][D]) ≥ 0, χ([E][F]) ≥ 0.

(2) A χ-normalized pair (τ, λ) is called χ-non-degenerate if χ([C][D]) > 0.

(3) For a χ-non-degenerate pair (τ, λ) we call

[A][B] < [C][D] a bi-quadratic inequality if χ([E][F]) > 0,
[A][B] = [C][D] a bi-quadratic equation if χ([E][F]) = 0,
[E][F] < [C][D] a bi-quadratic inequality if χ([A][B]) > 0,
[E][F] = [C][D] a bi-quadratic equation if χ([A][B]) = 0.

In fact (as a consequence of the oriented matroid axioms) for any τ ∈ E and λ ∈ E^{4} there is always a suitable permutation π ∈ S_{4} of the elements in λ such that (τ, π(λ)) is χ-normalized. Furthermore, if [A][B] = [C][D] is a bi-quadratic equation, [C][D] = [A][B] is a bi-quadratic equation as well. The set of all bi-quadratic inequalities of χ will be denoted by B_{χ} and the set of all its bi-quadratic equations will be denoted by A_{χ}. Each element in B_{χ} ∪ A_{χ} is called a bi-quadratic expression. The bi-quadratic expressions can be considered as natural consequences of Graßmann-Plücker relations in the realizable case, as we will see now.

Lemma 4.2. For a vector configuration X ∈ (IR^{d})^{n} and its corresponding oriented matroid χ_{X} we have

(i) [A]_{X}[B]_{X} < [C]_{X}[D]_{X} for all [A][B] < [C][D] ∈ B_{χ_{X}}.

(ii) [A]_{X}[B]_{X} = [C]_{X}[D]_{X} for all [A][B] = [C][D] ∈ A_{χ_{X}}

Proof. \underline{(i):} Assume that [A][B] < [C][D] is a bi-quadratic inequality and let (τ, λ) be the corresponding χ-non-degenerate pair. Let A, …, F be defined as in Definition 4.1. We have χ([E][F]) = 1. The polynomial [A][B] − [C][D] + [E][F] is a Graßmann-Plücker-polynomial. Hence its evaluation is identical to zero for every configuration X ∈ (IR^{d})^{n}:

[A]_{X}[B]_{X} − [C]_{X}[D]_{X} + [E]_{X}[F]_{X} = 0.

Since χ([E][F]) = 1, in any realization X of χ we have [A]_{X}[B]_{X} − [C]_{X}[D]_{X} < 0. This proves the first part of the lemma. \underline{(ii):} Let [A][B] = [C][D] be a bi-quadratic equation and let (τ, λ), E, F be defined as above. Then we have χ([E][F]) = 0. Therefore in any realization X of χ we have [A]_{X}[B]_{X} − [C]_{X}[D]_{X} = 0.

The following definition of bi-quadratic final polynomials is more general than the one given in [2], where only the uniform case (no zero determinants) was considered.

Definition 4.3. For an oriented matroid χ a non-empty collection of bi-quadratic inequalities

[A_{i}][B_{i}] < [C_{i}][D_{i}] ∈ B_{χ}; 1 ≤ i ≤ k

together with a (possibly empty) collection of bi-quadratic equations

[A_{i}][B_{i}] = [C_{i}][D_{i}] ∈ A_{χ}; k + 1 ≤ i ≤ l

is called a bi-quadratic final polynomial if the following equality holds within the ring B_{3,n} (where brackets are identified according to the alternating determinant rule):

∏_{i=1}^{l}[A_{i}][B_{i}] = ∏_{i=1}^{l}[C_{i}][D_{i}].

Lemma 4.4. [2, Lemma 4.1] If χ admits a bi-quadratic final polynomial, then χ is not realizable over IR.

Proof. Assume on the contrary that χ admits a bi-quadratic final polynomial as defined above, and χ is realizable, i.e χ = χ_{X} for a suitable vector configuration X. By Lemma 4.2 we have

[A_{i}]_{X}[B_{i}]_{X} < [C_{i}]_{X}[D_{i}]_{X} for all 1 ≤ i ≤ k, and
[A_{i}]_{X}[B_{i}]_{X} = [C_{i}]_{X}[D_{i}]_{X} for all k + 1 ≤ i ≤ l.

At least one proper inequality appears. By definition the products on the left side are all positive and the products on the right side are positive as well. If we multiply all right and all left sides we obtain:

∏_{i=1}^{l}[A_{i}]_{X}[B_{i}]_{X} < ∏_{i=1}^{l}[C_{i}]_{X}[D_{i}]_{X}.

On the other hand the fact that we have a bi-quadratic final polynomial implies

∏_{i=1}^{l}[A_{i}]_{X}[B_{i}]_{X} = ∏_{i=1}^{l}[C_{i}]_{X}[D_{i}]_{X}.

This contradicts the assumption that χ was realizable.

5 Ω_{14}^{−} has no bi-quadratic final polynomial

The main result of this section is:

Theorem 5.1. Let χ^{0}, χ^{+}, χ^{−} be three oriented matroids that differ in exactly one basis μ ∈ Λ(E, 3) with χ^{σ}(μ) = σ. If χ^{0} and χ^{−} are realizable and χ^{+} is not, then χ^{+} cannot have a bi-quadratic final polynomial.

Proof. Assume that a bi-quadratic final polynomial for χ^{+} exists. Let

{[A_{i}][B_{i}] < [C_{i}][D_{i}] | 1 ≤ i ≤ k} ⊆ B_{χ^{+}}

together with

{[A_{i}][B_{i}] = [C_{i}][D_{i}] | k + 1 ≤ i ≤ l} ⊆ A_{χ^{+}}

be a bi-quadratic final polynomial for χ^{+} consisting of k > 0 bi-quadratic inequalities and l − k ≥ 0 bi-quadratic equations. Since [τ, b, c][τ, e, f] = [τ, c, b][τ, f, e] holds, we may assume that every bracket in the bi-quadratic final polynomial has positive signature. In each bi-quadratic expression the bracket [μ] can be contained at most once (since each three-term Graßmann-Plücker-polynomial contains each bracket at most once). Since we have a bi-quadratic final polynomial the overall number r of occurrences of [μ] on the right sides of the expressions equals the number of overall occurrences of [μ] on the left sides. Thus we may assume that the bi-quadratic expressions are sorted in a way that each expression of the form [A_{i}][B_{i}] ≤ [C_{i}][D_{i}] with μ ∈ {A_{i}, B_{i}} is directly followed by an expression [A_{i+1}][B_{i+1}] ≤ [C_{i+1}][D_{i+1}] with μ ∈ {C_{i+1}, D_{i+1}} (indices taken modulo r).

With suitable τ_{i} ∈ E and λ_{i} := (λ_{i1}, …, λ_{i4}) ∈ E^{4} we have

\begin{matrix}A_{i} := (τ_{i}, λ_{i1}, λ_{i2}), & B_{i} := (τ_{i}, λ_{i3}, λ_{i4}), \\ C_{i} := (τ_{i}, λ_{i1}, λ_{i3}), & D_{i} := (τ_{i}, λ_{i_{2}}, λ_{i_{4}}). \end{matrix}

With this choice the Graßmann-Plücker polynomials

{τ_{i}|λ_{i}} := [A_{i}][B_{i}] − [C_{i}][D_{i}] + [E_{i}][F_{i}] are χ-normalized and χ-non-degenerate. By Definition 4.1 we know that χ([E_{i}][F_{i}]) is +1 for 1 ≤ i ≤ k and 0 for k + 1 ≤ i ≤ l. Furthermore χ([A_{i}][B_{i}]) = 1 and χ([C_{i}][D_{i}]) = 1 for all 1 ≤ i ≤ l. We define monomials

m_{i} := ∏_{j=1}^{i−1}([A_{i}][B_{i}]) · ∏_{j=i+1}^{l}([C_{i}][D_{i}])

and consider the polynomial

p := ∑_{i=1}^{l}(m_{i} · {τ_{i}|λ_{i}}).

We have

m_{i} · [A_{i}][B_{i}] = m_{i+1} · [C_{i+1}][D_{i+1}].

Furthermore, since all bi-quadratic expressions together form a bi-quadratic final polynomial, we also have

m_{l} · [A_{l}][B_{l}] = ∏_{i=1}^{l}([A_{i}][B_{i}]) = ∏_{i=1}^{l}([C_{i}][D_{i}]) = m_{1} · [C_{1}][D_{1}].

Thus, canceling pairwise vanishing summands in p yields:

p = ∑_{i=1}^{l}(m_{i} · [E_{i}][F_{i}]).

(In fact p is an ordinary final polynomial for χ^{+} in the sense of Bokowski & Sturmfels [1, 5].) Since all Graßmann-Plücker-polynomials that are involved were χ-normalized we get:

χ(m_{i} · [E_{i}][F_{i}]) = 1 for i = 1, …, k

and

χ(m_{i} · [E_{i}][F_{i}]) = 0 for i = k + 1, …, l.

By our assumption on the order of the bi-quadratic expressions in each of the monomials m_{i} = [μ]^{r} · m′_{i} the bracket [μ] occurs with degree r (the total number of occurrences of [μ] on the right side of bi-quadratic expressions). Thus if we consider the polynomial

p′ := ∑_{i=1}^{l}(m′_{i} · {τ_{i}|λ_{i}}) = ∑_{i=1}^{l}(m′_{i} · [E_{i}][F_{i}]).

each summand m′_{i} · [E_{i}][F_{i}] is either linear in [μ] (in case that μ ∈ {E_{i}, F_{i}}) or does not contain [μ] at all. Furthermore (since χ^{+}(μ) = 1) we have χ(m′_{i} · [E_{i}][F_{i}]) = 1 for i = 1, …, k and χ(m′_{i} · [E_{i}][F_{i}]) = 0 for i = k + 1, …, l. Thus we have

p′ = [μ] · ∑_{i=1}^{s} p_{i} + ∑_{i=1}^{l−s} q_{i}

with χ(p_{i}) and χ(q_{i}) all either zero or positive and at least one of these monomials positive. Observe that the p_{i} and q_{i} are independent on [μ] thus the corresponding signs χ(p_{i}) and χ(q_{i}) are identical for χ^{+}, χ^{0} and χ^{−}.

We now replace the brackets of p′ by the values of the actual determinants of a realization of χ^{0} (we know that such a realization does exist). The polynomial p′ is a linear combination of Graßmann-Plücker-polynomials, hence this expression must evaluate to zero. Since χ^{0}([μ]) = 0 and the monomials q_{i} evaluate to a non-negative number we can conclude that χ(q_{i}) = 0 for all i = 1, …, l − s.

Using this information we now consider the case where we replace the brackets of p′ by the values of the actual determinants of a realization of χ^{−} (we know that such a realization does also exist). The summands q_{i} for all i = 1, …, l − s evaluate to zero. Each of the summands [μ] · p_{i} for i = 1, …, s evaluates either to zero or to a number with sign since χ^{−}([μ]) = −1. At least one non-zero summand occurs. Thus we have a non-empty collection of negative numbers summing up to zero.

Corollary 5.2. The oriented matroid Ω_{14}^{−} is not realizable and does not admit a bi-quadratic final polynomial.

Proof. The non-realizability of Ω_{14}^{−} was proved in Theorem 3.1. Since Ω_{14}^{+} and Ω_{14}^{0} are realizable Theorem 5.1 applies and the corollary follows.

References

[1] A. Björner, M. Las Vergnas, B. Sturmfels, N. White & G.M. Ziegler, Oriented Matroids, Encyclopedia of Mathematics, Vol. 46, Cambridge University Press 1993.

[2] J. Bokowski & J. Richter, On the finding of final polynomials, Eur. J. Comb., 11 (1990), 21–34.

[3] J. Bokowski, J. Richter & B. Sturmfels, Nonrealizability proofs in computational geometry, Discrete Comput. Geom., 5 (1990), 333–350.

[4] J. Bokowski & B. Sturmfels, Programmsystem zur Realisierung orientierter Matroide, Preprint, Universtät Köln, (1985), 33 p.

[5] J. Bokowski & B. Sturmfels, Computational Synthetic Geometry, Lecture Notes in Mathematics, 1355, Springer-Verlag, Berlin Heidelberg 1989.

[6] N.E Mnëv, On manifolds of combinatorial types of projective configurations and convex polyhedra, Soviet Math. Doklady, 32 (1985), 335–337.

[7] N.E Mnëv, The universality theorems on the classification problem of configuration varieties and convex polytopes varieties, in: Viro, O.Ya. (ed.): Topology and Geometry — Rohlin Seminar, Lecture Notes in Mathematics 1346, Springer-Verlag, Berlin Heidelberg 1988, 527–544.

[8] J. Richter-Gebert, On the Realizability Problem of Combinatorial Geometries – Decision Methods, Dissertation, TH-Darmstadt, 1992, 144 p.

[9] J. Richter-Gebert, Realization spaces of 4-polytopes are universal, Habilitationsschrift TU-Berlin, 1995; Preprint 448/1995, TU Berlin 1995, 112 p.

[10] J. Richter-Gebert & G.M. Ziegler, Oriented Matroids, Preprint, TU Berlin, September 1995, 28 p.; CRC Handbook on “Discrete and Computational Geometry” (J.E. Goodman, J. O’Rourke, eds.), to appear.

[11] P. Shor, Stretchability of pseudolines is NP –hard, in: Applied Geometry and Discrete Mathematics – The Victor Klee Festschrift (P. Gritzmann, B. Sturmfels, eds.), DIMACS Series in Discrete Mathematics and Theoretical Computer Science, Amer. Math. Soc., Providence, RI, 4 (1991), 531–554.

[12] P.Y. Suvorov, Isotopic but not rigidly isotopic plane systems of straight lines, in: Viro, O.Ya. (ed.): Topology and Geometry — Rohlin Seminar, Lecture Notes in Mathematics 1346, Springer-Verlag, Heidelberg 1988, 545–556.

Jürgen Richter-Gebert

Technische Universität Berlin FB Mathematik, Sekr. MA 6-1 Straße des 17. Juni 136 D-10623 Berlin Germany richter@math.tu-berlin.de