Oriented Matroids

In Chapter 4 we learned about at least five versions of FARRAS’ Lemma. Is there any one which is more “natural” than the others? We propagate that the “linear subspace version” (Theorem 4.6) is the most natural one: It is both simple and “selfdual”, i.e. both alternatives a) and b) arise from each other by simply replacing L by L⊥. If we agree that Theorem 4.6 is the most natural way to state FARKAS’ Lemma, the next question that arises is: Are dual pairs of vector spaces the most natural structures for stating Theorem 4.6? More precisely, given two sets of vectors, say, S and S1 such that an analogue of Theorem 4.6 holds (with L and L⊥ replaced by S an S1, resp.), is it true then that S and S give rise to a dual pair of vector spaces in some way? As one might guess, the answer is no (for otherwise we would probably not have written this book). In fact, a systematic analysis of those properties of vector spaces which make L and L⊥ satisfy FARKAS’ Lemma will lead us to discover more general structures, called “oriented matroids”. These are, as we will see, the most general (and hence the most simple or “natural”) structures satisfying an analogue of FARKAS’ Lemma.