Oriented Lagrangian Matroids

arXiv:math/0010237v1 [math.CO] 25 Oct 2000 Oriented Lagrangian Matroids Richard F. Booth∗ Alexandre V. Borovik∗ Israel M. Gelfand† Neil White‡§ The aim of this paper is to develop, by analogy with the theory of oriented (ordinary) matroids [2], an oriented version of the theory of Lagrangian symplectic matroids [7]. Recall that the concept of an oriented matroid axiomatises, in combinatorial form, the properties of the ensemble of non-zero k × k minors of a real k × n matrix A, say. The k-subsets of indices of columns of A such that the corresponding k × k minors are non-zero form the collection of bases of an (ordinary) matroid [18]. When we consider also the signs of these minors we obtain a considerably richer combinatorial structure, an (ordinary) oriented matroid. These structures have important applications in combinatorics, geometry and topology. To give an idea of the concept of an oriented Lagrangian matroid, we consider one of the simplest situations in which they arise. Assume that we have a symmetric n × n matrix A over some field K. The collection of sets of row (equivalently, column) indices K ⊆ { 1, . . . , n } corresponding to non-zero diagonal minors |ai j |i, j∈K of A forms what is known as a ∆-matroid [10] (we include / and specify that a 0 × 0 minor takes the value for formal reasons the empty set K = 0, 1). These are equivalent structures to Lagrangian symplectic matroids. When K = R, we may consider also the signs of these minors. What follows in this introduction is a very elementary description of the resulting combinatorial structure; all necessary proofs, and detailed explanations, may be found later in the paper. Let our symmetric n × n matrix A over K have columns indexed by I = 1, . . . , n, and let e1 , . . . , en denote the standard basis in Rn . Given some B ⊆ I we define a point in Rn by B → ∑ ei − ∑ ei , i∈B i∈B / a vertex of the n-dimensional hypercube H = [−1, 1]n . Consider the convex hull of the points induced from non-zero minors of A in this way. It can be shown that this polytope, P, satisfies: (*) All vertices of P are vertices of H, and edges of P are either edges of H or diagonals of 2-dimensional faces of H. Notice that if points corresponding to B,C ⊆ I are at opposite ends of an edge of H, without loss of generality C = B ⊔ {i} for some 1 6 i 6 n. We now introduce some extra structure when K = R by orienting edges of P which coincide with those of H. Given B,C as above, we direct the corresponding edge from B to C if the corresponding minors have the same sign, and from C to B if the signs differ. It will be shown in Theorem 12 that the resulting partially oriented 2-skeleton of the polytope satisfies ∗ {richard.booth}{alexandre.borovik}@umist.ac.uk † igelfand@math.rutgers.edu ‡ white@math.ufl.edu § Partially supported by EPSRC Grant GR/M24707. 1 R. F. B OOTH ET AL . O RIENTED L AGRANGIAN M ATROIDS 2 (∗∗) In any 2-dimensional face, the same number of edges are oriented clockwise as anti-clockwise. We may abstract this situation as follows. (∗) is a cryptomorphic definition of a Lagrangian symplectic matroid [7], and (∗∗) is one of a pair of equivalent definitions of orientations of oriented Lagrangian matroids given in this paper. This is a natural definition, as the following observation shows: when the construction from a symmetric matrix is followed the signs of all diagonal minors may be recovered from the partially oriented polytope. Consequently, the rank and signature of the corresponding quadratic form are preserved within the combinatorial information (Corollary 13). In both cases, the recovery of this information is both geometric and uncomplicated. The reader should not be surprised by the fact that we define new combinatorial concepts in geometric terms. We work in the framework of the theory of Coxeter matroids, of which (ordinary) matroids and Lagrangian symplectic matroids are special cases corresponding to the Coxeter groups An and BCn . Combinatorial properties of Coxeter matroids are easily translated into the properties of the corresponding polytopes, and vice versa [6, 9]. In particular, the adjacency of vertices of the polytope P can be expressed entirely in terms of the Lagrangian symplectic matroid associated with the matrix A (Theorem 2 below; it is a special case of [9]). Moreover, the combinatorial type of the polytope P (in particular, its faces) can be read from the corresponding Lagrangian symplectic matroid [8]. One of the uses of oriented matroids is to provide a finer stratification of the real Grassmannian Gn,k (R) than that given by thin Schubert cells [4, 13]. If X and Y are two points in Gn,k (R) in the same thin Schubert cell C (which is equivalent to saying that they represent the same matroid), but which represent different oriented matroids, then they belong to different connected components of C. This finer stratification was used by MacPherson in his construction of the combinatorial model for the Grassmannian [14]. Similarly, oriented Lagrangian symplectic matroids provide a finer stratification of the variety of maximal isotropic subspaces of a real symplectic 2n-dimensional vector space (see Sections 1.2 and 3). Points in a thin Schubert cell representing different oriented Lagrangian symplectic matroids lie in distinct connected components of the thin Schubert cell. It would be interesting to use our concept of oriented Lagrangian symplectic matroid for the construction, by analogy with [14], of a combinatorial model for the variety of maximal isotropic subspaces of a real symplectic 2n-dimensional vector space. We wish to emphasise that oriented Lagrangian symplectic matroids should not be viewed as generalisations of oriented ordinary matroids. In fact, the natural generalisation of oriented matroids is provided by oriented even ∆-matroids [16, 17] (or oriented Lagrangian orthogonal matroids, in terminology of [3]). Every (ordinary) matroid is a Lagrangian orthogonal matroid, and every Lagrangian orthogonal matroid is also a Lagrangian symplectic matroid, which can be explained from the embeddings of root systems An−1 < Dn < Cn [7, 8]. However, the concepts of orientation for Lagrangian orthogonal and symplectic matroids are very different because they reflect the geometric properties of two different geometric objects: the varieties of maximal isotropic subspaces in the space R2n with a non-degenerate symmetric or a skew symmetric form. Not surprisingly, (ordinary) oriented matroids fit more happily into the geometry of a symmetric scalar product. See [3] for more detail on orthogonal orientation. R. F. B OOTH ET AL . O RIENTED L AGRANGIAN M ATROIDS 3 1 Symplectic Matroids This exposition of symplectic matroids follows [7]. For a more general discussion of the theory of Coxeter matroids, of which symplectic matroids are a special case, see [8]. 1.1 Symplectic and Lagrangian Matroids Let I = {1, 2, . . . , n}, I ∗ = {1∗ , 2∗ , . . . , n∗ }, and J = I ∪ I ∗ . We define a pair of maps ∗ : I → I ∗ by i → i∗ and ∗ : I ∗ → I by i∗ → i, giving us ∗ : J → J an involutive permutation of J. We say that a subset of K ⊂ J is / We denote by Jk the collection of all admissible admissible if and only if K ∩ K ∗ = 0. k-subsets of J. (We often use the word ‘collection’ to denote a set of sets, in order to avoid confusion.) An admissible permutation w of J is one which satisfies w(i∗ ) = w(i)∗ for each i ∈ J. We call the group of all admissible permutations W , and remark that it is the hyperoctahedral group BCn , that is, it is isomorphic to the group of symmetries of the n-cube [−1, 1]n in the real Euclidean space Rn . Consider: with e1 , . . . , en the standard orthogonal basis in Rn , we see that W acts as follows: for i ∈ I we set ei∗ = −ei and wei = ew(i) . It is not hard to see that W is exactly the group of all orthogonal transformations of Rn preserving the set of vectors {±e1 , . . . , ±en } and thus the n-cube. We order J by n∗ < (n − 1)∗ < . . . < 1∗ < 1 < 2 < . . . < n and for each w ∈ W define a new ordering 6w on J by putting i 6w j if and only if w−1 i 6 w−1 j. An admissible ordering ≺ of J is defined by i ≺ j implies j∗ ≺ i∗ , so we see that for w ∈ W , 6w is admissible. Now extending the concept of orderings to elements of Jk , we take ≺ an admissible ordering on J, and let A, B ∈ Jk with A = {a1 ≺ a2 ≺ . . . ≺ ak } and B = {b1 ≺ b2 ≺ . . . ≺ bk }. Then we set A ≺ B if and only if ai ≺ bi for each i = 1, . . . , k. Take B ⊆ Jk and let M be the triple (J,∗ , B ). Then M is a symplectic matroid if it satisfies Axiom 1 below: Axiom 1 (Maximality Property) For every w ∈ W there exists A ∈ B such that B 6w A for every B ∈ B . i.e. there is a unique w-maximal element of B for each w ∈ W . If the axiom holds, we call B the collection of bases of M. The cardinality k of the bases is called the rank of M. A symplectic matroid may be considered as a Coxeter matroid for BCn . A Lagrangian matroid is a symplectic matroid of rank n; this means that for each i ∈ I, we have either i ∈ A or i∗ ∈ A for every A ∈ B . This paper is concerned primarily with Lagrangian matroids. R. F. B OOTH ET AL . O RIENTED L AGRANGIAN M ATROIDS 4 1.2 Representability Let A, B be a pair of k × n matrices over a field F. Let C be the k × 2n matrix (A, B). Assume C has rank k. We label the columns of A with I in order, and similarly those of B with I ∗ , so that the columns of C are indexed by J. Define B ⊆ Jk by X ∈ B if and only if 1. X ∈ Jk and 2. the k × k minor consisting of the j-th column of C for all j ∈ X is non-zero. Then we have Theorem 1 If ABt is symmetric, then B is the collection of bases of a symplectic matroid. This result is proven in [7]. We call a symplectic matrix arising from a matrix (A, B) with ABt symmetric a representable symplectic matroid, and say that (A, B) is a representation of it over F. We sometimes refer to this as a symplectic representation, to distinguish it from other kinds of representations. Also, note that a representable symplectic matroid is Lagrangian if and only if A and B are both n × n square matrices and (A, B) is full rank. Note that this result may be given in terms of isotropic subspaces of symplectic vector spaces. Let V be a vector space with basis e1 , . . . , en , e1 ∗ , . . . , en ∗ . Define the standard symplectic bilinear form on V by putting  if i ∈ I and j = i∗ .  1 < ei , e j >= −1 if j ∈ I and i = j∗ .  0 otherwise. Consider an isotropic subspace U of V (that is, < u, v >= 0 for all u, v ∈ U). Take a basis of U and write these as row vectors in terms of the above basis in the above order, thus forming a k × 2n matrix C of rank k. This is then a representation of a symplectic matroid, as above; the isotropic condition is equivalent to the symmetry of ABt . Simple matrix algebra shows that the matroid represented is dependent only on the subspace chosen; thus, we may speak of a subspace being a representation. A Lagrangian subspace (maximal isotropic) corresponds to a Lagrangian matroid. We now define the concept of a thin Schubert cell. Consider the variety of all Lagrangian subspaces of V . Each such subspace has a corresponding Lagrangian matroid, and the set of subspaces corresponding to the same matroid is called a thin Schubert cell. Thin Schubert cells over R are in general not connected in the real topology. Indeed, two subspaces U and U ′ corresponding to the same symplectic matroid, but with distinct signs of non-zero k × k minors in their matrices C and C′ cannot be continuously transformed one into another within the same thin Schubert cell and thus belong to distinct connected components. This concept of representation is related to one of several given in [10], in which a representation consists of a symmetric, n × n matrix A, and is equivalent to our concept of a representation with the additional requirement that B = In , the identity matrix, and that k = n. Our Lagrangian matroids can be shown to be equivalent to constructions referred to as symmetric matroids in [10]; see [16] for a proof of this. R. F. B OOTH ET AL . O RIENTED L AGRANGIAN M ATROIDS 5 Figure 1: (−1, −1, 1) (−1, 1, 1) s ✚❅ ✚ ❅ ✚ ✚ ❅ ✚ (1, −1, 1) ❅ ✚ s (1, 1, 1) ❅ ❅ ❅ ❅ ❅ ❅ ❅ ❅ ❅ ❅ ❅ ❅ ❅ (−1, −1, −1) ❅ s ❅s ✚ ✚ ❅ ✚ (−1, 1, −1) ✚ ❅ ✚ ✚ ✚ ✚ ❅ ✚ ✚ (1, −1, −1) ❅ ✚ s s ❅✚ (1, 1, −1) 1.3 Symplectic Matroid Polytopes We now return to the n-cube [−1, 1]n in Rn . We again set e1 , . . . , en to be the standard orthonormal basis in Rn and define e1∗ = −e1 , . . . , en∗ = −en . Now given A ∈ Jk we set eA = ∑ e j ∈ Rn j∈A so that, for example, the set {eA |A ∈ Jn } is the set of vertices of the n-cube. We define the matroid polytope of a symplectic matroid M to be the convex hull of the points eA , A ∈ B . For example, the matroid polytope corresponding to the matroid represented by the matrix   1 1 1 1 0 0  1 2 2 0 1 0  1 2 2 0 0 1 can be drawn as shown in Figure 1, where dots represent bases, solid lines edges of the matroid polytope and dotted lines edges of the n-cube not present in the polytope. The bases of this matroid are 1∗ 2∗ 3∗ , 12∗ 3∗ , 1∗ 23∗ , 1∗ 2∗ 3, 123∗, 12∗ 3 (notice that we write, for example, 123 rather than {1, 2, 3}. This abbreviated notation is usual in matroid theory). We shall be specifically interested in Lagrangian matroid polytopes, that is, matroid polytopes corresponding to Lagrangian matroids. Some of the properties of these structures follow. The points eA for A ∈ B are exactly the vertices of the matroid polytope. In the sequel we shall often simply write A in the abbreviated notation used above rather than eA . The matroid polytope is inscribed in the n-cube, and in the Lagrangian case its vertices are vertices of the n-cube also. The edges of a Lagrangian matroid polytope can be of just two types, which may be R. F. B OOTH ET AL . O RIENTED L AGRANGIAN M ATROIDS 6 distinguished by their lengths. Type 1 is of length 2, for example the edge from 12∗ 3 to 1∗ 2∗ 3 in Figure 1. If A and B the bases corresponding to the end vertices of an edge of ∗ type 1, then they √ are connected by a short exchange, A = B∆{i, i } for some i. Type 2 is of length 2 2, for example the edge from 12∗ 3 to 123∗ in Figure 1. In that case, the end bases A and B of the edge are connected by a long exchange: A = B∆{i, j, i∗ , j∗ } with i 6= j, j∗ . In fact, a polytope is a Lagrangian matroid polytope in this sense if and only √ if its vertices are vertices of the n-cube and its edges are only of lengths 2 and 2 2. For more details and proofs see [7, 12]. These results rely heavily on the Gelfand–Serganova theorem, of which the relevant special case for symplectic matroids is Theorem 10 in [7]. We shall call an edge of type 1 a short exchange or short edge and an edge of type 2 a long exchange. Furthermore, it is easily seen that every edge in the Lagrangian case lies upon the surface of the n-cube, that is within one of the 2-dimensional faces of the n-cube. In fact, it is not hard to show Theorem 2 Two bases A, B of a Lagrangian matroid are adjacent if and only if 1. They are connected by a short exchange (A = B∆{i, i∗ }); or 2. They are connected by a long exchange (A = B∆{i, j, i∗ , j∗ } with i 6= j, j∗ ) and |{B∆{i, i∗ }, B∆{ j, j∗ }} ∩ B | < 2. Proof Two vertices of a polytope are adjacent exactly if there exists a linear functional which takes equal, maximal values on the vertices, and smaller values on all other vertices of the polytope. Such a functional in the first case is L= ∑ k∈(A∩B∩I) xk − ∑ xi , k∗ ∈(A∩B∩I ∗ ) by inspection. In the second case, we have the condition that not both of the two sets listed are bases. Suppose without loss of generality that C = B∆{i, i∗ } is not a basis. Then L = ∑ xk − ∑ xk + ∑ xk − ∑ xk k∈(C∩I) k∗ ∈(C∩I ∗ ) k∈(A∩B∩I) k∗ ∈(A∩B∩I ∗ ) is clearly a required functional. ⋄ We can show that in the Lagrangian case, the faces of the matroid polytope can only be the following: sSquare A square with short edges (see, for example, the face of Figure 1 whose vertices all contain 2∗ ). lSquare A square with long edges (an example follows). nsRect A rectangle with two short and two long edges (see Figure 1). iTri An isosceles triangle with two short and one long edge (see Figure 1). eqTri An equilateral triangle with long edges (any face of Figure 2, defined later). R. F. B OOTH ET AL . O RIENTED L AGRANGIAN M ATROIDS The matroid polytope of the representation  0 1 0 0  1 0 0 0   0 0 0 1 0 0 1 0 1 0 0 0 0 1 0 0 0 0 1 0 7  0 0   0  1 can be easily seen to be a square with long edges, embedded in 4-space. Again, for details, see [12]; these results all follow without great difficulty from results in [7] and [6]. 2 Oriented Lagrangian Matroids Let M = (J, ∗, B ) be a Lagrangian matroid. Let F ∈ B be a basis of M; we shall call it the fundamental basis. The fundamental basis defines a partial ordering on Jn and thus on B in the following way. The height h(A) of A ∈ Jn relative to F is defined to be h(A) = n − |A ∩ F|. Although h(A) is dependent on F, we haven chosen not to emphasise this fact in our notation. Notice that if we choose an admissible ordering in which the smallest n elements are those of F, then F is clearly the unique minimal basis in this ordering and this admissible ordering never disagrees with the partial ordering; if something is higher in the admissible ordering, then it is at least as far from F in height. Let ∆ signify the symmetric difference operator, A∆B = (A ∪ B) r (A ∩ B). Notice that a 2–dimensional face of the hypercube has vertices of the form {A, A∆{i, i∗ }, A∆{ j, j∗ }, A∆{i, i∗ , j, j∗ }}, and recall that such faces contain all edges of the Lagrangian matroid polytope. Then we see that such a face has one vertex closest to F, one vertex furthest from F, and the other two vertices at the same distance from F with respect to height. We call an edge of the matroid polytope between these last two vertices a horizontal long edge (relative to F). The other possible type of long edge is called a vertical long edge. To illustrate, we show Figure 2, where the fundamental basis 1∗ 2∗ 3∗ is shown as a larger dot than the other bases. In this polytope, those edges incident with the fundamental basis are vertical long edges, and the other edges are all horizontal long edges. It can be shown that this is a symplectic matroid; however, it is not representable in the sense used in this paper other than over a field of characteristic 2. Over GF(2), it can be represented as   0 1 1 1 0 0  1 0 1 0 1 0 . 1 1 0 0 0 1 Let sF : B → {+1, −1} be a map from the collection of bases of M onto the two signs. We say that sF (A) for A ∈ B is the sign of the basis A relative to the fundamental basis F. Then we say that sF is a relative sign function on M with respect to F if the following four axioms are satisfied (in addition to the Maximality Property). We shall say that sF defines an orientation on M. Abusing the terminology, we shall also call sF an orientation of M relative to F, although this usage does not agree well with the conventions of the theory of oriented (ordinary) matroids. Axiom 2 If there is a horizontal long edge (relative to F ) between A, B ∈ B then sF (A) = sF (B). R. F. B OOTH ET AL . O RIENTED L AGRANGIAN M ATROIDS 8 Figure 2: s(−1, 1, 1) ✘✘✘ ✘ ✘✘✘ ✘✘ ✘ ✘ ✘ ✘✘✘ (1, −1, 1) s✘✘ ❅ ❭ ❅ ❭ ❭❅ ❭❅ ❭❅ ❭❅ ❭✈❅ (−1, −1, −1) ❩❅ ❩❅ ❩ ❅ ❩ ❩ ❅ ❩ ❅s (1, 1, −1) Axiom 3 If there is a vertical long edge (relative to F ) between A, B ∈ B then sF (A) = −sF (B). Axiom 4 In a square 2–dimensional face with short edges, (type sSquare), if three bases have one sign relative to F and the fourth the other, that fourth basis must be the highest or lowest basis with respect to F in the face. Axiom 5 sF (F) = +1. Notice that each of these axioms may be checked one 2-dimensional face of the hypercube at a time, as every edge lies in a such a face and the short-sided squares of Axiom 4 are such faces. We now discuss change of fundamental basis. Assume sF is an orientation of M relative to F. Definition 1 For A, G ∈ B we define s(G, A) = sF (A) · sF (G) · (−1)|Gr(F∪A)| . Theorem 3 The function s : B × B → { +1, −1 } defined above satisfies 1. For all G ∈ B , sG ( . ) = s(G, . ) is an orientation of M relative to the fundamental basis G; that is, it satisfies Axioms 2–5. 2. For all G, H, A ∈ B , we have s(G, A) = s(H, A)s(H, G)(−1)|Gr(H∪A)| . R. F. B OOTH ET AL . O RIENTED L AGRANGIAN M ATROIDS 9 This is easily proven from the axioms and definition. We thus extend sF to a function s : Jn × Jn → { +1, −1, 0 } by means of the definition above and s = 0 whenever either of its arguments falls outside B . We say that two orientations sF , sG of M relative to fundamental bases F, G are equivalent whenever sF , sG extend to the same s. Definition 2 We say that the pair (M, s), with M ⊆ Jn and s is a function s : Jn × Jn → {+1, −1, 0}, is an oriented Lagrangian matroid whenever M is a Lagrangian matroid, s = 0 if one of its arguments is not a basis, and s satisfies the conclusions of Theorem 3. We also say that s is an orientation of M. Equivalently, an oriented Lagrangian matroid may be regarded as an equivalence class of orientations relative to fundamental bases. We shall often suppress s and refer to M as an oriented Lagrangian matroid. Definition 3 An even symplectic matroid is one in which the number of starred elements in all bases have the same parity (and so likewise for unstarred). Corollary 4 Any even Lagrangian matroid is orientable, and there is only one possible orientation. Proof Choose a fundamental basis. Orient it with positive sign, and where h is the height function relative to this basis, assign each other basis A the sign (−1)h(A)/2. Note that this is ±1, as h is always even. Axiom 2 is satisfied, since horizontal edges connect only bases of the same height; Axiom 3 is satisfied as vertical edges connect bases of height differential 2. There are no short edges, so Axiom 4 is satisfied, and Axiom 5 was specifically stated above, so this defines an orientation relative to the fundamental basis chosen. It is immediate from consideration of Axioms 2 and 3 that no other orientation is possible. ⋄ Thus, the theory of symplectic orientations of even Lagrangian matroids is rather uninteresting. Notice that symmetric matrices over R which give rise to even Lagrangian matroids are very special. Indeed, it follows from the later result in this paper (Corollary 13) that if A is a real symmetric matrix and all diagonal minors of A of odd dimension equal to zero, then the corresponding quadratic form Q has signature 0 and allows a hyperbolic basis, that is, Q can be transformed to the form x1 x2 + x3 x4 + · · · + x2k−1x2k . Even Lagrangian matroids are in fact just Lagrangian orthogonal matroids (see [15]), and a more interesting orientation scheme for Lagrangian orthogonal matroids is discussed in [3], which is a development of the orientation scheme given in [17] with the extra consideration of what we have called fundamental basis exchange. 3 Index Definition 4 Given a Lagrangian matroid M of rank n, its matroid polytope P and a fundamental basis F, we define an increasing path from a basis α to a basis ω as a list of vertices α = v0 , v1 , . . . , vs = ω and edges e1 , e2 , . . . , es of the matroid polytope such that R. F. B OOTH ET AL . O RIENTED L AGRANGIAN M ATROIDS 10 (1) For 1 6 i 6 s, the endpoints of ei are vi−1 and vi ; and (2) There is admissible ordering ≺ on J such that F is the ≺-minimal basis of M, and, for all 1 6 i 6 s, Ai−1 ≺ Ai for the bases Ai−1 and Ai corresponding to the vertices vi−1 and vi . It follows from [5, Lemma 3.4] that condition (2) is equivalent to the following reformulation in terms of linear functionals. (2*) There is some linear functional L on Rn which is compatible with the height function h (that is, h(A) > h(B) implies that L(A) > L(B) for any bases A and B of M), and which satisfies L(vi ) > L(vi−1 ) for 1 ≤ i ≤ s. We say that the path ({vi }, {ei }) is increasing with respect to L. We can find an L on Rn which agrees with any admissible ordering, and thus with a corresponding height function. Suppose without loss of generality that the ordering is n ≻ n − 1 ≻ · · · ≻ 2 ≻ 1 ≻ 1∗ ≻ · · · ≻ n∗ . Then we may take L(x1 e1 + · · · + xn en ) = ∑n1 3i xi on Rn ; this agrees with the ordering and never takes the same value on different vertices. The existence of an increasing path from a given non-maximal vertex α to some ω such that L(ω) is the maximal value achieved by L on the matroid polytope is a standard fact of linear programming. Definition 5 Given an oriented Lagrangian matroid M and a fundamental basis F, we define the index of M relative to the F as the number of changes of sign in any increasing path from F to a basis at maximal height. Theorem 5 For a given oriented Lagrangian matroid M , index relative to F is welldefined; that is, the number of changes of sign in any increasing path from the fundamental basis to any basis of maximal height from it is the same. We shall spend the remainder of the section proving this in stages. We first prove that any two paths leading to the same basis of maximal height have the same number of changes of sign. Fix F, the fundamental basis, until the end of the section. Lemma 6 If two such paths e, f differ only as to the route taken through a single twodimensional face h of the matroid polytope, then they have the same indices. Proof This can be checked, case by case, by considering the restrictions that the axioms place on each of the possible face types listed in the previous section. We exhibit the first the case of the rectangle nsRect. Notice that short edges connect two bases whose heights differ by 1; thus, the four vertices of the face take at least two different heights. Let a vertex of the face of minimal height correspond to the basis A. Then the other vertices are B = A∆{i, i∗ , j, j∗ }, C = A∆{k, k∗ }, D = A∆{i, i∗ , j, j∗ , k, k∗ } for some i, j, k ∈ I satisfying |{i, i∗ , j, j∗ , k, k∗ }| = 6. The short edges are AC and BD, the long edges AB and CD. Suppose there are two vertices of the same height. Then both long exchanges are horizontal, and s(F, A) = s(F, B), s(F,C) = s(F, D) where F is the fundamental basis, by Axiom 2. If s(F, A) = s(F,C) also, the case becomes trivial, R. F. B OOTH ET AL . O RIENTED L AGRANGIAN M ATROIDS 11 so assume otherwise. As paths must be non-decreasing in height, a path through this face travels exactly one short edge if it moves from one of A, B to one of C, D and no short edges otherwise. As sign changes take place exactly when traversing short edges, the case follows. If there are not two vertices at the same height, then both long edges are vertical, and thus induce sign changes. Now h(A) < h(C) < h(B) < h(D). The only journey for which there is a choice of two increasing paths is A → D, which may take place as AC + CD or AB + BD; if there is no choice of increasing paths, the case is trivial. Axiom 3 gives s(F, A) = −s(F, B) and s(F,C) = −s(F, D). If s(F, A) = s(F,C) then we obtain s(F, B) = s(F, D) and both paths contain one sign change. Alternatively, if s(F, A) = −s(F,C) then we obtain s(F, B) = −s(F, D) and both paths contain two sign changes. This establishes the result in this case. We now exhibit the case of the triangle iTri. Let A, B be the bases at the ends of the long edge and C the third basis. If the long edge is vertical, with say A lowest, the only possible paths are AB and ACB. Since the edge is vertical, B is of the opposite sign to A, and so whichever sign C takes, either path has one sign change. Suppose now AB is horizontal. Thus A and B take the same sign, and since any pair of paths must either both enter or both leave at C (depending on whether it is higher or lower than AB), the result is clear. Similar reasoning proves the lemma for the other types of two-dimensional faces. ⋄ The next two lemmata are proven for general convex polytopes. An admissible linear functional is one which is not constant along any edge of the convex polytope; we have exhibited such a functional which agrees with a given admissible ordering earlier. Lemma 7 If α is a vertex of the convex polytope P (not necessarily a matroid polytope), L an admissible linear functional, and e and f edges of P which are incident to α and increasing for L when we head away from α, then there exists a path of two-dimensional faces ( so that successive faces in the path have an edge in common ) incident to α connecting e to f and all on the L-positive side of α. Proof First cut P by the hyperplane H which is constant for L and passes through α, letting P′ be the resulting polytope containing e and f . Now let P′′ be the vertex figure of P′ at α. Now P′′ has a facet H ′′ contained in H, and vertices e′′ and f ′′ corresponding to the original edges e and f . Now all we want is a path of edges from e′′ to f ′′ which misses H ′′ ; those edges will then correspond to the desired two-dimensional faces in P. This now follows easily from Theorem 15.4 in [11]. ⋄ Lemma 8 Any two paths e = ({vi }, {ei }) , f = ({wi }, { fi }) increasing relative to the same L from v0 = w0 = α to vs = wt = ω with L maximal in the polytope at ω may be transformed into each other in steps, with each step involving only a transformation within a single 2–dimensional face of the polytope (a transformation facewise), and with the path at each step still an increasing path relative to L. Proof Set P(α) to be the assertion that the theorem holds for some particular α as above, and now attempt to prove P(α) for every vertex in the polytope (which is exactly the theorem) by an induction we shall call (∗). We must prove: R. F. B OOTH ET AL . O RIENTED L AGRANGIAN M ATROIDS 12 Basis of (*) P(ω) holds. Inductive Step of (*) Given that P(γ) holds for all vertices γ with L(γ) > L(α), we may deduce P(α). The basis is clearly trivial. The previous lemma tells us that we can find a path of two-dimensional faces h1 , . . . , hk of the polytope where each face hi has two edges gi−1 , gi incident to α, g0 = e1 and gk = f1 , and all the gi ’s increase going away from α. Let Q(k) be the assertion that P(α) holds when the number of faces above is exactly k. If we can prove Q(k) for all k under the inductive hypothesis of (∗), the theorem is complete. We thus assume P(γ) for all vertices γ with L(γ) > L(α), and proceed by induction (∗∗) on k. Basis of (**) Q(0) holds. Inductive Step of (**) Q(k − 1) implies Q(k). Let β be the point at the end of gk . If k = 0, the two paths have the same first edge, and since L(β) > L(α) we have P(β); but the two paths differ only after β, and so P(α). Thus the basis of (∗∗) holds. Take now k > 0. If β is the vertex of maximal L in the face hk , then there is an increasing path segment from α through gk−1 around the edge of the face to β, which then gives us an alternative path replacing f through a transformation facewise with k replaced by k − 1, completing the induction (∗∗). If not, we can replace the path from β to ω with one that goes through the point of maximal L in the face, using again P(β), and now continue as above. This again gives a situation where k is decreased by one after a transformation facewise, and so the induction is complete. ⋄ These lemmata suffice to prove the theorem for all increasing paths relative to the same linear ordering finishing at the same basis of maximal height. If we can exhibit a path strictly increasing with respect to height, that is increasing and without horizontal edges, this is increasing relative to any L agreeing with height, and we will have the result for all increasing paths to the same basis of maximal height. Consider some ω of maximal height, and take α the fundamental basis. It is now convenient to turn the situation ‘upside down’, as ω may not be unique of maximal height, but α is certainly unique of minimal height. If we suppose for convenience that α = {1∗ , . . . , n∗ } = (−1, . . . , −1) as a point in the space, and set a functional L = − ∑ni=1 xi for a point with co-ordinates (xi ), then we see easily that α is maximal in L and that L is constant along horizontal edges. From linear programming, we know that from any non-maximal point there extends a strictly increasing edge. Thus we may find a never-horizontal path from ω to α, which is the reverse of the path required. It remains only to prove that the theorem holds for increasing paths terminating at different bases of maximal height. Notice that any two such bases may be connected by a path of horizontal long edges. It thus suffices to show that two paths terminating at adjacent vertices ω, ω′ of maximal height contain the same number of sign changes. Now, we may replace both paths by never-horizontal paths p, p′ respectively as above. Consider any admissible linear functional L agreeing with height (we have seen that such things exist). From admissibility, without loss of generality L(ω) < L(ω′ ), as no R. F. B OOTH ET AL . O RIENTED L AGRANGIAN M ATROIDS 13 two vertices take equal values. Now consider the path q to ω′ which consists of p followed by the horizontal edge between ω, ω′ . Both q and p′ are increasing relative to L and terminate at ω′ , and so they have the same number of changes of sign. Thus q and p have the same number of changes of sign also, as they differ only in the final horizontal edge. This completes the proof. Notice that the above argument allows us to formulate an elementary version of Theorem 5. Let M be a Lagrangian matroid of rank n, P its matroid polytope and F a fundamental basis in M. Let α be the vertex of P corresponding to the basis F. Then α can be connected with any vertex ω of P by a path α = v0 , v1 , . . . , vs = ω of vertices of the matroid polytope such that: (1) For 1 ≤ i ≤ s, vi−1 and vi are adjacent in P; and (2) The height is strictly increasing along the path: h(vi−1 ) < h(vi ) for all 1 ≤ i ≤ s. We say that α = v0 , v1 , . . . , vs = ω is height-increasing path. Theorem 9 For a given oriented Lagrangian matroid M , the number of changes of sign in any height-increasing path from the fundamental basis to any basis of maximal height from it is the same. We can take Theorem 9 for a more elementary definition of index of the oriented Lagrangian matroid M with respect to a fundamental basis. 4 Lagrangian Representations of Oriented Lagrangian Matroids Recall that some Lagrangian matroids have symplectic representations consisting of two n × n matrices A and B indexed by I, I ∗ respectively such that ABt is symmetric, where a set of n columns of (A, B) corresponds to a basis if and only if its determinant as a minor is non-zero. Such a representation also defines a Lagrangian oriented matroid, as we shall now show. Suppose M is the Lagrangian matroid represented by (A, B). Let F be a basis of M, the fundamental basis. Put all of the columns indexed by elements of F onto the right-hand side by swapping i with i∗ as required and multiplying the column swapped into the left-hand side by −1. When all the columns of F are on the right, perform row operations to reduce the right hand n columns to the identity (possible as F is a basis). Now we have the form (CF , In ) where CF is symmetric and completely determined by A, B and F. Observe that K ∈ Jn , a set of n column labels, is a basis if and only if the square diagonal minor indexed by the columns of K ′ is non-zero, where G′ denotes G r F for all G ∈ Jn . We define s(F, G) for G ∈ B to be the sign of the minor indexed by G′ . We must now show that this definition satisfies the axioms for s(F, . ) given in the previous section, and that choosing a different fundamental basis gives results in accordance with Definition 1; that is, that Definition 2 holds. We first check agreement with Definition 1, in the form s(G, K) = s(F, K) · s(F, G) · (−1)|Gr(F∪K)| . It is enough to prove that this is true in cases where G = F∆{i, i∗ }, as then the case where there are two exchanges (that is, G = F∆{i, i∗ , j, j∗ } with i 6= j, j∗ ) follows from R. F. B OOTH ET AL . O RIENTED L AGRANGIAN M ATROIDS 14 the continuity of the determinant function, and any path through a Lagrangian matroid can be built up through these two types of exchange. By this we mean that if both intervening sets F∆{i, i∗ }, F∆{ j, j∗ } are non-bases, then we may make small changes in entries of (A, B) in order to make one or both bases, and consider limits as these changes go to zero. / Now, it must We consider two subcases, firstly the one where K ′ ∩ {i, i∗ } = 6 0. be possible to reduce this i-th column of CF to ei , as otherwise G is not a basis. In doing so, we reduce what was K ′ to one identity column and a minor corresponding to the columns of K r G. Now simple linear algebra tells us that the only change of the determinant of this minor undergone is division by the value in the i-th row and column, which has the sign s(F, G). Hence s(G, K) = s(F, G) · s(F, K) which is what we require as G r (F ∪ K) = 0/ in this case. / consider just the minor K ′ ∪ i, where without loss of generality If K ′ ∩ {i, i∗ } = 0, i ∈ G r F, and the corresponding identity minor in the same position on the right hand side. Upon swapping columns i with i∗ and multiplying by column i∗ by −1, the left hand minor is K ′ with −1 times the appropriate identity column and row added, and so has determinant −1 times the determinant of K ′ . The right hand minor is an identity matrix other than column i, and so has determinant equal to the entry from the i-th row of the i-th column which is s(F, G); this is non-zero, as G is a basis and this right-hand side represents G. When the right hand side is reduced to the identity, the left hand side thus becomes the minor of K relative to G, and so will have a determinant of sign s(G, K) = s(F, G) · s(F, K) · (−1) which is what we require as G r (F ∪ K) = {i}. So Definition 1 is respected. Axiom 5 is trivially satisfied, as the sign of the empty minor is positive by definition. For axiom 2, consider a horizontal long edge from K to L. Notice that |F r (K ∪ L)| is of the opposite parity to |F r (K ∪ K)| = |F r K|. Indeed, this holds if and only if |F ∩ (K ∪ L)| is of the opposite parity to |F ∩ K|. Now, F ∩ (K ∪ L) = (F ∩ K) ∪ (F ∩ L) = (F ∩ K) ⊔ (F ∩ (L r K)). Thus, we need to show that F ∩ (L r K) is of odd parity. Also, |(F ∩ L)| = |(F ∩ K)| as the edge is horizontal, and (similarly) F ∩ (K ∪ L) = (F ∩ L) ⊔ (F ∩ (K r L)). So |F ∩ (K r L)| = |F ∩ (L r K)|. Since, for appropriate i, j ∈ J, we have K∆L = {i, i∗ , j, j∗ }, we can write (F ∩ (K r L)) ⊔ (F ∩ (L r K)) = F ∩ (K∆L) = F ∩ {i, i∗ , j, j∗ } which has size 2, since F is maximal admissible. This establishes that the set F r (K ∪ K) has opposite parity to F r (K ∪ L). Now s(F, K) = s(K, F) · (−1)|F r(K∪K)| and s(F, L) = s(K, L) · s(K, F) · (−1)|F r(K∪L)| R. F. B OOTH ET AL . O RIENTED L AGRANGIAN M ATROIDS 15 and so s(F, K) = s(F, L) if and only if s(K, L) = −1. But this holds, as the minor corresponding to s(K, L) where there is a long edge is of the form   a b b 0 which must have negative sign. It must take this form because at least one of the vertices of the n–cube adjacent (in the n-cube) to the fundamental basis and lying within the same 2–dimensional face of the n–cube as this long edge must be a non -basis, otherwise the long edge would not exist; the zero corresponds to this vertex. Axiom 3, concerning a vertical long edge from K to L, is similarly satisfied through the observance that here |F r (K ∪ L)| must be of the same parity as |F r (K ∪ K)|, and the rest of the argument similar. It only remains to prove that axiom 4 holds. Let K be the basis of minimal height in a short-sided square face; then the other bases can be written as L1 = (K r { f1 }) ⊔ { f1∗ }, L2 = (K r { f2 }) ⊔ { f2∗ }, L3 = (K r { f1 , f2 }) ⊔ { f1∗ , f2∗ } for some f1 , f2 ∈ F. We show first that the relative signs of L3 and K and of L1 and L2 are unchanged when K replaces F as fundamental base. Observe first that / K r (F ∪ K) = K r (F ∪ L1 ) = K r (F ∪ L2 ) = K r (F ∪ L3 ) = 0; now, from Definition 1 and the above, we obtain s(K, Li ) = s(F, Li ) · s(F, K) for i = 1, 2, 3, and from this s(K, L1 ) · s(K, L2 ) = s(F, L1 ) · s(F, L2 ) as required. Thus these relative signs are unchanged by change of fundamental base; and to prove that the axiom holds, it suffices to show that if the bases at the same height are of opposite sign, so are the other two. Now consider a minor corresponding to this face with K as the fundamental base where the bases of equal height take different signs; it must take the form   a b b −c where a and c are non-zero and of the same sign. But then the minor of the top basis, which is shown, is clearly negative, but the fundamental basis is always positive. So axiom 4 holds. Thus we have proven Theorem 10 A representation of a Lagrangian matroid M defines also an orientation of M , by the above procedure. We make the obvious definition: an n × 2n matrix (A, B) with ABt symmetric is called a representation of the oriented Lagrangian matroid it yields through the above procedure. Since, in general, there is more than one way to orient a Lagrangian matroid, we see that Schubert cells are partitioned by orientation. It is clear that different orientations of the same Lagrangian matroid lie in different connected components of the thin Schubert cell; thus, Lagrangian orientations provide a natural further refinement of the structure on a real Lagrangian variety on a symplectic space. Recall that in linear algebra, the index of a quadratic form is often defined as the number of negative coefficients when it is expressed as a sum of squares. The signature, more often referred to, is the number of positive terms less the index, so that index can R. F. B OOTH ET AL . O RIENTED L AGRANGIAN M ATROIDS 16 be recovered from rank and signature. It is well known that rank, signature and index are all invariant under change of basis of a quadratic form. We now give the theorem that motivates the naming of the matroid property ‘index’: Theorem 11 The index of a (represented) oriented Lagrangian matroid relative to a fundamental basis F , as defined in section 2, is the same as the index of the quadratic form Q determined by the symmetric matrix CF constructed at the beginning of this section. Also, the rank of Q is the same as the maximal height relative to F attained in the matroid. Proof Notice first that upon obtaining the form (CF , In ) as above, bases of maximal height correspond to non-zero minors of CF of maximal size. This means exactly that rank of Q is this height. We utilise two results from the standard theory of quadratic forms (see, for example, [1, pages 133–138 in chapter 17] for a particularly clear treatment. Note, however, that Ayres defines index as the number of positive terms, rather than negative). If Pi is the determinental minor consisting of the first i columns and rows of a square, symmetric matrix A then we can rearrange by swapping of columns and of the corresponding rows so that not both of Pi and Pi−1 are zero for 1 6 i < r, and Pr is non-singular, where r = rank A. A matrix where this holds is called regularly arranged. Notice that putting A into a regular arrangement, and permuting column labels when permuting columns (of A), does not alter the oriented Lagrangian matroid represented by (A, In ). When a matrix is in regular arrangement, Kronecker’s method tells us that the index is exactly the number of changes of sign in the sequence P0 , P1 , . . . , Pr , discounting any zeroes. We may assume that CF is in a regular arrangement. We choose an increasing path by taking the list of bases corresponding to the non-zero Pi ; this is clearly increasing, and in fact has no horizontal edges. The theorem is immediate. ⋄ 5 Oriented Lagrangian Matroid Polytopes Take a Lagrangian matroid polytope, and assign a direction to each short edge, allowing long edges to remain undirected. Then Definition 6 A Lagrangian matroid polytope with oriented short edges is an oriented Lagrangian matroid polytope exactly when every 2–dimensional face has the same number of short edges directed clockwise as anti-clockwise. Assign a height function relative to some vertex of the n–cube (height is defined relative to non-bases by simply dropping the requirement that F is a basis in the original definition of height). Then an inducing edge relative to this height function is one which is either (long and) vertical, or which is (short and) directed downwards (notice all short edges connect bases of heights differing by 1). Theorem 12 Take an oriented Lagrangian matroid polytope and choose a fundamental basis F and corresponding height function. Assign signs s(F, . ) as follows: s(F, F) is positive. Any two bases connected by inducing edges have opposite signs. Any two bases connected by non-inducing edges have the same signs. Now: 1. This procedure is contradiction-free; and R. F. B OOTH ET AL . O RIENTED L AGRANGIAN M ATROIDS 17 2. The result is an oriented Lagrangian matroid relative to F , and different fundamental bases give equivalent orientations, so that an oriented Lagrangian matroid polytope defines uniquely an oriented Lagrangian matroid. 3. Every oriented Lagrangian matroid is induced from an orientation of its Lagrangian matroid polytope, so that oriented polytopes and oriented Lagrangian matroids are in one to one correspondence. Proof We first consider contradiction-freeness. The result is trivial when the Lagrangian matroid polytope is one-dimensional or smaller. If not, it is enough to show the procedure contradiction–free on 2–dimensional faces, which is a simple check. For part two, as observed when axioms 2–5 were stated, it is enough to check axioms on these faces also, and this too is immediate. It remains only to show that choosing a different fundamental basis gives results respecting Definition 1. The only possible points of concern are around short edges, since long edges give no freedom of sign choice if the result is a oriented Lagrangian matroid, as we have shown it must be. Notice that where A, B ∈ B are the ends of a short edge, that is A∆B = {i, i∗ } for some i, Definition 1 yields s(A, B) = −s(B, A) regardless of what signs we are given relative to F. Fix some F, and take all signs as being calculated from the signs relative to F decided as above through Definition 1. Let us suppose the edge is directed from A to B. We first show s(A, B) = 1 regardless of signs relative to F. Now, s(A, B) = s(F, A)s(F, B)(−1)|Ar(B∪F)| . But if A is lower than B, then |A r (B ∪ F)| = 0 and s(F, A) = s(F, B), as the edge is non-inducing, so s(A, B) is positive as required. If A is higher then B, |A r (B ∪ F)| = 1 and s(F, A) = −s(F, B), so s(A, B) remains positive. Now consider some basis G as fundamental. To complete the proof of this point, we must show that s(G, B)s(G, A) = 1 if and only if A is lower than B relative to G. But 1 = s(A, B) = s(G, A)s(G, B)(−1)|Ar(B∪G)| from the above and Definition 1. But notice, as before, that |A r (B ∪ G)| is 0 when A lies below B relative to G and 1 otherwise, which completes our proof. Finally, for part three, observe once more that only short edges need give us concern. From Definition 1 we obtain s(A, B) = −s(B, A) whenever A, B are the ends of a short edge, and so we direct the edge according to which of the two is positive. This then obviously gives the correct oriented polytope. ⋄ Corollary 13 The index of an oriented Lagrangian matroid relative to some basis F may be found by considering its oriented polytope and counting inducing edges in any path from F to a basis of maximal height in which no edge is followed downwards relative to F . Notice that in an even Lagrangian matroid inducing edges are vertical long edges. Hence the index of an even Lagrangian matroid is with respect to the fundamental basis F is exactly half of the maximal height of bases with respect to F. For an even Lagrangian matroids represented by a symmetric matrix A over R, this means that the R. F. B OOTH ET AL . O RIENTED L AGRANGIAN M ATROIDS 18 Figure 3: ✘r ✘✘ ✚ ✘ ✘ ✚ ✘ ✘ ❂ ✘ ✚ ✘ ✘✘ ✚ ✘ ✚ r ✘✘ ✲ r 123 ❅ ❅ ❅ ❅ ❅ ✻ ❅ ❅ ❅ ❅ ❅r ✘r ✘✘ ✚ ✘ ✘ ✚ ✘✘ ✚ ✘✘✘ ❃ ✘ ✚ ✘ ✘ ✛ ✚ r✘ r 123 ❅ ❅ ❅ ❅ ❄ ❅ ❅ ❅ ❅ ❅r index of the corresponding quadratic form Q is half its rank. Therefore Q has signature 0, hence allows a hyperbolic basis, that is, can be transformed to the form x1 x2 + x3 x4 + · · · + x2k−1x2k . We present the examples shown in figure 3. Both polytopes correspond to the same unoriented Lagrangian matroid, with bases 1∗ 23, 12∗3, 123∗, 123. If we consider signs relative to 123, all other signs are negative in the left-hand example and all signs are positive in the right-hand example. Both these oriented Lagrangian matroids are representable, by 1 1 0 0 2 0 1 0 3 0 0 1 1∗ 1 1 1 1 1 0 0 2 0 1 0 3 0 0 1 1∗ 2∗ 3∗ 1∗   −1 −1 −1 1 −1 −1 −1  ∼  1 −1 −1 −1 1 and  2∗ 1 1 1 1∗ 2∗ 3∗ 3∗   −1 −1 −1 1 1  ∼  −1 −1 −1 −1 −1 −1 1  2∗ 1 1 1 3∗ 1 1 1 1 1 0 0 2 0 1 0 3  0 0 1 1 1 0 0 2 0 1 0 3  0 0 1 respectively, where ∼ means that these are the same representations after permutations of columns and column labels as defined in section 3. All the indices of both examples are 1 except for the index of the right-hand example relative to 123, which is 0. Finally, it is easy to see (from the definition of oriented polytope and the theorem above) that these are the only possible orientations of this polytope, and hence of this Lagrangian matroid. Finally, we consider isomorphisms of oriented Lagrangian matroids. We say that two symplectic matroids on J = I ∪ I ∗ with basis collections B , B ′ are isomorphic when there exists some admissible permutation σ such that B ′ = σB = {σA|A ∈ B }. R. F. B OOTH ET AL . O RIENTED L AGRANGIAN M ATROIDS 19 We say that two oriented Lagrangian matroids, using the above notation with orientations s, s′ are isomorphic when, in addition, s′ (σA, σB) = s(A, B) for all A, B ∈ Jn . Observe that two oriented Lagrangian matroids are isomorphic exactly when their oriented polytopes are the same up to some admissible permutation of vertices of the n-cube, where an edge directed from A to B becomes an edge directed from σA to σB. Recall that the group of all admissible permutations is exactly the symmetry group of the n-cube. Thus isomorphism is a very natural geometric concept. We now see that the two Lagrangian matroid polytopes of figure 3 are (trivially) isomorphic as unoriented polytopes, but non-isomorphic as oriented polytopes. Acknowledgement. The authors wish to thank the referee for comments which helped to improve the exposition in this paper. References [1] F. Ayres, Jr, Theory and Problems of Matrices, McGraw–Hill International Book Company, 1962. [2] A. Björner, M. Las Vergnas, B. Strumfels, N. White, G. M. Ziegler, Oriented Matroids, Cambridge University Press, Cambridge, 1993. [3] R. F. Booth, Oriented Lagrangian orthogonal matroid representations, submitted to the European Journal of Combinatorics. [4] A. V. Borovik, I. M. Gelfand, W P-matroids and thin Schubert cells on Tits systems, Adv. Math. 103 (1994) 162–179. [5] A. V. Borovik, I. M. Gelfand and N. White, On exchange properties of Coxeter matroids and oriented matroids, Discrete Mathematics, 179 (1998), 59–72. [6] A. V. Borovik, I. M. Gelfand and N. White, Coxeter matroid polytopes, Annals of Combinatorics, 1 (1997) 123–134. [7] A. V. Borovik, I. M. Gelfand, N. White, Symplectic Matroids, J. Algebraic Combinatorics 8 (1998), 235–252. [8] A. V. Borovik, I. M. Gelfand and N. White, Coxeter Matroids, Birkhäuser, Boston, in preparation. [9] A. V. Borovik and A. Vince, An adjacency criterion for Coxeter matroids, J. Algebraic Combinatorics 9 (1999), 271–280. [10] A. Bouchet, Representability of ∆- matroids, in Combinatorics (Eger, 1987), NorthHolland, Amsterdam, 1988, pp. 167–182. [11] A. Brøndsted, An Introduction to Convex Polytopes, Graduate Texts in Mathematics 90, Springer-Verlag, 1983. [12] B. Carman, Matroids and their Polytopes, UMIST MSc Thesis, 1995. [13] I. M. Gelfand and V. V. Serganova, Combinatorial geometries and torus strata on homogeneous compact manifolds, Russian Math. Surveys 42 (1987) 133–168; see also I. M. Gelfand, Collected Papers, vol. III, Springer-Verlag, New York a.o., 1989, pp. 926– 958. [14] R. MacPherson, Combinatorial Differential Manifolds, in Topological Methods in Modern Mathematics. Proceedings of a symposium in honor of John Milnor’s sixtieth birthday, held at the State University of New York at Stony Brook, USA, June 14– June 21 1991, L. R. Goldberg et al., eds., Houston, Publish or Perish, Inc., 1993, pp. 203–221. [15] A. Vince, N. White, Orthogonal Matroids, J. Algebraic Combinatorics, to appear. R. F. B OOTH ET AL . O RIENTED L AGRANGIAN M ATROIDS 20 [16] W. Wenzel, Geometric algebra of ∆-Matroids and related combinatorial geometries, habilitationsschrift, Bielefeld, 1991. [17] W. Wenzel, Pfaffian forms and ∆-matroids, Discrete Math. 115 (1993) 253–266. [18] N. White, ed., Theory of Matroids, Cambridge University Press, Cambridge, 1986. Authors’ addresses Richard F. Booth, Alexandre V. Borovik, Department of Mathematics, UMIST, PO Box 88, Manchester M60 1QD, United Kingdom; alexandre.borovik@umist.ac.uk Israel M. Gelfand, Department of Mathematics, Rutgers University, New Brunswick NJ 08903, USA; igelfand@math.rutgers.edu Neil White, Department of Mathematics, P.O. Box 118105, University of Florida, Gainesville FL 32611-8105, USA; white@math.ufl.edu