Chevalley-Bruhat order

Hecke algebras and the Kazhdan-Lusztig polynomials »

Chevalley-Bruhat order

July 11, 2010 by Qiaochu Yuan

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 $V$ of dimension $n$ is a chain $V_0 \subset V_1 \subset ... \subset V_n$ of subspaces such that $\dim V_i = i$ . The flag variety of $G = \text{SL}(V) = \text{SL}_n$ is, for our purposes, the “space” of all maximal flags. $\text{SL}_n$ acts on the flag variety in the obvious way, and the stabilizer of any particular flag is a Borel subgroup $B$ . If $e_1, ... e_n$ denotes a choice of ordered basis, one can define the standard flag $0, \text{span}(e_1), \text{span}(e_1, e_2), ...$ , whose stabilizer is the space of upper triangular matrices of determinant $1$ with respect to the basis $e_i$ . This is the standard Borel, and all other Borel subgroups are conjugate to it. Indeed, it’s not hard to see that $\text{SL}_n$ acts transitively on the flag variety, so the flag variety can be identified with the homogeneous space $G/B$ .

The flag variety for $\text{SL}_n$ 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 $F$ , the points of the flag variety over $F$ are precisely the maximal flags in $F^n$ . In particular, over a finite field $\mathbb{F}_q^n$ we can count the maximal flags. There are $\frac{q^n - 1}{q - 1} = 1 + q + ... + q^{n-1}$ ways to choose $V_1$ , since we can take it to be spanned by any nonzero vector but must quotient out by scalar multiplication. There are $\frac{q^{n-1} - 1}{q - 1} = 1 + q + ... + q^{n-2}$ ways to choose $V_2$ , since we can add to $V_1$ any nonzero vector in the quotient space $V / V_1$ but must again quotient out by scalar multiplication. And so forth. It follows that the total number of maximal flags in $\mathbb{F}_q^n$ is

$(1 + q)(1 + q + q^2)...(1 + q + ... + q^{n-1}) = (n)_q!$

where $(n)!_q$ denotes the $q$ -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, $G/B$ only has cells in even dimensions. This means that all boundary maps are trivial, hence that the rank of $H_{2i}(G/B)$ (singular homology) is equal to the number of cells of dimension $2i$ . But by the Weil conjectures, $H_{2i}(G/B)$ is the coefficient of $q^i$ in the number of points of $G/B$ over $\mathbb{F}_q$ ! So one can compute the Betti numbers of flag varieties just by expanding out the $q$ -factorial above.

On the other hand, as mentioned earlier, it’s not hard to show that

$\displaystyle \sum_{w \in W} q^{\ell(w)} = (n)_q!$

when $W = S_n$ . This is far from a coincidence; it is what might be called a decategorification of the Bruhat decomposition

$\displaystyle G/B = \bigcup_{w \in W} BwB/B$ ,

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 $BwB/B$ has dimension $\ell(w)$ , which leads to the formulas above. This relationship generalizes to more general algebraic groups, where $W$ 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 $BwB/B$ are not closed. Their closures $X_w$ are subvarieties of $G/B$ called Schubert varieties. Schubert varieties define a partial order on $W$ as follows: we say that $u \le v$ if and only if $X_u \subseteq X_v$ . 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.

Bruhat order

Let $(W, S)$ be a Coxeter system and define a partial order on $W$ as follows. The Bruhat graph $B(W, S)$ has vertices the elements of $W$ and an edge from $w$ to $w'$ whenever $wt = w', t \in T$ and $\ell(w') < \ell(w)$ . (Later we will need the edge to be labeled by $t$ .) The transitive closure of this graph then describes Bruhat order. Concretely, $w \ge w'$ whenever there is a sequence $t_1, ... t_k$ of elements of $T$ such that $w t_1 ... t_k = w'$ and such that $\ell(w') < \ell(w t_1 ... t_{k-1}) < ... < \ell(w t_1) < \ell(w)$ .

Example. When $W = D_n$ , the Bruhat order is as simple as it could be: $u < w$ if and only if $\ell(u) < \ell(w)$ .

Example. When $W = S_n$ , the Bruhat order is closely related to bubblesort. The reflections $T$ are precisely the transpositions $(ij)$ , and the number of positive roots sent to negative roots by a permutation is precisely the number of inversions of the permutation, so $\ell(wt) < \ell(w)$ if and only if $t$ swaps two elements which are in the wrong order in the one-line notation for $w$ . For example,

$3412 > 3142 > 1342 > 1324 > 1234$ .

It’s not hard to see that $w \mapsto w^{-1}$ is an automorphism of Bruhat order. Another automorphism is less obvious.

Lemma: Let $W$ be finite with longest element $w_0$ . Then $v \le w$ if and only if $w_0 w \le w_0 v$ .

Proof. Since $w_0$ sends all positive roots to negative roots, it follows that $\ell(w_0 v) = \ell(v w_0) = \ell(w_0) - \ell(v)$ . The result then follows by definition.

(Once we have proven that $\ell(w)$ is a rank function on $W$ , it will follow that $W$ is rank-symmetric. One should think of this as a combinatorial reflection of Poincare duality in the flag variety, where $w_0$ is the avatar of the fundamental class. Indeed, since the identity $e$ is less than every element, it follows that $w_0$ is greater than every element, hence that the closure of the Schubert variety $X_{w_0}$ is the entire flag variety in the Weyl group case.)

