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.

	CG on GILA V: The Polya enumeration…
	rajeshd007 on Gradient descent
	Robert on Gradient descent
	Qiaochu Yuan on Gradient descent
	Kram Einsnulldreizwe… on Gradient descent

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