Category Archives: Coxeter Groups

Hecke Algebra of a Coxeter Group

Let G be a Coxeter group with a generating set S.

Definition 1.  The Hecke algebra of G, denoted H(G), is generated by elements \{T_g\}_{g\in G} over the ring \mathbb{Z}[q^{1/2},q^{-1/2}] such that multiplication satisfies

\begin{array}{lcll}T_sT_x&=&qT_{sx}+(q-1)T_x&\mbox{if~}sx<x\mbox{~for~}s\in S\\T_xT_y&=&T_{xy}&\mbox{if~}\ell(x)+\ell(y)=\ell(xy)\end{array}

where the order is Bruhat.  It is trivial to verify that the Hecke algebra is unital with unit T_1.

Proposition 2.  If s\in S, then T_s is invertible with inverse

T_{s}^{-1}=(q^{-1}-1)T_1+q^{-1}T_s.

Proof.

\begin{array}{lcl}T_sT_{s}^{-1}&=&T_s\left((q^{-1}-1)T_1+q^{-1}T_s\right)\\&=&T_s(q^{-1}T_1-T_1+q^{-1}T_s)\\&=&q^{-1}T_sT_1-T_sT_1+q^{-1}T_sT_s\\&=&(q^{-1}-1)T_sT_1+q^{-1}T_sT_s\\&=&(q^{-1}-1)T_s+T_1+q^{-1}(q-1)T_s\\&=&T_1.\end{array}

It follows that all elements of the form T_g with g\in G are invertible, so the Hecke algebra is a division algebra.  Moreover it is a *-algebra with involution defined by

\displaystyle \overline{\sum_{g\in G}p_g(q^{1/2})T_g}=\sum_{g\in G}p_g(q^{1/2})T_{g^{-1}}^{-1}.

It turns out that there is a basis \{x_g\}_{g\in G} of H(G) where

\displaystyle x_g=q^{\ell(g)/2}\sum_{h\leq g}(-1)^{\ell(h,g)}q^{-\ell(h)}P_{h,g}T_h

with \ell(h,g)=|\ell(h)-\ell(g)| and P_{h,g}\in\mathbb{Z}[q], which can be proven to uniquely exist for elements h,g\in G, which are called the Kazhdan-Lusztig polynomials.

[1]  Björner, Anders and Francesco Brenti.  Combinatorics of Coxeter Groups.  Vol. 231.  Graduate Texts in Mathematics.  Springer.  2005.

Bruhat Order

The Bruhat order is defined on a Coxeter group G in the following manner for x,y\in G:

  1. x\stackrel{t}{\to}y\Leftrightarrow x^{-1}y=t with t a reflection (conjugate of a generator) and \ell(x)<\ell(y),
  2. x\leq y\Leftrightarrow x\stackrel{t_0}{\to}x_1\stackrel{t_1}{\to}\cdots\stackrel{t_{n-1}}{\to}x_n\stackrel{t_n}{\to}y.

