Before we define Bruhat order, I’d like to say a few things by way of motivation. Warning: I know nothing about algebraic groups, so take everything I say with a grain of salt.
A (maximal) flag in a vector space of dimension is a chain of subspaces such that . The flag variety of is, for our purposes, the “space” of all maximal flags. acts on the flag variety in the obvious way, and the stabilizer of any particular flag is a Borel subgroup . If denotes a choice of ordered basis, one can define the standard flag , whose stabilizer is the space of upper triangular matrices of determinant with respect to the basis . This is the standard Borel, and all other Borel subgroups are conjugate to it. Indeed, it’s not hard to see that acts transitively on the flag variety, so the flag variety can be identified with the homogeneous space .
The flag variety for is a projective variety, hence a finite CW-complex, and there is a tricky way to compute the dimensions of its cells. Over any field , the points of the flag variety over are precisely the maximal flags in . In particular, over a finite field we can count the maximal flags. There are ways to choose , since we can take it to be spanned by any nonzero vector but must quotient out by scalar multiplication. There are ways to choose , since we can add to any nonzero vector in the quotient space but must again quotient out by scalar multiplication. And so forth. It follows that the total number of maximal flags in is
where denotes the -factorial.
Now, if we take on faith that the flag variety decomposes into a bunch of copies of affine space glued together (as projective space does), it follows that over the complex numbers, only has cells in even dimensions. This means that all boundary maps are trivial, hence that the rank of (singular homology) is equal to the number of cells of dimension . But by the Weil conjectures, is the coefficient of in the number of points of over ! So one can compute the Betti numbers of flag varieties just by expanding out the -factorial above.
On the other hand, as mentioned earlier, it’s not hard to show that
when . This is far from a coincidence; it is what might be called a decategorification of the Bruhat decomposition
which completely describes the cells in the flag variety. (More general Bruhat decompositions and Weyl groups come from the theory of BN-pairs.) Each cell has dimension , which leads to the formulas above. This relationship generalizes to more general algebraic groups, where is replaced by a different Weyl group. (Once again, John Baez has some good exposition on this, although it starts in week178 and not week184 as I had previously thought.)
Now, the cells are not closed. Their closures are subvarieties of called Schubert varieties. Schubert varieties define a partial order on as follows: we say that if and only if . Since Schubert varieties can in general be singular, it’s important to understand this partial order in order to get some information about those singularities.
This partial order, Chevalley-Bruhat order (but usually just called Bruhat order), has a completely combinatorial definition and can be defined on any Coxeter group, regardless of whether it is a Weyl group or not. Today we’ll describe Bruhat order and prove some of its properties.
Let be a Coxeter system and define a partial order on as follows. The Bruhat graph has vertices the elements of and an edge from to whenever and . (Later we will need the edge to be labeled by .) The transitive closure of this graph then describes Bruhat order. Concretely, whenever there is a sequence of elements of such that and such that .
Example. When , the Bruhat order is as simple as it could be: if and only if .
Example. When , the Bruhat order is closely related to bubblesort. The reflections are precisely the transpositions , and the number of positive roots sent to negative roots by a permutation is precisely the number of inversions of the permutation, so if and only if swaps two elements which are in the wrong order in the one-line notation for . For example,
It’s not hard to see that is an automorphism of Bruhat order. Another automorphism is less obvious.
Lemma: Let be finite with longest element . Then if and only if .
Proof. Since sends all positive roots to negative roots, it follows that . The result then follows by definition.
(Once we have proven that is a rank function on , it will follow that is rank-symmetric. One should think of this as a combinatorial reflection of Poincare duality in the flag variety, where is the avatar of the fundamental class. Indeed, since the identity is less than every element, it follows that is greater than every element, hence that the closure of the Schubert variety is the entire flag variety in the Weyl group case.)
So is an antiautomorphism of Bruhat order. It will turn out that Bruhat order can be defined with multiplication on either the right or the left, so is also an antiautomorphism of Bruhat order, hence is an automorphism of Bruhat order. Since , it follows that permutes the simple reflections. Since it is also an inner automorphism, it preserves the order of products of simple reflections, e.g. it is a diagram automorphism (an automorphism of the Coxeter diagram), and we even know it is of order since is also a longest element. More generally, any diagram automorphism gives an automorphism of Bruhat order. Except in the dihedral case, all automorphisms of Bruhat order are a composition of inversion and a diagram automorphism (Waterhouse).
There is a nice characterization of Bruhat order in terms of reduced words, but to prove it we will need the following important lemma.
Lemma: Let with . Then either or (or both).
Proof. It suffices to check the case that . If we are done. If then . If , then we claim that as follows. First, letting $t’ = sts$ we see that , so it suffices to show that . Suppose otherwise. If is a reduced expression, then so is because we assumed . Applying the strong exchange condition to and , we conclude that is obtained from by omitting one factor. This factor cannot be since , so
hence , which contradicts .
Theorem: Fix a reduced word . Then if and only if is a subexpression of .
Proof. The strong exchange and deletion conditions readily imply that any is a subexpression of . In the other direction, we will induct on . The conclusion is clear for . Suppose is a subexpression of . If , then apply the inductive hypothesis to . If , then the inductive hypothesis tells us that . Then by the lemma, either
Note that this definition of the Bruhat order, while convenient, is not a good initial definition since it is far from obvious that the defined relation is transitive.
The length function
An element of a poset is said to cover an element , written , if the interval has only the two elements . A graded poset is a poset with a rank function, that is, an order-preserving map , such that whenever . Examples include the lattice of subsets of a finite set, where the rank function is the number of elements, or more generally the lattice of faces of a convex polytope, where the rank function is the dimension of the face.
It is reasonable to suspect that the length is the rank function on Bruhat order, but this is not obvious from the definition. To prove it, we will need the following lemma.
Lemma: Let in the Bruhat order, with . Suppose there exists such that and . Then and .
Proof. By the lemma in the last section, either or . The first case is impossible since but . Since , we conclude that . And since , it follows that .
Theorem: Let . Then there exists a maximal chain of length between them, e.g. a sequence such that and such that . In particular, Bruhat order is graded by length.
Proof. We proceed by induction on . The statement is obvious when . Let and let , so that . We know that is some subexpression.
Case: . If , then is a subexpression of , so by induction we can find a maximal chain. If , then is a subexpression of , so again by induction we can find a maximal chain.
Case: . The inductive hypothesis gives us a maximal chain
with . Since while , there is a least index such that . We claim that . Otherwise, applying the above lemma to gives ; contradiction. On the other hand, for we know that because . Applying the lemma to gives . It now follows that
is a maximal chain with the desired property.