So $w \mapsto w_0 w$ 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 $w \mapsto w w_0$ is also an antiautomorphism of Bruhat order, hence $w \mapsto w_0 w w_0$ is an automorphism of Bruhat order. Since $\ell(w_0 w w_0) = \ell(w)$ , it follows that $w \mapsto w_0 w w_0$ 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 $2$ since $w_0^{-1} = w_0$ 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 $u \le v$ with $s \in S$ . Then either $us \le v$ or $us \le vs$ (or both).

Proof. It suffices to check the case that $u = vt, t \in T$ . If $s = t$ we are done. If $\ell(us) = \ell(u) - 1$ then $us \le u \le v$ . If $\ell(us) = \ell(u) + 1$ , then we claim that $us < vs$ as follows. First, letting $t’ = sts$ we see that $(us)t' = (vs)$ , so it suffices to show that $\ell(us) < \ell(vs)$ . Suppose otherwise. If $u = s_1 ... s_r$ is a reduced expression, then so is $us = s_1 ... s_r s$ because we assumed $\ell(us) = \ell(u) + 1$ . Applying the strong exchange condition to $vs$ and $t'$ , we conclude that $vs = (us)t'$ is obtained from $s_1 ... s_r s$ by omitting one factor. This factor cannot be $s$ since $s \neq t$ , so

$vs = s_1 ... \hat{s_i} ... s_r s$

hence $\ell(v) \le r$ , which contradicts $\ell(v) > \ell(u)$ .

Theorem: Fix a reduced word $v = s_1 ... s_r$ . Then $u \le v$ if and only if $u$ is a subexpression of $s_1 ... s_r$ .

Proof. The strong exchange and deletion conditions readily imply that any $u \le v$ is a subexpression of $s_1 ... s_r$ . In the other direction, we will induct on $r$ . The conclusion is clear for $r = 1$ . Suppose $s_{i_1} ... s_{i_q}$ is a subexpression of $s_1 ... s_r$ . If $i_q < r$ , then apply the inductive hypothesis to $s_1 ... s_{r-1}$ . If $i_q = r$ , then the inductive hypothesis tells us that $s_{i_1} ... s_{i_{q-1}} \le s_1 ... s_{r-1}$ . Then by the lemma, either

$s_{i_1} ... s_{i_q} \le s_1 ... s_{r-1} < s_1 ... s_r$

$s_{i_1} ... s_{i_q} \le s_1 ... s_r$ .

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 $y$ of a poset is said to cover an element $x$ , written $y \triangleright x$ , if the interval $[x, y] = \{ z : x \le z \le y \}$ has only the two elements $x, y$ . A graded poset $P$ is a poset with a rank function, that is, an order-preserving map $\rho : P \to \mathbb{N}$ , such that $\rho(y) = \rho(x) + 1$ whenever $y \triangleright x$ . 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 $\ell(w)$ 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 $u < v$ in the Bruhat order, with $\ell(u) + 1 = \ell(v)$ . Suppose there exists $s \in S$ such that $u < us$ and $us \neq v$ . Then $v < vs$ and $us < vs$ .

Proof. By the lemma in the last section, either $us \le v$ or $us \le vs$ . The first case is impossible since $\ell(us) = \ell(v)$ but $us \neq v$ . Since $us \neq vs$ , we conclude that $us < vs$ . And since $\ell(v) = \ell(us) < \ell(vs)$ , it follows that $v < vs$ .

Theorem: Let $u < v$ . Then there exists a maximal chain of length $\ell(v) - \ell(u)$ between them, e.g. a sequence $w_0, ... w_m$ such that $u = w_0 < ... < w_m = v$ and such that $\ell(w_i) + 1 = \ell(w_{i+1})$ . In particular, Bruhat order is graded by length.

Proof. We proceed by induction on $\ell(u) + \ell(v)$ . The statement is obvious when $\ell(u) + \ell(v) = 1$ . Let $v = s_1 ... s_r$ and let $s = s_r$ , so that $\ell(vs) < \ell(v)$ . We know that $u = s_{i_1} ... s_{i_q}$ is some subexpression.

Case: $u < us$ . If $i_q = r$ , then $us$ is a subexpression of $vs = s_1 ... s_{r-1}$ , so by induction we can find a maximal chain. If $i_q \neq r$ , then $u$ is a subexpression of $vs$ , so again by induction we can find a maximal chain.

Case: $us < u$ . The inductive hypothesis gives us a maximal chain

$us = w_0 < ... < w_m = v$

with $\ell(w_{i+1}) = \ell(w_i) + 1$ . Since $u = w_0 s > w_0 = us$ while $vs = w_m s < w_m = v$ , there is a least index $i$ such that $w_i s < w_i$ . We claim that $w_i s = w_{i-1}$ . Otherwise, applying the above lemma to $w_{i-1}, w_{i-1} s, w_i$ gives $w_i < w_i s$ ; contradiction. On the other hand, for $1 \le j < i$ we know that $w_j s \neq w_{j-1}$ because $w_j < w_j s$ . Applying the lemma to $w_{j-1}, w_{j-1} s, w_j$ gives $w_{j-1} s < w_j s$ . It now follows that

$u = w_0 s < w_1 s < ... < w_{i-1} s = w_i < w_{i+1} < ... < w_m = v$

is a maximal chain with the desired property.

Posted in math.CO | Tagged Coxeter groups | Leave a Comment

Comments RSS

	Anonymous on Lie algebras are groups
	Matthew Kiely on What’s a fire, and why d…
	Combien il y a-t-il… on Groupoid cardinality
	Qiaochu Yuan on A meditation on semiadditive…
	Qiaochu Yuan on Units

Annoying Precision

"A good stock of examples, as large as possible, is indispensable for a thorough understanding of any concept, and when I want to learn something new, I make it my first job to build one." – Paul Halmos