5. Bruhat order

I was planning to include this as part of an earlier post, but I figured this was important enough to warrant a new post. Bruhat order is a partial ordering on a Weyl group that arises from Schubert calculus. The main result required here is Theorem 5.3, but since this is its own post I added some additional material that we may explore in further detail later. We have two main goals here: one is to develop the theory sufficiently to state and prove the main result in my dissertation, and the other is to present some of my work that is unpublished and probably will only be published here. It's going to take a few more posts to get to my dissertation, after which we will see where it goes. There is an unpublished result of mine based on the root systems that has already been cited by Sara Billey in a talk and that I hope to get to here.

Definition 1: Let $(R,B)$ be a root system. If $u,v\in W(R)$, define $u\to v$ if there exists $y\in I(v)$ such that $us_y=v$; that is, $u^{-1}v$ is a reflection and $\ell(u) < \ell(v)$. Then define a partial ordering $\leq$, called Bruhat order, to be the reflexive, transitive closure of $\to$.

This definition of Bruhat order is not always the easiest to work with. The main theorem in this post gives another characterization of Bruhat order in terms of subwords.

Definition 2: Given a word $(s_{x_1},\ldots,s_{x_n})$, we say that a sequence $(e_1,\ldots,e_n)$ is a subword of this word if $e_i\in \{1,s_{x_i}\}$ for all $i$. A subword has an associated word obtained by deleting all of the $1$'s; we say the subword is reduced if the corresponding word is reduced, and we say that the subword is for the element $e_1e_2\cdots e_n$. We can iterate this process; if we have two subwords $\mathbf{u}'=(e_1,\ldots,e_n)$, $\mathbf{u}''=(f_1,\ldots,f_n)$ of a word $\mathbf{u}$ we say that $\mathbf{u}'$ is a subword of $\mathbf{u}''$ if $e_i\in \{1,f_i\}$ for all $i$.

We will need the following lemma (or rather the corollary afterwards).

Lemma 5.1 (The deletion property): Let $(R,B)$ be a root system, let $w\in W(R)$, and let $(s_{x_1},\ldots,s_{x_n})$ be a word for $w$. If $w$ is not reduced, then there exist indices $i < j$ such that $$(s_{x_1},\ldots,\widehat{s_{x_i}},\ldots,\widehat{s_{x_j}},\ldots,s_{x_n})$$ is a word for $w$.

Proof: Let $j$ be the minimal index such that $(s_{x_1},\ldots,s_{x_j})$ is not a reduced word. Let $v=s_{x_1}\cdots s_{x_{j-1}}$. Then $\ell(vs_{x_j}) < \ell(v)$, so there exists an index $i$ such that $$(s_{x_1},\ldots,\widehat{s_{x_i}},\ldots,s_{x_{j-1}})$$ is a word for $vs_{x_j}$. These are the $i$ and $j$ we seek in the statement of the result. $\square$

The proof of the following is easy and we leave it to the reader.

Corollary 5.2: Let $(R,B)$ be a root system and let $w\in W(R)$. Given any word $(s_{x_1},\ldots,s_{x_n})$ for $w$ there exists a reduced subword for $w$. $\square$

Theorem 5.3: Let $(R,B)$ be a root system and let $u,v\in W(R)$. Then $u\leq v$ if and only if for any word $(s_{x_1},\ldots,s_{x_n})$ for $v$ there exists a reduced subword for $u$.

Proof: We prove that if $u\leq v$ then there exists such a reduced subword by induction on $\ell(v)-\ell(u)$, the result being true by the corollary when $\ell(u)=\ell(v)$. Otherwise by definition there exists a $u'$ with $u\leq u'\to v$. By Theorem 2.3 we may delete one element from any word for $v$ to obtain a word for $u'$, or equivalently set the element at some single index to $1$ to obtain a subword for $u'$. By the induction hypothesis, for this subword for $u'$ we have that there is a reduced subword that is a word for $u$. Thus there is a reduced subword for $u$ of the word for $v$, and one implication follows.