Reflexivity is clear since x\stackrel{1}{\to}x (assuming 1 is considered a generator).  Transitivity is trivial.  And if we have x\leq y and y\leq x, then in the simple case where x\stackrel{t}{\to}y and y\stackrel{t'}{\to}x, we have

x^{-1}y=t

and

y^{-1}x=t'

which imply that t'=t^{-1} and hence that t=t'.  So x^{-1}y=y^{-1}x.  Since we must have \ell(x)=\ell(y), it follows that x=y.  The general cases are done by induction.  So we have antisymmetry.

So it is a partial order on the Coxeter group.  The Bruhat digraph is constructed with elements as vertices and a directed edge from x to y iff x\leq y.  Note how this ordering differs from the simplicial ordering we previously mentioned on the induced Coxeter complex.

Recall the notion of standard subgroups (also known as parabolic subgroups) of a Coxeter group where J triply represents a subset of indices of a generating set, the corresponding generators indexed by those indices, and the subgroup generated by such generators.  Also recall the definition of descents of elements.  In the following definition, I,J are used in the second sense (as subsets of generators), and we will use G_J to represent the subgroup generated by J.

Definition 1.  Let I\subseteq J\subseteq S and define

\begin{array}{l}D_I^J=\{g\in G:I\subseteq D_R(g)\subseteq J\}\\D_I=D_I^I\\D^I=D_\varnothing^{S-I}.\end{array}

The sets D_I^J are called the right descent classes (or the analogous definition for left descent classes).

Proposition 2.  Let J\subseteq S.  Then every g\in G has a unique factorization of the form g=g^Jg_J where g^J\in D^J and g_J\in G_J.  Moreover we have \ell(g)=\ell(g^J)+\ell(g_J).

We can define the map P^J:G\to G^J where P^J(g)=g^J.  This map is clearly idempotent.  Moreover we have the following.

Proposition 3.  The map P^J preserves Bruhat order (g_1\leq g_2\Rightarrow g_1^J\leq g_2^J).

[1]  Björner, Anders and Francesco Brenti.  Combinatorics of Coxeter Groups.  Vol. 231.  Graduate Texts in Mathematics.  Springer.  2005.

More on Coxeter Groups

Definition 1.  Let B and N be subgroups of a group G.  They are called a BN-pair if

  1. B\cup N generates G and B\cap N\unlhd N.
  2. W=N/(B\cap N) is generated by a set S of involutions.
  3. Let s\in S and w\in W, then BsB\cdot BwB\subseteq BswB\cup BwB.
  4. Let s\in S, then BsB\cdot BsB\neq B.

W is called the Weyl group of the BN-pair, and |S| is called the rank of the BN-pair.

So from 3 and 4 we have BsB\cdot BsB\subseteq BsB.  If G has a BN-pair, then it has a direct decomposition called the Bruhat decomposition.  It has the form

\displaystyle G=\bigsqcup_{w\in W}BwB.

This is plausible since W has stuff in N but not in B (if not 1).  So a term in the union is represented as a product of something in N (but not B) multiplied on both sides by something in B, but together B and N generate G.

One can further show that if G has a BN-pair, then W is a Coxeter group with generating set S.  Also, every element by definition has the form g=r_1\cdots r_k with r_i generators and k minimal.  k is then called the length of g and denoted \ell(g).

Definition 2.  We define a reflection in a Coxeter group G as a conjugate of a generator.

Exchange Property.  Let g=s_1\cdots s_k be a reduced word with each s_i a generator.  If \ell(sg)\leq\ell(g) for a generator s, then sg=s_1\cdots\hat{s_i}\cdots s_k for some i\leq k.

We could replace the generator s with a reflection t and remove the reduced and possible equality to obtain the Strong Exchange Property.

Proposition 3.  The strong exchange property holds in a Coxeter group.

Deletion Property.  Let g=s_1\cdots s_k and \ell(g)<k, then g=s_1\cdots\hat{s_i}\cdots\hat{s_j}\cdots s_k for 1\leq i<j\leq k.

Theorem 4.  Let (G,S) be a pair with G a group and S a generating set of G such that s^2=1 for all s\in S.  Then the following are equivalent.

  1. G is a Coxeter group.
  2. (G,S) satisfies the exchange property.
  3. (G,S) satisfies the deletion property.

Also worthy of mentioning is the concept of descents.  Let (G,S) be a pair as described above and T be the set of reflections in G.

Definition 5.  Define

T_L(g)=\{t\in T:\ell(tg)<\ell(g)\}

T_R(g)=\{t\in T:\ell(gt)<\ell(g)\}

and then define D_L(g)=T_L(g)\cap S and D_R(g)=T_R(g)\cap S.  The latter two sets are respectively called the left and right descents of g.

My initial terminological intuition is that s\in D_L(g) is a left descent in the sense that the “altitude” relative to g is lower when shifted to s: \ell(sg)<\ell(g).

Now let g=s_1\cdots s_k be reduced.  Then \ell(g)=k.  Moreover left multiples of g that shorten its length must have the form s_1s_2\cdots s_i\cdots s_2s_1 where 1\leq i\leq k.  So T_L(g) are precisely those elements.  There are k such palindrome killers.  So we have |T_L(g)|=\ell(g).The palindrome notion is clear.  The killer part refers to the palindrome killing more letters than it adds–namely killing i letters while adding i-1 letters (hence net kill 1).

Since the inverse of an element is its mirror, it follows that T_L(g)=T_R(g^{-1}) and \ell(g)=\ell(g^{-1}).  We also thus have |T_L(g^{-1})|=\ell(g).  This is easy to see as palindrome killers of the inverse have the form s_ks_{k-1}\cdots s_{k-i}\cdots s_{k-1}s_k with 0\leq i\leq k-1.

[1]  Björner, Anders and Francesco Brenti.  Combinatorics of Coxeter Groups.  Vol. 231.  Graduate Texts in Mathematics.  Springer.  2005.

Metric Construction of Buildings

Let G be a Coxeter group where G is generated by n elements.  Also by \ell(g) for g\in G we mean the minimal length is a product decomposition of g.  Let us first use the book definition.

Definition 1.  A Weyl distance function is a map \delta:C\times C\to G where C a set whose elements are called chambers such that

  1. \delta(x,y)=1\Leftrightarrow x=y;
  2. if \delta(x,y)=g and w\in C such that \delta(w,x)=r_i, then \delta(w,y)\in\{r_ig,g\}.  If we also have that \ell(r_ig)=\ell(g)+1, then \delta(w,y)=r_ig;
  3. if \delta(x,y)=g, then for any i we have a chamber w\in C such that \delta(w,x)=r_i and \delta(w,y)=r_ig.

The pair (C,\delta) is called a W– metric space.  The triple (C,G,\delta) is called a building.

I’m fairly certain I copied correctly (triple checked), but it looks like 3\Rightarrow 2, or the first sentence in 2 at least.  Of importance is the fact we previously mentioned:  that chambers of a Coxeter complex coincide with elements of the Coxeter group (since they are (standard) cosets of the trivial standard subgroup).  If we thus let C=C(G_\Delta), then \delta:G\times G\to G can be thought of as a product on G.  By condition 1, the element 1\in G is thus not an identity with respect to this product.  Also in this regard one can show that the chambers C(G_\Delta) of a Coxeter complex form a building where

d(x,y)=\ell(\delta(x,y))

with d being the gallery metric we previously defined.

Conversely we can say two elements in C are r_i-adjacent if \delta(x,y)=r_i and r_i-equivalent if they are either r_i-adjacent or equal.  If x and y are r_i-equivalent, we write x\sim_{r_i}y.  This is an equivalence relation since

Proposition 2.  \delta(x,y)=\delta(y,x) if one takes a generator value.

Proof.  Suppose \delta(x,y)=r_i.  By part 3 of the definition there is a w\in C such that \delta(w,x)=r_i and \delta(w,y)=r_i^2=1.  Thus by 1 we have w=y and thus

\delta(y,x)=\delta(w,x)=r_i=\delta(x,y).

The equivalence classes under \sim_{r_i} are called r_i-panels.  A panel is an r_i-panel for some i.  Galleries can be defined similarly with this terminology.  Thus (C,G,\delta)=\left(C(G_\Delta),d\right).

[1]  Abramenko, Peter and Kenneth Brown.  Buildings.  Graduate Texts in Mathematics.  Vol. 248.  Springer Science and Business Media.  2008.

Coxeter Complexes

Let G be a Coxeter group with n generators and J be a subset of \{1,...,n\}.  We define the subgroup \langle \{r_i\}_{i\in J}\rangle as the standard subgroup J (i.e. hereafter we abuse notation by using J interchangeably for the subset of indicies as well as the subgroup generated by the corresponding elements of G).  Its cosets will be called standard cosets of J.

Definition 1.  Let g_1H,g_2J be (standard) cosets of standard subgroups H and J.  We define the partial ordering g_1H\leq g_2J\Leftrightarrow g_2J\subseteq g_1H.  If G_\Delta denotes the set of standard cosets in G, then we call (G_\Delta,\leq) the Coxeter complex of G, and will denote it G_\Delta for short.

It’s clear that G_\Delta is a poset since the ordering is merely reverse containment on all cosets.  Elements of G_\Delta will be called simplices, maximal elements will be called chambers.  Since 1 is a standard subgroup with J=\varnothing, it follows that the chambers simply coincide with elements of G.  Also if J is generated by one generator, then it has two elements: J=\{1,r_i\}.  Cosets of such standard subgroups have the form gJ=\{g,gr_i\}, and are called panels.  In the case where g=1, we call 1J=J the fundamental panel of J. Also if g is a chamber and J is generated by a singleton, then gJ is a face of g.  Note that G is the trivial minimal element, but suppose J is generated by n-1 generators of G, then a coset of J is called a vertex.

Every panel is the face of exactly two chambers:  panels have the form \{g,gr_i\}, and are thus faces of g and gr_i.

Recall every element in a Coxeter group has the form

\displaystyle g=\prod_{k=1}^ls_k

where s_k=r_i for some i.  If g is a chamber and we define the chamber g_i=gs_1\cdots s_i, then g_i and g_{i+1} have a panel in common: \{g_i,g_is_{i+1}=g_{i+1}\}.  A gallery is a sequence (g_1,...,g_l) of chambers such that g_i and g_{i+1} have a panel in common.  We can thus define a metric on G

\displaystyle d(x,y)=\min\{l:(x=g_1,...,g_l=y)\mbox{~is a gallery}\}.

This metric can be extended to any simplices, where it is the minimized version of the above taken over all chambers containing those simplices.

Definition 2.  A type function is a map \tau:G_V\to\{1,...,n\} where G_V denotes the vertices in G_\Delta such that it is a bijection on G_V(g)=\{gJ\} for all g where G_V(g) are the n vertices of the chamber g.  The value (or singleton set) \tau(gJ) is called the type of gJ;  we may dually call \{\tau(gJ)\}^C the cotype of gJ.

The standard type function on a Coxeter complex G_\Delta is defined chamber-wise by

\tau(gJ)=S-J,

by which we mean the one element of S-J, as J ranges through \{1,...,n\} (in the sense of which generator it excludes).  Remember we use J both to represent a subset of \{1,...,n\} and to represent the Coxeter subgroup (aka standard subgroup) generated by the elements \{r_i\}_{i\in J}.

We can generalize the type function on the Coxeter complex from vertices to all simplices.  We simply map the simplex to the subset of \{1,...,n\} to which all of its vertices are sent.  Hence chambers get sent to the whole set, and have empty cotype.

Definition 3.  Let gJ be a simplex.  We define its link, denoted lnk(gJ), as the set of all simplices \{g'K\} such that gJ\cap g'K=\varnothing and gJ,g'K have a lower bound.

The link is clearly a subcomplex since if gJ\cap g'K=\varnothing, then gJ\cap S=\varnothing for all subsets S\subseteq g'K.  Thus the facet ordering is still transitive.

Proposition 4.  Let gJ be a simplex.  Then lnk(gJ)=J_\Delta (as posets).

[1]  Abramenko, Peter and Kenneth Brown.  Buildings.  Graduate Texts in Mathematics.  Vol. 248.  Springer Science and Business Media.  2008.