Monthly Archives: September, 2011

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




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.

The Relentless Ingroup Bias

With the termination of the military’s “Don’t Ask Don’t Tell” policy as of yesterday, I am reminded of the fundamental concept at play that delayed this resolution for so long.  This fundamental concept is also at the core of many other issues: gender discrimination, racial discrimination, religious discrimination,…, X discrimination.  This fundamental concept is at the heart of contemporary political partisan bickering, the wealth gap, and wars altogether.  This fundamental concept is the scarcity of resources.  When the set of resources available to a population in insufficient for that population, members of the population will inevitably compete for them.  The ingroup bias has become the catalyst for nonuniform distribution of resources.

The ingroup bias follows from the ingroup instigation.  The heuristic for obtaining resources is cooperative gameplay.  We primitively wish to form alliances with people for the sole purpose of overpowering others (or groups of others) in order to ensure the acquisition of resources.  This is the biologically intrinsic (and evolutionally reinforced) tendency which I call the ingroup instigation.  Given the objective of the ingroup (to work together), the ingroup bias (the tendency to favor individuals in the ingroup and disfavor those in the outgroup) follows.  If we assume this to be true, then the function determining which individuals will group is only governed by what best allows them to overpower other groups or individuals.  By default this starts with proximity and special cases of it such as family (note also how fundamental physical forces operate).  Then, once some groups gather many resources, it may be beneficial for them to team as well.  This can be seen in political alliances, corporate mergers, residential segregation with respect to socioeconomic status (i.e. poor towns or rich towns),…,collisions of galaxies, etc.

It then follows that any minority or group of individuals who have less power become targets of the majority, simply because it is easy to take their resources.  Whether it be a minority based on gender, race, sexual orientation, or religion, the characteristic of a group being a minority–not being in the ingroup of those with the quantitative or qualitative power–becomes sufficient for hindering their progress and in turn targeting their resources.

Hopefully one day we will realize that “potential knowledge” is a good with no scarcity that can in turn be distributed to everyone without limits.  The amount of knowledge in a system will always be finite (but not constant), yet it will also always be an upper bound on usable resources in society (i.e. the amount of consumable resources in the system is dependent upon the amount of knowledge [on how to create such resources from raw resources] in the system at that time).

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




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.