Suppose now that there exists such a subword for $u$ in any word for $v$. Let $\mathbf{v}$ be a reduced word for $v$ containing a reduced subword $\mathbf{u}$ for $u$; we prove by induction on $\ell(v)$ that $u\leq v$. When $\ell(v)=0$ we must have that $\ell(u)=0$ so the result holds. Let $s_{x_n}$ be the last simple reflection in $\mathbf{v}$, so the element $\mathbf{v}_{\ell(v)}$, so that $\ell(v)=n$. Let $\widehat{\mathbf{v}}$ be the subword of $\mathbf{v}$ such that $\widehat{\mathbf{v}}_n=1$ and $\widehat{\mathbf{v}}_i=\mathbf{v}_i$ for $i < n$; note that this is a subword for $vs_{x_n}$. Similarly, let $\widehat{\mathbf{u}}$ be the subword of $\mathbf{u}$ such that $\widehat{\mathbf{u}}_n=1$ and $\widehat{\mathbf{u}}_i=\mathbf{u}_i$ for $i < n$. Suppose first $\mathbf{u}_n\neq s_{x_n}$. Then $\mathbf{u}=\widehat{\mathbf{u}}$ is a subword of $\widehat{\mathbf{v}}$, so $u\leq vs_{x_n}\to v$ by the induction hypothesis and the result follows.

If $\mathbf{u}_n=s_{x_n}$, then since $\widehat{\mathbf{u}}$ is a subword for $us_{x_n}$ and is a subword of $\widehat{\mathbf{v}}$ we have by the induction hypothesis that $us_{x_n}\leq vs_{x_n}$. Thus there exists some $u'$ such that $us_{x_n}\leq u'\to vs_{x_n}$, and there is a reduced subword $\mathbf{u}'$ of $\widehat{\mathbf{v}}$ for $u'$. Assume without loss of generality that $\widehat{\mathbf{u}}$ is a subword of $\mathbf{u}'$. We split into two cases, depending on whether $x_n\in I(u')$.

If $x_n\notin I(u')$, then $\ell(u's_{x_n}) > \ell(u')$, hence if $\mathbf{u}''$ is the subword of $\mathbf{v}$ for $u's_{x_n}$ such that $\mathbf{u}''_i=\mathbf{u}'_i$ for $i < n$ and $\mathbf{u}''_n=s_{x_n}$, then since $\mathbf{u}$ is a subword of $\mathbf{u}''$ and $u's_{x_n}\to v$ (since if $u's_y=vs_{x_n}$ then $(u's_{x_n})s_{x_n\ast y}=v$) we have by the induction hypothesis that $u\leq u's_{x_n}\leq v$ and we are done.

If $x_n\in I(u')$, then we may assume that $\mathbf{u}'_n=s_{x_n}$. This is because if this were not the case then we could delete an element of $\mathbf{u}'$, setting say $\mathbf{u}'_i=1$ to obtain a word for $u's_{x_n}$, then set $\mathbf{u}'_n=s_{x_n}$ to obtain another subword for $u'$. $\mathbf{u}'$ contains a reduced subword for $us_{x_n}$ by the induction hypothesis whose last element is not $s_{x_n}$ (because no word for $us_{x_n}$ ends in $s_{x_n}$), hence there is a reduced subword $\widetilde{\mathbf{u}}$ of $\mathbf{u}'$ for $u$, so that $u\leq u'\to vs_{x_n}\to v$ by the induction hypothesis and we are done. The result follows by induction. $\square$

Now we for the additional material, where we relate Bruhat order to subsystems. The following theorem, which is an easy consequence of the theory built so far in this blog, is highly nontrivial in the setting of Coxeter systems. It was the main result of (Dyer, Matthew. On the "Bruhat graph" of a Coxeter system, Compositio Mathematica 78.2 (1991): 185-191). To start we will need a lemma, followed by a definition, then we may move on to the theorem. Recall that for a root system $(R,B)$ and a subsystem $U$, we defined in Theorem-Definition 4.5 a function $\phi_U:W(R)\to W(U)$ that sends an element $w\in W(R)$ to the element of $W(U)$ whose inversion set in $U$ is the intersection $I(w)\cap U$.

Lemma 5.4: Let $(R,B)$ be a root system, let $U\subseteq R$ be a subsystem, and let $w\in W(R)$. Then $w\in W(U)$ if and only if $$\phi_U(w)=w$$
Proof: By definition, the codomain of $\phi_U$ is $W(U)$, hence if $\phi_U(w)=w$ then $w\in W(U)$. Conversely, suppose $w\in W(U)$ and $\phi_U(w)=w'\in W(U)$. Then $I_U(w)=I_U(w')$, and since $w,w'\in W(U)$ it follows by Proposition 3.5 that $w=w'$. The result follows. $\square$

