The Bruhat graph by length-increasing reflection chains, the Bruhat order, inversion symmetry, and reflection parity

Let $(S,m)$ be a Coxeter matrix (Coxeter matrices, the presented Coxeter group, reduced words, length, and standard parabolic subgroups), let $W$ be the presented group with length function $\mathrm{\ell }$ and identity $1$ (Coxeter matrices, the presented Coxeter group, reduced words, length, and standard parabolic subgroups), and let $T=\{ws{w}^{-1}:w\in W,s\in S\}$ be its set of reflections (The canonical reflection homomorphism, roots, reflections, and the positive cone (2)).

(1) The Bruhat graph and the Bruhat order. For $u,v\in W$ write $u\to v$ if $v=ut$ for some $t\in T$ with $\mathrm{\ell }(v)>\mathrm{\ell }(u)$. The directed graph on $W$ with these edges is the Bruhat graph of $(W,S)$. Define $u\le v$ if there exist $u_0,\dots ,u_k\in W$ with $u=u_0\to u_1\to \cdots \to u_k=v$; the empty chain ($k=0$) is allowed, so $u\le u$ for every $u$. This relation is the Bruhat order on $W$. Both $\to$ and $\le$ are predicates on $W\times W$ defined from the length function of Coxeter matrices, the presented Coxeter group, reduced words, length, and standard parabolic subgroups, and chains in the definition of $\le$ are finite sequences of elements of $W$, so both relations are well defined; every object below is a subset or a predicate on the fixed group $W$, and no choice principle is used anywhere in this definition.

(2) Partial order and the identity. $\le$ is a partial order on $W$: it is reflexive and transitive by construction (an empty chain, and concatenation of chains), and it is antisymmetric because $\mathrm{\ell }$ strictly increases along every edge, so a chain from $u$ to $v$ containing at least one edge satisfies $\mathrm{\ell }(u)<\mathrm{\ell }(v)$ (The natural numbers $\mathbb{N}$ (von Neumann)). Consequently $u\le v$ together with $\mathrm{\ell }(u)=\mathrm{\ell }(v)$ forces $u=v$, and every $u<v$ (that is, $u\le v$ and $u\mathrm{\ne }v$) satisfies $\mathrm{\ell }(u)<\mathrm{\ell }(v)$. Moreover $1\le w$ for every $w\in W$: for a reduced expression $w=s_1\cdots s_k$ and $w_j:=s_1\cdots s_j$ one has $\mathrm{\ell }(w_j)=j$ (a shorter expression for the prefix $s_1\cdots s_j$, substituted into $s_1\cdots s_k$, would be a word of length $<k$ for $w$), so $w_{j-1}\to w_j$ because $w_{j-1}^{-1}{w}_j=s_j=1\cdot s_j\cdot 1^{-1}\in T$ and $\mathrm{\ell }(w_j)=j>\mathrm{\ell }(w_{j-1})=j-1$ (Group and abelian group).

(3) Inversion and left multiplication. For all $u,v\in W$ one has $u\le v$ if and only if $u^{-1}\le v^{-1}$. More precisely, a chain $u=u_0\to \cdots \to u_k=v$ with $u_{j+1}=u_j{t}_j$, $t_j\in T$, inverts to the chain $u^{-1}=u_0^{-1}\to \cdots \to u_k^{-1}=v^{-1}$, because $u_{j+1}^{-1}=t_j{u}_j^{-1}=u_j^{-1}(u_j{t}_j{u}_j^{-1})$ with $u_j{t}_j{u}_j^{-1}\in T$ and $\mathrm{\ell }(u_{j+1}^{-1})=\mathrm{\ell }(u_{j+1})>\mathrm{\ell }(u_j)=\mathrm{\ell }(u_j^{-1})$; here $\mathrm{\ell }(x)=\mathrm{\ell }(x^{-1})$ holds because reversing a reduced expression of $x$ gives a reduced expression of $x^{-1}$ (Support, intrinsic parabolic presentations, minimal coset representatives and length additivity, with the type-A identification (3)). Consequently the order is also generated by left multiplication by reflections: if $x\in W$, $t\in T$ and $\mathrm{\ell }(tx)>\mathrm{\ell }(x)$, then $x\to tx$, since $x^{-1}(tx)=x^{-1}tx\in T$ and $T$ is closed under conjugation (Group and abelian group).

(4) Reflection parity. If $x\in W$ and $t\in T$ then $\mathrm{\ell }(xt)\equiv \mathrm{\ell }(x)+1(\mathrm{m}\mathrm{o}\mathrm{d}2)$, so $\mathrm{\ell }(xt)\mathrm{\ne }\mathrm{\ell }(x)$; in particular $x\to xt$ if and only if $\mathrm{\ell }(xt)>\mathrm{\ell }(x)$, and for each pair $(x,t)$ exactly one of the relations $x\to xt$, $xt\to x$ holds. Indeed Length parity, exchange, two-letter deletion, and faithfulness of the signed reflection action (1) supplies the sign character $\mathrm{sgn}:W\to \{\pm 1\}$ with $\mathrm{sgn}(s)=-1$ for all $s\in S$ and $\mathrm{sgn}(x)=(-1{)}^{\mathrm{\ell }(x)}$ for all $x\in W$; as $\mathrm{sgn}$ is a homomorphism into the abelian group $\{\pm 1\}$ (Group and abelian group) one has $\mathrm{sgn}(ws{w}^{-1})=\mathrm{sgn}(s)=-1$ for every $w\in W$ and $s\in S$, so $\mathrm{sgn}(t)=-1$ for every $t\in T$, and then $\mathrm{sgn}(xt)=-\mathrm{sgn}(x)$ gives the asserted congruence.

The interval $[u,v]:=\{x\in W:u\le x\le v\}$ and the statement that $\mathrm{\ell }$ is a rank function are introduced only after the saturated-chain results of Finiteness of Bruhat intervals, the chain refinement property, and grading by length. The subword description of $\le$ used throughout this page is the theorem The subword characterization of Bruhat order and its independence of the reduced expression ↗, the recorded justifier of this definition; no subword assertion is made here.

No form of the Axiom of Choice is used: every object is a subset, a subgroup or a predicate on the fixed group $W$, lengths lie in $\mathbb{N}$ (The natural numbers $\mathbb{N}$ (von Neumann)), and the only arguments invoked above are the sign character, prefix reduction and inversion of reduced words.

The definition deliberately asserts no finiteness of $W$, no longest element, and no interval finiteness; intervals and chain structure are treated in Finiteness of Bruhat intervals, the chain refinement property, and grading by length, and the order-theoretic description by subwords in The subword characterization of Bruhat order and its independence of the reduced expression ↗.