Orthogonal Matroids.
The notion of matroid has been generalized to Coxeter matroid by Gelfand and Serganova. To each pair i>(W, P) consisting of a finite irreducible Coxeter group i>W and parabolic subgroup i>P is associated a collection of objects called Coxeter matroids. The (ordinary) matroids are the special case where i>W is the symmetric group (the i>An case) and i>P is a maximal parabolic subgroup.This generalization of matroid introduces interesting combinatorial structures corresponding to each of the finite Coxeter groups. Borovik, Gelfand and White began an investigation of the i>Bn case, called symplectic matroids. This paper initiates the study of the i>Dn case, called orthogonal matroids. The main result (Theorem 2) gives three characterizations of orthogonal matroid: algebraic, geometric, and combinatorial. This result relies on a combinatorial description of the Bruhat order on i>Dn (Theorem 1). The representation of orthogonal matroids by way of totally isotropic subspaces of a classical orthogonal space (Theorem 5) justifies the terminology i>orthogonal matroid.
Introduction
.
Matroids, introduced by Hassler Whitney in 1935, are now a fundamental tool
in combinatorics with a wide range of applications ranging from the geometry of
Grassmannians to combinatorial optimization. In 1987 Gelfand and Serganova [9]
[10] generalized the matroid concept to the notion of Coxeter matroid. To each nite
Coxeter group W and parabolic subgroup P is associated a family of objects called
Coxeter matroids. Ordinary matoids correspond to the case where W is the symmetric
group (the An case) and P is a maximal parabolic subgroup.
This generalization of matroid introduces interesting combinatorial structures corresponding
to each of the nite Coxeter groups. Borovik, Gelfand and White [2] began
an investigation of the Bn case, called symplectic matroids. The term \symplectic"
comes >from examples constructed from symplectic geometries. This paper initiates
the study of the Dn case, called orthogonal matroid because of examples constructed
from orthogonal geometries.
The rst goal of this paper is to give three characterizations of orthogonal matroids:
algebraic, geometric and combinatorial. This is done in Sections 3, 4 and 6 (Theorem
after preliminary results in Section 2 concerning the family Dn of Coxeter groups.
The algebraic description is in terms of left cosets of a parabolic subgroup P in
The work of Neil White on this paper was partially supported at UMIST under funding of EPSRC
Visiting Fellowship GR/M24707.
Dn . The Bruhat order on Dn plays a central role in the denition. The geometric
description is in terms of a polytope obtained as the convex hull of a subset of the
orbit of a point in R n under the action of Dn as a Euclidean re
ection group. The
roots of Dn play a central role in the denition. The combinatorial description is
in terms of k-element subsets of a certain set and
ags of such subsets. The Gale
order plays a central role in the denition. Section 5 gives a precise description of the
Bruhat order on both Bn and Dn in terms of the Gale order on the corresponding
ags (Theorem 1). A fourth characterization, in terms of ori
ammes, holds for an
important special case (Theorem 3 of Section 6).
Section 7 concerns the relationship between symplectic and orthogonal matroids.
Every orthogonal matroid is a symplectic matroid. Necessary and su-cient conditions
are provided when a Lagrangian symplectic matroid is orthogonal (Theorem 4). More
generally, the question remains open.
Section 8 concerns the representation of orthogonal matroids and, in particular,
justies the term orthogonal. Just as ordinary matroids arise from subspaces of
projective spaces, symplectic and orthogonal matroids arise from totally isotropic
subspaces of symplectic and orthogonal spaces, respectively (Theorem 5).
2. The Coxeter group Dn
We give three descriptions of the family Dn of Coxeter groups: (1) in terms of
generators and relations; (2) as a permutation group; and (3) as a re
ection group in
Euclidean space.
Presentation in terms of generators and relation. A Coxeter group W is
dened in terms of a nite set S of generators with the presentation
ss 0 is the order of ss 0 , and m ss (hence each generator is an involution).
The cardinality of S is called the rank of W . The diagram of W is the graph where
each generator is represented by a node, and nodes s and s 0 are joined by an edge
labeled m ss 0 whenever m ss 0  3. By convention, the label is omitted if m ss
Coxeter system is irreducible if its diagram is a connected graph. A reducible Coxeter
group is the direct product of the Coxeter groups corresponding to the connected
components of its diagram. The nite irreducible Coxeter groups have been completely
classied and are usually denoted by An (n  1); Bn(= Cn ) (n  2); Dn (n
the subscript denoting the
rank. The diagrams of of the families An ; B=Cn and Dn appear in Figure 1, these
being the families of concern in this paper.
Permutation representation. Throughout the paper we will use the notation
ng and [n] g. As a permutation group, An is isomorphic
to the symmetric group on the set [n + 1] with the standard generators being
the adjacent transpositions
n-12n
Fig. 1. Diagrams of three Coxeter families.
Likewise Bn is isomorphic to the permutation group acting on [n] [ [n]  generated by
the involutions
We will use the convention i Call a subset X  [n] [ [n]
admissible if X \ X does not contain both i and i  for any i. The
group Bn acts simply transitively on ordered, admissible n-tuples; hence
The group Dn is isomorphic to the permutation group acting on [n] [ [n]  and
generated by the involutions
Note that Dn is a subgroup of Bn . More precisely, Dn consists of all the even permutations
in Bn ; hence
Re
ection group. A re
ection in a Coxeter group W is a conjugate of some
involution in S. Let denote the set of all re
ections in W . Every nite
Coxeter group W can be realized as a re
ection group in some Euclidean space E of
dimension equal to the rank of W . In this realization, each element of T corresponds
to the orthogonal re
ection through a hyperplane in E containing the origin.
It is not di-cult to give an explicit representation of Bn and Dn as re
ection
groups. If i 2 [n], let e i denote the i th standard coordinate vector. Moreover, let
its subgroup Dn , as a permutation group as given above.
Then for w 2 Bn , the representation of w as an orthogonal transformation is given
by letting
for each i 2 [n] and expanding linearly.
As a re
ection group, each nite Coxeter group W acts on its Coxeter complex.
Let  denote the set of all re
ecting hyperplanes of W , and let
The connected components of E 0 are called chambers. For any chamber , its closure
is a simplicial cone in E . These simplicial cones and all their faces form a simplicial
fan called the Coxeter complex and denoted  := (W ). It is known that W acts
simply transitively on the set of chambers of (W ).
A
ag of an n-dimensional polytope is a nested sequence F 0  F 1      Fn 1
of faces. A polytope is regular if its symmetry group is
ag transitive. Each of the
irreducible Coxeter groups listed above, except Dn is the symmetry
group of a regular convex polytope. In particular An is the symmetry group of the
(n 1)-simplex, the permutation representation above being the action on the set of
vertices, each vertex labeled with an element of [n]. The group Bn is the symmetry
group of the n-cube or its dual, the cross polytope (generalized octahedron). For this
reason, the group Bn is referred to as the hyperoctahedral group. The permutation
representation is the action on the set of 2n vertices of the cross polytope, each vertex
labeled with an element of [n] [ [n]  , the vertex i  being the vertex antipodal to the
vertex i. Dually, the action is on the set of 2n facets of the n-cube, the facet i  being
the one opposite the facet i. In the cases where Coxeter group W is the symmetry
group of a regular polytope, the intersection of the Coxeter complex (W ) with a
sphere centered at the origin is essentially the barycentric subdivision of the polytope.
The Coxeter group of type Dn also acts on the n-cube Qn , although not quite
ag
acts transitively on the set of k-dimensional faces of Qn for all k
However, there are two orbits in its action on the set of vertices of Qn ,
and hence two orbits in its action on the set of
ags of Qn .
3. Dn matroids
Three denitions of Dn matroid (orthogonal matroid) are now given: (1) algebraic,
(2) geometric, and (3) combinatorial. That these three denitions are equivalent is the
subject of Sections 4, 5 and 6. Three such denitions are also given of An (ordinary)
matroids and Bn (symplectic) matroids.
Algebraic description. We begin with a denition of the Bruhat order on a
Coxeter group W ; for equivalent denitions see e.g., [7][12]. We will use the notation
for the Bruhat order. For w 2 W a factorization into the product of
generators in S is called reduced if it is shortest possible. Let l(w) denote the length
k of a reduced factorization of w.
Denition 1. Dene u  v if there exists a sequence
that re
ection
Every subset J  S gives rise to a (standard) parabolic subgroup P J generated by
J . The Bruhat order can be extended to an ordering on the left coset space W=P for
any parabolic subgroup P of W .
Denition 2. Dene Bruhat order on W=P by u  v if there exists a u 2 u and
such that u  v.
Associated with each w 2 W is a shifted version of the Bruhat order on W=P ,
which will be called the w-Bruhat order and denoted w .
Denition 3. Dene u w v in the w-Bruhat order on W=P if w 1 u  w 1 v.
Denition 4. The set L  W=P is a Coxeter matroid (for W and P ) if, for each
there is a
The condition in Denition 4 is referred to as the Bruhat maximality condition. A
Coxeter diagram with a subset of the nodes circled will be referred to as a marked
diagram. The marked diagram G of W=P is the diagram of W with exactly those
nodes circled that do not correspond to generators of P . Likewise, if L is a Coxeter
matroid for W and P , then G is referred to as the marked diagram of L.
Geometric description. Consider the representation of a Coxeter group W as a
re
ection group in Euclidean space E as discussed in Section 2. A root of W is a vector
orthogonal to some hyperplane of re
ection (a hyperplane in the Coxeter complex).
For Dn , with respect to the same coordinate system used in equation (2.1), the roots
are precisely the vectors
while the roots of Bn are
For our purposes the norm of the root vector is not relevant.
In the Coxeter complex of W choose a fundamental chamber that is bounded by
the hyperplanes of re
ection corresponding to the generators in S. With the Coxeter
complex of Dn as described in Section 2, a fundamental chamber is the convex cone
spanned by the vectors
Let x be any nonzero point in the closure of this fundamental chamber. Denote the
orbit of x by
O
If L  O x , then the convex hull of L, denoted (L), is a polytope. The following
formulation was originally stated by Gelfand and Serganova [10]; also see [12].
Denition 5. The set L  O x is a Coxeter matroid if every edge in (L) is
parallel to a root of W .
The marked diagram G of a point x is the diagram of W with exactly those nodes
circled that correspond to hyperplanes of re
ection not containing point x. Note that
x and y have the same diagram if and only if they have the same stabilizer in W . If
L  O x is a Coxeter matroid, then G is referred to as the marked diagram of L. The
polytope (L) is independent of the choice of x in the following sense. The proof
appears in [5].
Lemma 1. If x and y have the same diagram and L x  O x and L y  O y are
corresponding subsets of the orbits (i.e., determined by the same subset of W ), then
are combinatorially equivalent and corresponding edges of the two
polytopes are parallel.
Because of Lemma 1, there is no loss of generality in taking, for each diagram, one
particular representative point x in the fundamental chamber and the corresponding
orbit O x . In particular, we can take x in the set Z 0 of points
where each of the following quantities equals either 0 or 1: x
and xn 1 jx n j, and jx n j. The set Z 0 consists essentially of all possible barycenters of
subsets of the vectors in (3.1) that span the fundamental chamber. (Except, however,
the single vector e 1 used instead of the last two vectors in (3.1) when
both of those vectors are present. Thus, if example, we get (2;
instead of (3; 2; 0).)
Combinatorial description. Our combinatorial description of symplectic and
orthogonal matroids is analogous to the denition of an ordinary matroid in terms
of its collection of bases. Whereas the algebraic and geometric descriptions hold for
any nite irreducible Coxeter group, the denitions in this section are specic to the
An ; Bn and Dn cases. For a generalization see [13].
An essential notion in these denitions is Gale ordering. Given a partial ordering
on a nite set X, the corresponding Gale ordering on the collection of k-element
subsets of X is dened as follows: A  B if, for some ordering of the elements of A
and B,
we have a i  b i for all i. Equivalently, we need a bijection A so that (b)  b
for all b 2 B. In later proofs when constructing such a bijection, we will refer to b as
dominating (b). The following lemma is straightforward.
Lemma 2. Let
and assume the elements have been ordered so that a i  a i+1 and b i  b i+1 for all
in the Gale order if and only if a i  b i for all i.
Dene a
ag F of type nested
sequence of subsets of X
such that jA
ag of type k is just a single k-element set. Extend the Gale
ordering on sets to the Gale ordering on
ags as follows. If
are two
ags, then FA  FB if A i  B i for all i.
An matroids. Consider
ags for each
i. Let
denote the set of all
ags of type
Denition 6. A collection L  A (k1 ;k 2 ;:::;k m ) is an An matroid if, for any linear
ordering of [n], L has a unique maximal member in the corresponding Gale order.
If the
ag consists of more than one subset, the An matroid is often referred to as
an ordinary
ag matroid. In the case of single sets (
ags of type k), it is a standard
result in matroid theory [14] that an An matroid is simply an ordinary matroid of
rank k.
Bn matroids. Now consider
ags
for each i. Call such a
ag admissible if Am \ A
does not contain
both i and i  for any i. Let
denote the set of all admissible
ags of type
< km  n.
Dene a partial order on [n] [ [n]  by
A partial order on [n] [ [n]  is called Bn -admissible if it is a shifted ordering w for
some w 2 Bn . By a shifted ordering we mean:
a w b if and only if w 1 (a)  w 1 (b):
Note that an ordering  on [n][[n]  is admissible if and only if (1)  is a linear ordering
and (2) from i  j it follows that j   i  for any distinct elements
For example, is an admissible ordering.
Denition 7. A collection L  A (k1 ;k 2 ;:::;k m ) is a Bn matroid (symplectic
ag
matroid) if, for any admissible ordering of [n] [ [n]  , L has a unique maximal member
in the corresponding Gale ordering.
The marked diagram G of A (k1 ;k 2 ;:::;k m ) is the diagram for Bn with the nodes
referred to as the marked diagram of L.
Dn matroids. Again consider
ags
for each i. Let A (k1 ;k 2 ;:::;k m ) denote the same set of admissible
ags of type
as in the Bn case, except when
then let
denote the set of admissible
ags of type containing an
even number of starred elements, and let
denote the set of admissible
ags of type containing an
odd number of starred elements. Note that we do not permit both km
In the case should be understood, without explicitly stating it,
that A means either A + or A .
Dene a partial order on [n] [ [n]  by
Note that the elements n and n  are incomparable in this ordering. A partial order
on [n] [ [n]  is Dn -admissible if it is a shifted order w for some w
a w b if and only if w 1 (a)  w 1 (b):
Note that an ordering  is Dn -admissible if and only if it is of the form
an
a 1  a an 1   a
2  a
a
an g is admissible and we again use the convention i
Denition 8. A collection L  A (k1 ;k 2 ;:::;k m ) is a Dn matroid (orthogonal matroid)
if, for each admissible ordering, L has a unique maximal member in the corresponding
Gale order.
The elements of L will be called bases of the matroid. If m > 1, then the matroid
is sometimes referred to as an orthogonal
ag matroid. The marked diagram G of
A (k1 ;k 2 ;:::;k m ) is obtained from the diagram of Dn by considering three cases:
Case 1. If km  n 2, then circle the nodes k
Case 2. If km 1  n 2 (or
and the node n 1 or n depending on whether the collection of
ags is A (k1 ;k
or A +
Case 3. If km 1  n 2 (or
and both nodes n 1 and n.
Note that all possibilities for marked diagrams are realized. If L  A (k1 ;k 2 ;:::;k m ) is a
Dn matroid, then G is referred to as its marked diagram.
4. Bijections
The denitions of Dn matroid in the previous section are cryptomorphic in the sense
of matroid theory; that is, they dene the same object in terms of its various aspects.
Likewise for Bn matroids. For ordinary matroids there are additional denitions in
terms of independent sets,
ats, cycles, the closure operator, etc. In this section we
make the crytomorphisms explicit for orthogonal matroids.
The denitions given for Dn matroid in the previous section are
(1) in terms of the set W=P of cosets (Denition 4),
(2) in terms of the set O x of points in Euclidean space (Denition 5), and
(3) in terms of a collection A (k1 ;k 2 ;:::;k m ) of admissible
ags (Denition 8).
Explicit bijections are now established between W=P; O x and A (k1 ;k 2 ;:::;k m ) , each with
the same marked diagram:
To dene f , start with the collection Dn=P of cosets with marked diagram G. Fix
a point x 2 R n r f0g in the fundamental chamber with marked diagram G. In fact,
we can take x to be a point in the set Z 0 dened in Section 3. In other words, the
stabilizer of x in W is exactly P . For w 2 Dn , the point w(x) depends only on the
coset wP . This gives a bijection
To describe the inverse of f , let y 2 O x and let w 2 Dn be such that y. If P
is the parabolic subgroup of Dn generated by exactly those re
ections that stabilize
To dene g, again consider the collection Dn=P of cosets with marked diagram G.
Let A (k1 ;:::;k m ) be the collection of admissible sets with the same marked diagram G
(as described by the three cases in Section 3). If
ag
and A then the
ag will often be denoted
For example the
ag will be denoted simply
be the
ag
in the case
depending, respectively, on whether the node n 1 or n is circled. Let F be an
arbitrary
ag given in the form (4.1). The action of Dn as a permutation group on
as described in Section 2 extends to an action on A (k1 ;k
. For this action of Dn on A (k1 ;:::;k m ) the stabilizer of F 0 is P . So, for
the
ag w(F ) depends only on the coset wP . Thus a bijection is induced:
The map g is surjective because, if km < n, then there is one orbit, A (k1 ;:::;k m ) , in
the action of Dn on the set of admissible
ags of type
there are two orbits, A
the one consisting of those admissible
ags such that Am contains an even number of starred elements, and the other those
admissible
ags such that Am contains an odd number of starred elements.
To describe the inverse of g, let F be an arbitrary
ag in A (k1 ;:::;k m ) and let w 2 Dn
be such that w(F 0 If P is the parabolic subgroup of Dn that stabilizes F 0 , then
The third bijection is However, it is useful to provide the direct
construction, as follows. Let F be a
ag of type
Recall that e i dene the
km
where  i is the number of sets in the
ag that contain a i . In
particular let
where we allow when we are in case
respectively. Now we have our map
There is an alternative way to describe the map h, in terms of the barycentric
subdivision (Q) of the n-cube Q centered at the origin with edges parallel to the
axes. Let the faces of Q be labeled by [n] [ [n]  , where i and i  are antipodal
faces. If F 2 A k , then h(F ) is a vertex of (Q) (appropriately scaled). For a
ag
the image h(F ) is the barycenter of the
simplex of (Q) determined by the vertices
To describe the inverse of h, note that each vertex v in (Q) represents a face f v
of Q. If A  [n] [ [n]  is the set of k facets of Q whose intersection is f v , then label
v by A. Point x is the barycenter of a simplex of (Q) whose vertices are labeled,
say [k (again, in the case replace
ng by f1; each point y 2 O x is the
barycenter of some simplex of (Q) whose vertices are labeled A 1 ; A
for each i. Then
Proposition. With the maps as dened above: h -
Proof. Let w 2 Dn=P and use formula (2.1):
km
km
5. The Bruhat Order on Dn .
Let Dn=P and A (k1 ;:::;k m ) have the same marked diagram. In this section a combinatorial
description of the Bruhat order on Dn=P is given in terms of A (k1 ;:::;k m ) .
This is also done in the Bn case.
Consider two
ags of the same type:
Alternatively,
Assume, without loss of generality, that in A and B the elements between consecutive
vertical bars are arranged in descending order with respect to (3.2). This is possible
because, by denition, elements n and n  do not appear together in an admissible
set.
Now we dene a partial order on A (k1 ;:::;k m ) called the weak Dn Gale order. Consider
two distinct
ags A and B (denoted as above) where, for each i, either (1) b
or (2) b
i . In case (2) also assume that
(a) a i is unstarred and a i 6= n;
(b) a j (and thus also b j ) is less than a i in numerical value for all j > i; and
(c) all elements greater than a i in numerical value appear to the left of a i in A.
A in the Gale order for Dn . Call two
ags with the above properties close.
For example, if are close, but
and are not close and are not close. For any pair of
ags that are close, it is easy to check that one covers the other in the Gale order.
Consider the Hasse diagram of the Dn Gale order on the set A (k1 ;:::;k m ) of
ags.
Remove >from the diagram all covering relations that are close. Call the resulting
partial order on A (k1 ;:::;k m ) the weak Dn Gale order.
The following notation is used in the next lemma, which provides a formula for
the length l(u) of any element u 2 Dn . Let Fu 2 A (1;:::;n 1) . Since all nodes in the
corresponding diagram are circled, the parabolic subgroup in this case is trivial, so we
are justied in using the notation Fu , where u 2 Dn . Let F 0
u be the
ag in A (1;:::;n)
obtained from Fu by adjoining the missing element at the end so that the number of
starred elements is even. For a
ag A in A (1;:::;n) dene a descent as a pair (a i ; a j )
of elements such that j > i and a i  a j . Let d(A) denote the number of descents in
ag A. Note that, as a permutation of [n] [ [n]  , a re
ection t 2 Dn is an involution
of the form
A generating re
ection is of the form (i
n).
Lemma 3. Let Fu be the
ag corresponding to an element u 2 Dn . Then
(n
Proof. The proof is by induction. For a
ag in denote the
parameter
s  2[n]  \F 0 (n s) by p(F ). Note that applying any generating
re
ection s to F changes p(F ) by at most 1. Since necessarily l(u)
But we can always arrange it so that p(sF
Theorem 1.
(1) The correspondence poset isomorphism between Dn=P
with respect to the Bruhat order and A (k1 ;:::;k m ) with respect to the weak Dn Gale
order. In other words, for Dn , Bruhat order is weaker than Gale order.
(2) On the other hand, for Bn , Bruhat order on Bn=P is isomorphic to Gale order on
A
Proof. In this proof the relation  refers to the Dn weak Gale order. Let FA and FB
be two
ags in A (k1 ;:::;k m ) and v and u the corresponding cosets in Dn=P . It must
be shown that FB  FA if and only if u  v. According to denitions (1) and (2) in
Section 3, in Dn=P we have u  v in the Bruhat order if and only if there exists a
sequence re
ection
and is a re
ection, and let
ags
F v and Fu be the corresponding
ags. Note that, according to Lemma 3, u  v if
and only if Fu > F v .
Below it will be shown that, in A (k1 ;:::;k m ) , we have FB  FA in the weak Dn
order if and only if there exists a sequence of
ags
that F of the form (5.1), and F i > F i 1 for
m. This will prove the theorem. Thus it is now su-cient to show that, for
any two
ags FB > FA , there is an involution t of the form (5.1) such that either
To simplify notation assume that B > A are two
ags. Let j be the rst index
such that a j 6= b j , and such that, furthermore, if b
then assume that either
(i) there is an a that is greater than a j in numerical value or
(ii) there is an element c greater than a j in numerical value such that neither c
nor c  lies to the left of a j in A.
Since A and B are not close, such a j must exist. To simplify notation let a =
. If a  b, then it is not possible that B > A. Also
not possible; otherwise there would be an earlier pair a
would
qualify as the rst pair such a j 6= b j . Thus b  a. Let [a; bg. One of
the following cases must hold:
(1) There is a c 2 [a; b] such that either c lies to the right of a in A or neither c
nor c  appears in A.
(2) There is a c 2 [a; b] such that c lies to the right of b in B or neither c nor c
appears in B.
(3) There is a c  2 [a; b]  such that c  lies to the right of a in A.
In fact, if neither (1) nor (2) holds, then clearly b can play the role of c in (3) unless
a  and neither (1) nor (2) holds, then the non-closeness of A and
B is violated.
Case 1. Assume that such a c exists. If such c exists to the right of a in A, let
a k be the rst such element as we move to the right of a in A. (If neither c nor
c  appear in A for all such c, let 1.) The elements a i 2 A between a and a k do
not lie in [a; b].
There are now two subcases. Assume that a C be obtained
from A by applying the involution (ac)(a  c  ). Clearly C > A, since c must occur in
a separate block of A from a, since c > a and we assumed elements in a block were
ordered in decreasing order. It remains to show that B  C. We must show that
and we may assume that all elements
of the left of b in B i are used to dominate the elements to the left of a in A. The
element b in B i must be used to dominate an element of A that is less than or equal
to a. But then, without loss of generality, we may assume that b is used to dominate
a. Using the same correspondence we have B i  C i .
Now assume the other subcase, that b
Arguing as above, for
may be the case that b is used to dominate a i . By the choice of j satisfying
properties (i) and (ii) above, b is less than a i in numerical value, and hence it must
be the case that b  b
. But then, without loss of generality, we can take b i to
dominate a i and b to dominate a. Then proceed as in the paragraph above.
Case 2 is proved in an analogous fashion to Case 1, nding a C such that B > C
A:
Case 3. Assume that neither case (1) nor case (2) holds. We have already seen
that b 6= a  . The situation is now divided into two possibilities. Either
(1) a and b are both unstarred or a is unstarred and
(2) a and b are both starred or b is starred and a = n.
The two cases are exhaustive. To see this let a 6= n be unstarred and b 6= n  starred.
Either a is greater than b in numerical value or b is greater than a in numerical value.
Assume the former; the argument is the same in either case. Then a 2 [a; b] and
a  2 [a; b]. One of the following must be true: neither a nor a  appear in B (which
is case 2) or one of a or a  appears to the right of b in B (also case 2). (Note that
n is not possible.)
We consider the case where both a and b are unstarred or a is unstarred and
the argument in the second case is analogous. We assume that there is a c  2 [a; b]
such that c  lies to the right of a in A. Let c  = a k be the last such starred element
as we move to the right of a in A. In other words, all other elements in [a; b]  that lie
to the right of a in A lie to the left of c  . Let C be obtained from A by applying the
involution (ac)(a  c  ). Clearly C > A; it remains to show that B  C. In particular,
we must show that B i  C i for all i such that k i > j. We have and we can
assume, by the same reasoning as in case (1), that all elements of the left of b in B
are used to dominate the elements to the left of a in A. Since no elements in [a; b]
appear to the right of a in A, there is no loss of generality in assuming that b is used
to dominate a. Then, unless k i  k, the same correspondence between the elements
of A i and B i shows that B i  C i .
If k i  k, then consider the set X of starred elements of A i (and n if
lie to the right of a and the set Y of starred elements of B i that lie to the right of b.
It is not necessary to consider elements to the left of a or b because, even if for some
such pair we have b
i , the element b i cannot be used to dominate any element of
X in the Gale order B i > A i since all elements in X are less than b i in numerical value
(and hence greater in order). So in the Gale order B i > A i the elements of X must be
dominated by elements of Y . Indeed, X \ ([a; g. There
may be elements of ([a; not in B i , by virtue of appearing to the right of
position k i . But in that case, even larger elements of Y must be used to dominate
g. By letting each element be used to dominate itself, where possible,
we see that there is no loss of generality in assuming that x  a  dominates
now almost the same correspondence shows that B i  C i . Merely make
the changes that x dominates a  2 C i and c  2 B i (or some larger
dominates b  2 C i , whereas b now dominates c. This completes the proof of statement
(1) of Theorem 1.
A similar though considerably simpler proof of statement (2) in Theorem 1 can be
given. In fact, a general proof for all Coxeter groups with a linear diagram was given
in [13]. This would include the Bn case, but not the Dn case.
6. Cryptomorphisms.
We have seen that for Dn , the bijection not a poset
isomorphism between Bruhat order and Gale order, but rather that Bruhat order is
weaker than Gale order. It is therefore somewhat surprising that the Bruhat maximality
condition is still equivalent to the Gale maximality condition. We now prove
the equivalence of our three denitions of Dn matroid, the algebraic, geometric, and
combinatorial descriptions.
Theorem 2. Let L  Dn=P be a collection of cosets, let be the
corresponding polytope, and let be the corresponding collection
of
ags. Then the following are equivalent.
(1) L satises the Bruhat maximality condition,
(2) (L) satises the root condition,
(3) F satises the Gale maximality condition.
Proof. This theorem follows from Theorem 3 in [13]. However, that paper considers a
much more general setting, and the proof, including that of the prerequisite Theorem
1 of [13], is quite long and involved. The situation simplies considerably in the
current setting. The equivalence of statements (1) and (2) is a special case of the
Gelfand-Serganova Theorem and is proved for any nite irreducible Coxeter group in
[12, Theorem 5.2]. Now we show the equivalence of (1) and (3).
Assume that L  Dn=P satises the maximality condition with respect to Bruhat
order. This means that, for any w 2 Dn , there is a maximum u 0 2 L such that
statement (1) of Theorem 1 this implies that
in the weak Dn Gale order for all
is the
ag dened in Section 4. So F satises the Gale maximality
condition.
Conversely, suppose that F satises the Gale maximality condition with respect
to admissible Dn -orderings. Since every admissible Bn -ordering is a renement of an
admissible Dn -ordering, it is clear that F satises the Gale maximality condition with
respect to admissible Bn -orderings. By statement (2) of Theorem 1, the corresponding
collection of cosets of Bn=P satises the Bruhat maximality condition, and hence
the corresponding polytope (L) satises the root condition for Bn by the above-mentioned
equivalence of (1) and (2) for nite irreducible Coxeter groups. Note that
if we consider the same set of
ags F as both a Dn matroid and a Bn matroid, (L)
is the same polytope in both cases. If (L) also satises the root condition for Dn , we
are done. Therefore we assume, by way of contradiction, that (L) does not satisfy
the root condition for Dn , and hence that there is an edge of (L) which is parallel
to e i for some i. Let this edge be - A - B for some pair of
ags
and is the bijection from Section 4. Then A and B dier only
in element i, and hence for some k, a
be a
linear functional which takes its maximum value on the polytope (L) only on the
two vertices - A - B and, of course, the edge between them. Clearly
loss of generality, we may assume that f is chosen so that
Now choose an admissible Dn -ordering on [n] [ [n]  according to the values of
we write
k , break the tie arbitrarily, as long as admissibility is attained. Also i and
remain incomparable. In the Gale order induced by this admissible order, A and
are unrelated. Suppose there exists some
ag X > A in the Gale order. Clearly
contradicting the fact that - A and - B are the unique vertices of (L)
on which f is maximized. Thus A, and likewise B, are both maximal in the Dn Gale
order, contrary to assumption.
We now consider a fourth equivalent denition of orthogonal matroid in the case
that the marked diagram has both nodes n 1 and n circled. In this case an orthogonal
matroid L  A (k1 ;:::;k m ) has and the largest member Am of each
ag
is an admissible set of cardinality n 1. It is easily seen that the collection of all
such (n 1)-sets for all members of L itself constitutes an orthogonal matroid of rank
n 1. (This is likewise true for smaller ranks, as well as for all ranks for Bn and An
matroids.) However, the present case is the only one among all of these in which the
parabolic subgroup P is not maximal since, by the way the diagram is dened, the
two generators corresponding to n 1 and n are both deleted to get the generators
of P . Thus the idea presents itself that such an orthogonal matroid of rank n 1
should be equivalent in some way to a pair of orthogonal matroids of opposite parity,
corresponding to the two marked diagrams with either n 1 or n circled. This is
indeed the case. Let
be a
ag with
m and A m denote the unique extensions of
Am to admissible sets of cardinality n having an even and an odd number of starred
elements, respectively. Let us denote
where the notation is intended to convey that Am 1 is a subset of both A
m and
A m , whereas the latter two are not to be regarded as occurring in any particular
order since they are unrelated by containment. A is sometimes referred to as an
amme. Given a Dn admissible order, we will write A  B if A i  B i in Dn
Gale order, for each
which we dene to mean that either A
m . We will refer to this ordering as modied Gale order.
Theorem 3. For any two
ags FA ; FB of the same type
n 1, with corresponding ori
ammes we have FA  FB if and only if
A  B . Hence a collection of
ags is an orthogonal matroid if and only if the
corresponding collection of ori
ammes satises the maximum condition for modied
Gale order.
Proof. It su-ces to consider the case are
admissible sets of cardinality n 1. We may also
fy  gg, where x; x  are the unique pair neither of which is in A, and
similarly B. Note that if then the theorem is trivial, so we
assume henceforth that this is not the case.
Suppose A  B . If x >
fy  g, we see immediately that A  B. Similar arguments cover the
remaining possible cases of the admissible order restricted to x; x  ;
To prove the converse, assume that A  B. We must prove that fA [
fy  gg. The assumption that A  B means that there is a
bijection  >from A to B, so that a  (a) for all a 2 A. Note that we can assume
without loss of generality that  maps any element b of A\B to itself, for if
and then we can reassign b. Thus we have (a) 2 BrA
if and only if a 2 ArB.
Let us assume that our admissible ordering restricted to x; x  ;
and . The argument for the remaining cases is similar. (In particular,
when x and x  are between y and y  , we just need to reverse the roles of A and B
and reverse the ordering to transform the argument to the above case.) Notice that
A[fxg  B[fyg and A[fxg  B[fy  g as well. Thus we only need to prove either
fy  g. Since x 6= we have two cases:
either
Case 1: x 2 B. Write
we have a
A. We denote
Now if a 2  y or a 2  y  , then we
are done, for we can dene  (or similarly with y  ), with the
rest of  0 agreeing with , and  0 establishes the desired (modied) Gale dominance.
Hence we may now assume that a 2 <
have a
Denoting
and a 3 > a
a
and we write b
We continue in this fashion until either two a i 's coincide (and hence so do the
corresponding b i 's), or until some a i  y or a i  y  for some even i, one of which
must occur eventually since A is nite. In the case of a coincidence, since a i >
for i odd but not for i even, our coincidence is of the form a of the same
parity. Assume that i is the minimal index in such a coincidence. But then b
since  is a bijection, which if i  1 means a
By minimality of i, we must have had
showing that x  2 A, a contradiction. Thus we could not have two
a i 's coincide, so we must instead have a i  y (or y  ) for some even i. Note that for
even j  2, we have a
j+1  a
. We now dene
with . This gives the desired result for Case 1.
Case 2: x  2 B. Starting with b we construct a i 's and b i 's exactly as above,
except that now it is the even-numbered a i which are always larger than
want to nd one odd-numbered a i which is greater than either y or y  . The rest of
the proof is similar to Case 1, with being used to contradict any coincidence
among the a i 's.
7. Relation between symplectic and orthogonal matroids
In this section we view both symplectic matroids and orthogonal matroids in terms
of their combinatorial description. Both are dened in terms of admissible k-element
subsets of [n] [ [n]  . The number k is called the rank of the symplectic or orthogonal
matroid.
Corollary. Every orthogonal (
ag) matroid is a symplectic (
ag) matroid.
Proof. This follows directly from Theorem 2 since every admissible set of
ags for Dn
is admissible for Bn and every root of Dn is a root of Bn .
In general, the converse is false. For example, f12; 12  g is a rank 2 symplectic (B 4 )
matroid, but is not an orthogonal (D 4 ) matroid. We are not able, in general, to give
a simple combinatorial characterization of when a symplectic matroid is orthogonal
(the geometric characterization is obvious). Below, however, is a characterization for
the special case of a rank n symplectic matroid L  An , called a Lagrangian matroid
in [2] or a symmetric matroid in [6].
Theorem 4. A Bn matroid L of rank n is a Dn matroid if and only if L lies either
entirely in A
n or entirely in A n .
Proof. Assume that L is a symplectic matroid. In one direction the result follows
directly from the denition of orthogonal matroid.
For the other direction, assume that L lies either entirely in A
n or entirely in
A n . Consider any admissible orthogonal ordering  of [n] [ [n]  . Without loss of
generality, let  be the ordering in (3.3). Use the notation  s for either one of the two
admissible symplectic orderings that are linear extensions of . With respect to  s
there is a Gale maximum an ), where the a i can be taken in descending
order with respect to  s . Thus for any descending order,
we have b i  s a i for all i. However, the same inequality b i  a i also holds for the
orthogonal ordering unless n and n  appear in the same position in A and B, resp.
But that can happen only if A\ [n This would imply A 2 A
n and
or the other way around, a contradiction.
8. Representable orthogonal matroids.
Some symplectic matroids and orthogonal matoids arise naturally from symplectic
and orthogonal geometries, respectively, in much the same way that ordinary matroids
arise from projective geometry. The representation of symplectic matroids was
discussed in [2]; the representation of orthogonal matroids is discussed in this section.
However, it is convenient to consider the symplectic and the orthogonal case simulta-
neously; this leads to a simplied treatment of the symplectic case as well as a proof
in the orthogonal case. We will consider only the representation of symplectic and
orthogonal matroids of type k, for some k  n. Flag symplectic and
ag orthogonal
matroids can similarly be represented using
ags of totally isotropic subspaces.
Both a symplectic space and an orthogonal space consist of a pair (V; f) where V
is a vector space over a eld of characteristic 6= 2 with basis
and f is a bilinear form hereafter denoted just (; ). The bilinear form is antisymmetric
for a symplectic space and symmetric in an orthogonal space. In both cases
A subspace U of V is totally isotropic if (u;
Let U be a totally isotropic subspace of dimension k of either a symplectic or an
orthogonal space V . Since U ? U , and dimU we see that k  n.
Now choose a basis fu of U , and expand each of these vectors in terms
of the basis E:
. Thus we have represented the totally
isotropic subspace U as the row-space of a k2n matrix
with the columns indexed by [n] [ [n]  , specically, the columns of A by [n] and those
of B by [n]  .
Given a totally isotropic subspace U of dimension k, let be a k  2n
matrix dened above. If X is any k-element subset of [n] [ [n]  , let CX denote the
formed by taking the j-th column of C for all j 2 X. Dene a collection
LU of k-element subsets of [n] [ [n]  by declaring X 2 LU if X is an admissible k-element
set and det(CX ) 6= 0. Note that LU is independent of the choice of the basis
of U .
Theorem 5. If U is a totally isotropic subspace of a symplectic or orthogonal space,
then LU is the collection of bases of a symplectic or orthogonal matroid, respectively.
Proof. The fact that the row space is totally isotropic implies
for all i; l. In terms of the matrices A and B this is equivalent to
where A i and B i denote the respective row vectors and  denotes the the usual dot
product. The sign is + in the orthogonal case and in the symplectic case. In the
orthogonal case, taking l, the equality (8.1) above implies
Let  be any admissible ordering of [n][[n]  . Order the columns of C in descending
order with respect to . (The order of n and n  is arbitrary in the orthogonal case.)
The re-ordering may be done by rst interchanging pairs of columns indexed by j
and j  for some j. In order to maintain (8.1) in the symplectic case (where we still
consider A to be the rst n columns of C), one of the two interchanged columns must
be multiplied by 1. Note that this does not change LU . Second, do like column
permutations on both A and B. Finally, reverse the order of the columns of B. Then
and (8.2) remain valid, provided we now interpret XY to mean the dot product
of X with the reverse of Y .
In light of the preceding paragraph, we may, without loss of generality, assume  is
the ordering (3.2) in the symplectic case and the ordering (3.3) in the orthogonal case.
This will keep our notation simpler. We must show that LU contains a maximum
member with respect to the induced Gale ordering. Using the usual row operations,
put C in echelon form so that each row has a leading 1, the leading 1 to the right
of the leading one in the preceeding row, and zeros lling each column containing
a leading 1. Let X 0 be the subset of [n] [ [n]  corresponding to the columns with
leading ones. It is now su-cient to show that (1) X 0 is admissible, and (2) X  X 0
for any X such that the determinant of the k  k minor CX of C corresponding to X
is non-zero.
Concerning (1), assume that X 0 is not admissible. Then both j and j  appear in
l be the rows for which there is a leading 1 at positions
contradicting equality (8.1).
Concerning (2), if it is not the case that X  X 0 , then, for some j, the rst j
columns of CX have at least k zeros. But such a matrix CX has
determinant 0. The exception to this argument is in the orthogonal case when X
and X 0 contain the incomparable elements, n and n  , in the same position when
the elements of X and X 0 are arranged in descending order. However, for this to
happen, there must be a row of C, say the j-th, such that A
then by equality (8.2) we have b jn
In either case the rst j columns of CX or CX0 again have at least k
zeros, implying that det(CX



--R

The lattice of ats and its underlying ag matroid polytope


Coxeter groups and matroids
An adjacency criterion for Coxeter matroids

Some characterizations of Coxeter groups

On a general de
Combinatorial geometries and torus strata on homogeneous compact manifolds
Geometry of Coxeter Groups
A geometric characterization of Coxeter matroids
The greedy algorithm and Coxeter matroids
Theory of Matroids
--TR
Greedy algorithm and symmetric matroids
Symplectic Matroids
An Adjacency Criterion for Coxeter Matroids
The Greedy Algorithm and Coxeter Matroids

--CTR
Richard F. Booth , Alexandre V. Borovik , Neil White, Lagrangian pairs and Lagrangian orthogonal matroids, European Journal of Combinatorics, v.26 n.7, p.1023-1032, October 2005
Richard F. Booth , Maria Leonor Moreira , Maria Rosrio Pinto, A circuit axiomatisation of Lagrangian matroids, Discrete Mathematics, v.266 n.1-3, p.109-118, 6 May
coxeter matroid;coxeter group;orthogonal matroid;bruhat order