Definition 3: Let $(R,B)$ be a root system and let $U$ be a subsystem. If $u,v\in W(R)$ are such that $\ell(u) < \ell(v)$ and there exists a root $y\in U$ such that $us_y=v$, then we say that $u\to_U v$. Define $\leq_U$ to be the reflexive, transitive closure of $\to_U$. Note that Bruhat order on $W(U)$ is the restriction of the relation $\leq_U$.

The Bruhat graph of a Weyl group $W(R)$ is the directed graph on $W(R)$ with the edges $u\to v$, where we may consider the edge $u\to v$ as being labeled with the reflection $u^{-1}v$. The theorem below says that the Bruhat graph of $wW(U)\subseteq W(R)$ for any coset $wW(R)$ is isomorphic as a labeled graph to the Bruhat graph of $W(U)$ and is an induced subgraph of the Bruhat graph of $W(R)$ (so there are no extra edges that do not come from reflections in $W(U)$).

Theorem 5.5: Let $(R,B)$ be a root system, let $U$ be a subsystem, and let $w\in W(R)$. If $u,v$ are both contained in the coset $wW(U)$, then $u\to_R v$ if and only if $u\to_U v$.

Proof: If $u\to_U v$, then clearly $u\to_R v$. Conversely, if $u\to_R v$, then there exists a reflection $t\in W(R)$ such that $ut=v$. Since $u,v$ are in the same left coset of $W(U)$ we must have that $t\in W(U)$. We need to prove then that if $t\in W(R)$ is a reflection and $t\in W(U)$, then there is a root $y\in U$ such that $t=s_y$. The contrapositive is that if $t=s_y$ for some $y\in R-U$, then $t\notin W(U)$. To see this, let $w'\in W(R)$ be an element such that $w'(y)\in B$. Then $s_y\notin W(U)$ if and only if $s_{w'(y)}\notin W(w'(U))$. For all $z\in w'(U)\cap R^+(B)$ we have that $w'(y)\ast z\in R^+(B)$, hence $\phi_{w'(U)}(s_{w'(y)})=1\neq s_{w'(y)}$, hence $s_{w'(y)}\notin W(w'(U))$ by Lemma 5.4 and we are done. $\square$

This implies that if $u,v\in wW(U)$ and $\phi_U(u)\leq_U \phi_U(v)$, then $u\leq v$. However, this does not in general imply that if $u,v\in wW(U)$ and $u\leq v$ then $\phi_U(u)\leq_U \phi_U(v)$. For an example, consider the root system $R_{A}^3$, defined in post 2. Let $x=t_2-t_3$ and let $y=t_1-t_4$. Then $U=\{\pm x,\pm y\}$ is a subsystem of $R_{A}^3$ since $x\ast y=y$ and $y\ast x=x$, and $s_x\leq s_y$. However it is not the case that $s_x\leq_U s_y$ because $\ell_U(s_x)=\ell_U(s_y)$.