Introduction

The goal of this dissertation is to construct low-dimensional representations of finite Coxeter groups and their associated Hecke algebras, using theory developed by D. Kazhdan and G. Lusztig.

Coxeter groups form a large class of groups, and they include the symmetric and dihedral groups. Finite Coxeter groups are the same thing as finite reflection groups, and they include the Weyl groups associated with semisimple Lie algebras over .

Hecke algebras arise in mathematical nature as endomorphism algebras of induced representations 1_{B}^{G} for groups G with a BN-pair, i.e. groups G with subgroups B and N satisfying certain axioms. Such a G has an associated Coxeter group W. In §1, we study some of the properties of groups with BN-pairs, and eventually derive the multiplication relations of the basis {T_{w} : w ∈ W } of the associated Hecke algebra. The treatment largely follows Carter [1]; further information on Chevalley groups can be found in Carter [2], and another approach to BN-pairs is given in Tits [1].

In §2, we explore further some of the properties of the Hecke algebra, and show how to invert the basis elements T_{w}. We also investigate a particular involution ι of the Hecke algebra. The work in this section is a prelude to the main theorems of §3, and closely follows Humphreys [1], except for the material on isomorphisms between Hecke algebras and group algebras of Weyl groups, which comes from Lusztig [1].

In §3, we prove the uniqueness and existence of another basis for the Hecke algebra, the C-basis. This is manufactured from the T -basis, and has more convenient properties. We also study multiplication formulas between the T -basis and C-basis. This allows us to act the T -basis on the C-basis to obtain modules and representations for the Hecke algebra. The treatment tends to follow Humphreys [1], except Lemmas 3.3 and 3.4 which follow Kazhdan-Lusztig [1]. The details of the last part of the proof of Theorem 3.1 have been supplied by the author.

In §4, we define cells in Coxeter groups. The cells of a particular type partition the group in a way compatible with the theory developed in §3. It turns out that each cell affords a representation of the Hecke algebra, where the dimension of the representation is equal to the number of elements in the cell. By specialising the parameter q in the Hecke algebra to 1, it can be shown that we obtain a representation of the Coxeter group. The example given will be the symmetric group on 4 letters; in this case, we obtain all its irreducible representations over using these methods. The matrix representations were calculated by the author, following the ideas discussed in Humphreys [1].

1: Finite groups with BN-pairs

Groups with a BN-pair

In order to motivate the definition of a Hecke Algebra in §2, we first study some of the properties of groups with a BN-pair. The treatment is based on Carter [1].

Let G be a group. Subgroups B and N of G are said to form a BN-pair if the following axioms are satisfied:

(i) G is generated by B and N.
(ii) B ∩ N is a normal subgroup of N.

We write N/B ∩ N = W, and π : N → W for the canonical epimorphism.

(iii) W is generated by a subset S such that s^{2} = 1 for all s ∈ S.
(iv) Let n_{i} ∈ N satisfy π(n_{i}) = s_{i} ∈ S. Then n_{i}Bn_{i}^{−1} ≠ B.

Because n_{i}^{2} ∈ B ∩ N (since it maps to the identity in W), this is equivalent to n_{i}Bn_{i}^{−1} ≠ B.

(v) n_{i}Bn ⊂ Bn_{i}nB ∪ BnB for all n_{i}, n ∈ N with π(n_{i}) ∈ S.

This is equivalent to Bn_{i}B.BnB ⊂ Bn_{i}nB ∪ BnB

These axioms may appear strange, but they are satisfied by many important groups. It can be shown that GL_{n}(q) satisfies these axioms for suitable choices of B and N, and for q a prime power. Tits [1] explores equivalent ways of defining groups with a BN-pair, and derives some of their basic properties.

It should also be noted that it is possible to prove that W above is a Coxeter group; that is, it is given by generators s_{1}, …, s_{n} of order 2 subject only to relations of the form (s_{i}s_{j})^{m(i,j)} = 1.

Double Cosets

Let G be a group and B a subgroup of G. The subsets of G of the form BgB (g ∈ G) are called the double cosets of G with respect to B. The set of all double cosets of G with respect to B is denoted by B\G/B. We now show that G is partitioned by these sets (although it is not generally true that each double coset has the same size, as in the case of ordinary cosets).

Suppose BgB and Bg′B are two double cosets of G with respect to B. We aim to show that these sets are either identical or disjoint. Suppose they have an element in common, so x ∈ BgB ∩ Bg′B. Then x = bgb′, and BxB = Bbgb′B = BgB. Similarly BxB = Bg′B, so BgB = Bg′B.

The following sequence of results will show that each double coset in a group G (with a BN-pair) with respect to B can be written in the form BnB, and furthermore, BnB = Bn′B ⟺ π(n) = π(n′). From this it is immediate that the number of double cosets equals |W |.

Proposition 1.1 Suppose G has a BN-pair. Then G = BNB. Proof Since B and N are subgroups of G, it is enough to show that BNB is closed under multiplication and inversion. From this, it will follow that G = BNB, because G is generated by B and N.

Inversion is easy: (BNB)^{−1} = B^{−1}N^{−1}B^{−1} = BNB.

Now BNB.BNB = BNBNB. Let nBn′ ∈ NBN, and define w := π(n). Let s_{i_{1}}, …, s_{i_{k}} be elements of S such that s_{i_{1}} ⋯ s_{i_{k}} = w. Choose n_{i_{1}}, ..., n_{i_{k}} ∈ N with π(n_{i_{α}}) = s_{i_{α}}. By multiplying by a suitable element of B ∩ N if necessary, we may assume that n = n_{i_{1}} ⋯ n_{i_{k}}.

n_{i_{k}}BN  ⊂ BNB (using Axiom (v) for BN-pairs)
n_{i_{k−1}}n_{i_{k}}BN ⊂ n_{i_{k−1}}BNB ⊂ BNB.B = BNB
⋮
n_{i_{1}} ⋯ n_{i_{k}}BN ⊂ BNB
Hence nBN ⊂ BNB, NBN ⊂ BNB and BNB.BNB ⊂ BNB, thus proving the claim.

Proposition 1.2 Every double coset of B in G contains an element of N; hence any double coset can be written as BnB for n ∈ N. Proof This follows quickly from Proposition 1.1, because, for any g ∈ G, BgB = Bbnb′B = BnB, for suitable elements b, b′ ∈ B and n ∈ N.

Proposition 1.3 Let n, n′ ∈ N. Then BnB = Bn′B if and only if π(n) = π(n′). Proof One way is easy; if π(n) = π(n′) then n′ = nh for some h ∈ B ∩ N, so Bn′B = BnhB = BnB.

Going the other way, suppose BnB = Bn′B. Let π(n) = w and π(n′) = w′. Each element of W is a product of elements of S. Define the length of w, written as ℓ(w), as the shortest length of any expression of w as a product of s_{i} ∈ S, with the convention that ℓ(1) = 0. Without loss of generality, ℓ(w) ≤ ℓ(w′). We wish to show w = w′. To do this we use the standard technique of induction on ℓ(w).

If ℓ(w) = 0 then w = 1, hence n ∈ B ∩ N and BnB = B, forcing Bn′B = B. So n′ ∈ B ∩ N, and w′ = 1 as desired.

If ℓ(w) > 0, we can write w = s_{i}w′′ where s_{i} ∈ S and ℓ(w′′) = ℓ(w)−1 (the obvious way of arranging this is to let s_{i} be the first element in a reduced expression for w). Choose n_{i}, n′′ ∈ N with π(n_{i}) = s_{i}, π(n′′) = w′′. Then we have

Bn′B = BnB = Bn_{i}n′′B,
n_{i}n′′B ⊂ Bn′B,

n′′B ⊂ n_{i}^{−1}Bn′B = n_{i}Bn′B ⊂ Bn_{i}n′B ∪ Bn′B,
so Bn′′B = Bn_{i}n′B or Bn′B.

We now invoke the inductive hypothesis to show that w′′ = s_{i}w′ or w′′ = w′.

However, ℓ(w′′) = ℓ(w)−1 ≤ ℓ(w′)−1 < ℓ(w′), meaning w′′ ≠ w′. Hence w′′ = s_{i}w′, and w′ = s_{i}w′′ = w, as desired.

Corollary 1.4 Using the above notation, the double cosets of G with respect to B are precisely those of the form BnB as n ranges over a set containing one preimage under π of each element of W.

Axiom (v) for a group with a BN-pair states that n_{i}Bn ⊂ Bn_{i}nB ∪ BnB for n_{i}, n ∈ N and π(n_{i}) ∈ S. Using the notion of length defined earlier, we can obtain more information about the nature of this inclusion, This information will turn out to be important later in motivating the formula for the multiplication of basis elements in the Hecke algebra.

Proposition 1.5 Let w ∈ W, s_{i} ∈ S satisfy ℓ(s_{i}w) ≥ ℓ(w). Let n_{i}, n ∈ N with π(n_{i}) = s_{i}, π(n) = w. Then n_{i}Bn ⊂ Bn_{i}nB. Proof Again, we use induction on ℓ(w). Suppose ℓ(w) = 0, so that w = 1 and n ∈ B and

n_{i}Bn = n_{i}B ⊂ Bn_{i}nB

as required.

Now suppose ℓ(w) > 0, and write w = w′s_{j} with s_{j} ∈ S and ℓ(w′) = ℓ(w) − 1. Let π(n′) = w′. Suppose the result is false, so that

n_{i}Bn ∩ BnB ≠ ∅,
n_{i}Bn′n_{j} ∩ BnB ≠ ∅,
n_{i}Bn′ ∩ BnBn_{j} ≠ ∅.

We now claim that ℓ(s_{i}w′) ≥ ℓ(w′). Otherwise, ℓ(s_{i}w′) < ℓ(w′) = ℓ(w)−1, giving ℓ(s_{i}w) ≤ ℓ(s_{i}w′)+1 ≤ ℓ(w) − 1, contrary to assumption.

Thus, by induction, n_{i}Bn′ ⊂ Bn_{i}nB, and hence Bn_{i}n′B ∩ BnBn_{j} ≠ ∅.

Axiom (v) shows that nBn_{j} ⊂ Bnn_{j}B ∪ BnB, so Bn_{i}n′B intersects either Bnn_{j}B or BnB, and, using Proposition 1.3, we see that either s_{i}w′ = ws_{j} or s_{i}w′ = w. The former possibility implies s_{i} = 1 (a contradiction to n_{i}Bn_{i}^{−1} ≠ B) so we must have s_{i}w′ = w, and hence s_{i}w = w′, so ℓ(s_{i}w) < ℓ(w), a contradiction, thus establishing the result.

An idempotent in the group algebra

We now consider a finite group G with a BN-pair and study some of the properties of a particular idempotent e in the group algebra of G. The group algebra, G, of G is, for our purposes, a -vector space with the elements of the group as basis elements, together with a bilinear multiplication which, when restricted to the elements of the group, gives the multiplication in the group. The idempotent e is defined by

e = \frac{1}{|B|} ∑_{b∈B} b.

(It is clear that e is idempotent, i.e. e^{2} = e, from the fact that B is a subgroup of G.)

We will study further properties of e later, but for now it should suffice to say that the elements ene (where n ∈ N) are closely related to a set of basis elements in the Hecke algebra (which may be thought of as a deformed version of W, where W is the associated Weyl group). Studying how these elements ene multiply together will provide insight into the behaviour of the Hecke algebra.

Proposition 1.6 Suppose ℓ(s_{i}w) = ℓ(w) + 1. Then

en_{i}e.ene = en_{i}ne,

where n ∈ N and π(n) = w. Proof

en_{i}e.ene = en_{i}ene = \frac{1}{|B|} ∑_{b∈B} en_{i}bne

Now, using Proposition 1.5, we have that n_{i}bn ∈ Bn_{i}nB. Hence e(n_{i}bn)e = en_{i}ne for each b ∈ B. Hence

en_{i}e.ene = \frac{1}{|B|} ∑_{b∈B} en_{i}ne = en_{i}ne.

We are also interested in the case where ℓ(s_{i}w) = ℓ(w) − 1. (It is an easily-proved fact that, in Coxeter groups, ℓ(s_{i}w) = ℓ(w) ± 1.) It will turn out that once we know the value of en_{i}e.en_{i}e, the properties we require will be easily deducible.

Proposition 1.7 Let q_{i} := |B : n_{i}Bn_{i}^{−1} ∩ B|. Then

en_{i}e.en_{i}e = \frac{1}{q_{i}} e + \frac{q_{i} − 1}{q_{i}}en_{i}e.

Proof From the axioms, we know n_{i}Bn_{i} ⊂ B∪Bn_{i}B. We also have that |n_{i}Bn_{i}| = |B| and |n_{i}Bn_{i}∩B| = \frac{1}{q_{i}} |B|. By an elementary counting argument, we obtain

|n_{i}Bn_{i} ∩ Bn_{i}B| = |B| − \frac{|B|}{q_{i}} = \frac{1}{q_{i}} (q_{i} − 1)|B|.

Now

en_{i}e.en_{i}e = en_{i}en_{i}e

= e (\frac{1}{|B|} ∑_{b∈B} n_{i}bn_{i}) e

= \frac{1}{|B|} ∑_{b∈B} e(n_{i}bn_{i})e

= \frac{1}{|B|} (\frac{1}{q_{i}} |B|e + \frac{1}{q_{i}} (q_{i} − 1)|B|en_{i}e)

= \frac{1}{q_{i}} e + \frac{1}{q_{i}} (q_{i} − 1)en_{i}e.

In the case of GL_{n}(q), all the q_{i} are equal to q. This is also the case in many other interesting and important groups, such as the finite Chevalley groups arising from the simple Lie algebras over (see Carter [2] for further details in this area). We now give an outline proof that G = GL_{n}(q) has a BN-pair.

Lemma 1.8 The group G = GL_{n}(q), where q is a prime power, has a BN-pair satisfying

|B : n_{i}Bn_{i}^{−1}| = q

for all i. Proof Let k denote the field with q elements. Denote by B the subgroup of G consisting of upper triangular matrices. Let N denote the subgroup of monomial matrices, i.e. those with nonzero entries only in positions (i, σ(i)) for some permutation σ. Let H denote the subgroup of G consisting of the diagonal matrices. Note that mapping an element of N to the associated permutation gives a surjective homomorphism π : N → S_{n}. The kernel is H = B ∩ N, so W ≅ S_{n} here. For each permutation (i, i + 1), define an element n_{i} ∈ N mapping to it under π.

We now tackle axiom (i). Choose an element g ∈ GL_{n}(q). Left multiplication by an element of B transforms a given row to a non-zero multiple of itself plus a linear combination of later rows. Hence we can find b ∈ B such that the first non-zero elements in the rows of bg occur in different columns. Right multiplication by elements of B transforms a given column to itself plus a linear combination of earlier columns. It is now possible to find b′ ∈ B such that bgb′ is a monomial matrix. It follows that BNB = G, and hence B and N generate G.

Denote by U the unitriangular subgroup of G consisting of those elements of B with b_{i,i} = 1 for all i. Let U_{i} denote the matrices (a_{i,j}) ∈ U such that a_{i,i+1} = 0. Let e_{i,j} denote the matrix with 1 in (i, j) position and 0 elsewhere. Let X_{i,j} denote the set {I + λe_{i,j}; λ ∈ k} for i ≠ j, where I is the identity matrix. Furthermore, let X_{i} denote X_{i,i+1} and X_{−i} denote X_{i+1,i}. It is easy to show that U B, B = UH = HU, U ∩ H = 1, U = X_{i}U_{i} = U_{i}X_{i}, U_{i} ∩ X_{i} = 1, n_{i}X_{i}n_{i}^{−1} = X_{−i}, and n_{i}U_{i}n_{i}^{−1} = U_{i}. This is enough to prove that n_{i}Bn_{i}^{−1} ≠ B, and that |B : B ∩ n_{i}Bn_{i}^{−1}| = q, thus proving q_{i} = q for all i.

It remains to verify axiom (v). We have

n_{i}Bn = n_{i}HUn = n_{i}Hn_{i}^{−1}n_{i}Un = Hn_{i}U_{i}X_{i}n = HU_{i}n_{i}X_{i}n ⊂ Bn_{i}X_{i}n.

Let π(n) = σ ∈ S_{n}. Then n^{−1}X_{i,j}n = X_{iσ,jσ}. So

n_{i}X_{i}n = n_{i}nn^{−1}X_{i}n = n_{i}nn^{−1}X_{i,i+1}n = n_{i}nX_{iσ,(i+1)σ}.

Case 1: Suppose iσ < (i + 1)σ. Then X_{iσ,(i+1)σ} ⊂ B, so n_{i}X_{i}n ⊂ n_{i}nB, and n_{i}Bn ⊂ Bn_{i}nB. Case 2: Suppose iσ > (i + 1)σ. Write n′ = n_{i}n, where π(n′) = σ′. Then iσ′ < (i + 1)σ′, and

n_{i}X_{i}n = n_{i}X_{i}n_{i}^{−1}n′ = X_{−i}n′.

Write

( \begin{matrix}1 \\ & . & . & . \\ & & & & a & b \\ & & & & c & d \\ & & & & & & 1 \\ & & & & & & & . & . & . \\ & & & & & & & & & & 1 \end{matrix} ) as [ \begin{matrix}a & b \\ c & d \end{matrix} ]

for short, where a occurs in the (i, i) position.

We have

[ \begin{matrix}1 & 0 \\ λ & 1 \end{matrix} ] = [ \begin{matrix}1 & λ^{−1} \\ 0 & 1 \end{matrix} ] [ \begin{matrix}−λ^{−1} & 0 \\ 0 & λ \end{matrix} ] [ \begin{matrix}0 & 1 \\ 1 & 0 \end{matrix} ] [ \begin{matrix}1 & λ^{−1} \\ 0 & 1 \end{matrix} ]

if λ ≠ 0.

This lies in UHn_{i}U ⊂ Bn_{i}B, so X_{−i} ⊂ B ∪ Bn_{i}B and X_{−i}n′ ⊂ Bn′ ∪ Bn_{i}Bn′. Now iσ′ < (i + 1)σ′, so, by Case 1,

n_{i}Bn′ ⊂ Bn_{i}n′B.

Hence X_{−i}n′ ⊂ Bn′B ∪ Bn_{i}n′B, giving

n_{i}Bn ⊂ Bn_{i}X_{i}n ⊂ BX_{−i}n′ ⊂ Bn′B ∪ Bn_{i}n′B

and

n_{i}Bn ⊂ Bn_{i}nB ∪ BnB,

as required.

Induced Modules, the Hecke Algebra and their relationship to the Weyl Group

We now continue our study of a typical finite group G with a BN-pair, and corresponding Weyl group W. The aim is to define, and work out the basic properties of, the Hecke algebra of G with respect to B. It is clear that e is a 1-dimensional left B-module affording the trivial representation of B. The idempotent e (as defined earlier), generates a G-submodule of G, denoted by V (= Ge).

A -linear map θ : V → V is called a G-endomorphism (also a homomorphism of representations or an intertwining operator) if it has the additional property that θ(gv) = g(θv) for all g ∈ G and v ∈ V. The G endomorphisms have a natural algebra structure (pointwise addition and composition of maps as the multiplication), and this algebra is known as the Hecke algebra of G with respect to B. It is denoted by H = End_{G} V.

It is also instructive to study the properties of the subalgebra e Ge of the group algebra, because it turns out to be isomorphic to H. This is why the elements ene were introduced earlier, and this also provides the motivation for the multiplication relations in the Hecke algebra, which will be introduced later.

Proposition 1.9 dimA = |B\G/B|. Proof Let x_{1}, …, x_{s} be double coset representatives of G with respect to B. Then the elements ege (g ∈ G), span A. Writing g = bx_{i}b′, we get ege = ebx_{i}b′e = ex_{i}e. Thus A is spanned by elements ex_{i}e. It remains to show these are linearly independent. Suppose ∑_{i} λ_{i}ex_{i}e = 0. Then

\frac{1}{|B|^{2}} ∑_{b} ∑_{b′} ∑_{i} λ_{i}bx_{i}b′ = 0.

Also,

bx_{i}b′ = \overline{b}x_{i}\overline{b}′ ⟺ x_{i}^{−1}\overline{b}^{−1}bx_{i} = \overline{b}′b^{′−1}.

In this case, \overline{b}′ ∈ (B ∩ x_{i}^{−1}Bx_{i})b′. Conversely, for each \overline{b}′ ∈ (B ∩ x_{i}^{−1}Bx_{i})b′, there is a unique \overline{b} such that x_{i}^{−1}\overline{b}^{−1}bx_{i} = \overline{b}′b^{′−1}. (Note that we are regarding b and b′ as fixed.) Thus each bx_{i}b′ occurs |B ∩ x_{i}^{−1}Bx_{i}| times in the above sum. The coefficient of bx_{i}b′ is

\frac{1}{|B|^{2}} λ_{i}|B ∩ x_{i}^{−1}Bx_{i}|.

This must be 0, so λ_{i} = 0 and the elements are indeed linearly independent, thus establishing the proposition.

Proposition 1.10 A is anti-isomorphic to H. Proof Firstly, if v ∈ V and a ∈ A, then va ∈ V. (This is immediate from the definitions of V and A, and the fact that e ∈ V.) Denote the map v → va by ρ_{a}. It is clear that ρ_{a} ∈ H, because g(ρ_{a}v) = gva = ρ_{a} (gv).

We now show that the map a → ρ_{a} is a bijection from A to H. Suppose ρ_{a}v = ρ_{b}v for all v ∈ V. Then in particular ρ_{a}e = ρ_{b}e, and ea = eb. Hence, since a, b ∈ A and e is idempotent, we get a = b. Thus the map is injective.

Suppose θ ∈ H. Let θ(e) = a ∈ V. Now, eθ(e) = θ(ee) = θ(e), hence ea = a and a ∈ A. Now we show that θ = ρ_{a}. Let v ∈ V, so ve = v. We have θ(v) = θ(ve) = v(θe) = va. Thus θ = ρ_{a} and the map is surjective.

Finally,

ρ_{ab}v = vab = ρ_{b}(va) = ρ_{b}ρ_{a}v.

Hence ρ_{ab} = ρ_{b}ρ_{a} and the proposition is proved.

Proposition 1.11 There is an anti-isomorphism between A and itself. Thus, from Proposition 1.10, we have that A is isomorphic to H. Proof Define a map ι : G → G by ι(g) = g^{−1}. This is an anti-isomorphism of the group, and extends linearly to an anti-isomorphism of the group algebra. Furthermore,

ι(e) = ι (\frac{1}{|B|^{2}} ∑_{b∈B} b) = \frac{1}{|B|} ∑_{b∈B} b^{−1} = e.

Let x ∈ G. Then ι(exe) = ι(e)ι(x)ι(e) = eι(x)e. So ι : A → A is an anti-isomorphism of A to itself. Combining this with the anti-isomorphism in Proposition 1.10, we get the desired isomorphism between A and H.

Finally, we are ready to show how the bilinear multiplication works on a basis of the Hecke algebra. It is a consequence of Corollary 1.4 that the elements q^{ℓ(w)}ene , where π(n) = w ∈ W, are linearly independent, and, thanks to Proposition 1.9, that they are a basis for A. We now choose an isomorphism ϕ between A and H, and define a basis T_{w} for H by

T_{w} := ϕ(q^{ℓ(w)}ene).

This is a basis for H. At the moment, we have in mind that q is an integer depending on the group G we are studying, but we shall be intentionally vague about this, because later, the same q will serve as a parameter.

We now want to find out how these basis elements multiply together. This is easy following the results of Propositions 1.6 and 1.7.

Proposition 1.12

a) If ℓ(s_{i}w) = ℓ(w) + 1, then

T_{s_{i}}T_{w} = T_{s_{i}w}.

b) If ℓ(s_{i}w) = ℓ(w) − 1, then

T_{s_{i}}T_{w} = qT_{s_{i}w} + (q − 1)T_{w}.

Proof

a) ℓ(s_{i}) = 1. By Proposition 1.6 we have

qen_{i}e.q^{ℓ(w)}ene = q^{ℓ(w)+1}en_{i}e.ene = q^{ℓ(s_{i}w)}en_{i}ne.

b) Write w = s_{i}w′, so that ℓ(s_{i}w′) = ℓ(w′) + 1. Using Proposition 1.7, we have that

qen_{i}e.qen_{i}e = q(e) + (q − 1)(qen_{i}e),

thus

T_{s_{i}}T_{s_{i}}T_{w′} = qT_{1}T_{w′} + (q − 1)T_{s_{i}}T_{w′}.

Using Case (a), we obtain

T_{s_{i}}T_{w} = qT_{s_{i}w} + (q − 1)T_{w}.

These results suffice to define the multiplication between any two basis elements (since the T_{s_{i}} generate H as an algebra), and thus the entire algebra structure is determined in terms of this basis.

2: Hecke Algebras

Encouraged by the results of §1, we now define the Hecke algebra H of a Coxeter group W. First, we attempt to define an algebra H̃ over the polynomial ring [q], which has basis elements T_{w} parametrised by w ∈ W, and the following multiplication rules:

T_{s}T_{w} = \{ \begin{matrix}T_{sw} & if ℓ(sw) > ℓ(w), \\ qT_{sw} + (q − 1)T_{w} & if ℓ(sw) < ℓ(w). \end{matrix}

The existence of an algebra structure is not immediately clear, but can be checked.

We also define a ring A := [q, q^{−1}], although later we shall want to extend this somewhat.

From this, we construct the Hecke algebra of W, as follows:

H := H̃ ⊗_{[q]} [q^{\frac{1}{2}} , q^{− \frac{1}{2}} ].

The reasons for choosing [q^{\frac{1}{2}} , q^{− \frac{1}{2}} ] above will eventually become clear. (Put simply, it is convenient to have a square root of q in the ring to set up a certain isomorphism, and it will be necessary to be able to invert q in order to invert the elements T_{w}).

It should be observed that the elements T_{s} corresponding to the generating involutions of the W generate H̃ as a [q]-algebra. To see this, choose w ∈ W and write w = s_{i_{1}} ⋯ s_{i_{r}} as a reduced expression (i.e. one of minimal length). It is then clear from the multiplication relations above that T_{w} = T_{s_{i_{1}}} ⋯ T_{s_{ir}}.

I now claim that all the basis elements T_{w} are invertible in H. The above remarks show that it suffices to be able to invert the elements T_{s} where s is a generating involution of W. This turns out to be easy, since

T_{s}^{2} = (q − 1)T_{s} + qT_{1},

hence

T_{s}^{−1} = q^{−1}T_{s} − (1 − q^{−1})T_{1}.

(Of course, this works because T_{1} acts as a multiplicative identity in H.)

The motivation for studying the inverses of these basis elements will become clear when we study the Cbasis of H in §3. The inverses play a crucial role in establishing the existence and uniqueness of the C-basis, which has some interesting properties that make it a good object to study in our quest for representations of H.

Hecke Algebras and Group Algebras

Consider the algebra multiplication relations presented above, but with q specialised to 1. Notice that we obtain the first relation in both cases, thus recovering the relations of the group algebra of the Coxeter group W. Thus, if we specialise q → 1 in a representation of the Hecke algebra, we will obtain a representation of the Coxeter group.

We can go some way towards finding a converse to this specialisation process. Iwahori conjectured that the Hecke algebra of W (over instead of this time, and interpreting q as the number of elements in a finite field) was isomorphic to the group algebra of W, in the case where W was a Weyl group. (“Most” finite Coxeter groups with irreducible systems of generating involutions are Weyl groups, the exceptions being types H_{3}, H_{4}, and the dihedral groups excluding those of orders 2, 4, 6, 8 and 12.) Benson and Curtis showed that this conjecture is not quite true; it works for all the cases except types E_{7} and E_{8}, but, provided we are willing to introduce a square root of q into the relevant field, it works in these cases too. For this reason, we will eventually want to redefine the ring A to be [q^{\frac{1}{2}} , q^{− \frac{1}{2}} ].

Lusztig [1] constructs an explicit isomorphism between the Hecke algebra over (q^{\frac{1}{2}} ) and the group algebra over (q^{\frac{1}{2}} ) of the Weyl group, using the Kazhdan-Lusztig polynomials, which will be introduced later in this dissertation. The upshot of all this is that, over , and for a (non-zero) complex value of q, the Hecke algebra is isomorphic to the group algebra, so by understanding the representations of the former, we can find representations of the latter, and vice versa.

Example (Lusztig)

Let W be a Weyl group of type A_{2} given by generators s_{1} and s_{2} of order 2 such that s_{1}s_{2} has order 3, and let Φ be the isomorphism from H to the group algebra mentioned above. Then:

\begin{aligned}Φ(T_{s_{1}}) & = \frac{q + 1}{2}s_{1} + \frac{q − 1}{2} + \frac{(\sqrt{q} − 1)^{2}}{6} × (−s_{2} + s_{1}s_{2} − s_{2}s_{1} + s_{1}s_{2}s_{1}), \\ Φ(T_{s_{2}}) & = \frac{q + 1}{2}s_{2} + \frac{q − 1}{2} + \frac{(\sqrt{q} − 1)^{2}}{6} × (−s_{1} + s_{2}s_{1} − s_{1}s_{2} + s_{2}s_{1}s_{2}). \end{aligned}

Note the symmetry above between 1 and 2 (corresponding to an automorphism of the Dynkin diagram).

Inverses and the Bruhat order

We now turn our attention to working out the inverse of T_{w} for arbitrary w. To do this efficiently, it is convenient to introduce a family of polynomials known as the R-polynomials. First, however, we state without proof some of the properties of the Bruhat order which is a natural partial order on a Coxeter group W.

Let W be an arbitrary Coxeter group, and w an element of W. The Bruhat order can be characterised as follows, although it is difficult to prove it is a well-defined partial order on the group from this starting point. Let s_{i_{1}} ⋯ s_{i_{l}} be a (fixed) reduced expression for w. The elements x in the group satisfying x ≤ w are exactly those of the form s_{j_{1}} ⋯ s_{j_{m}} where (j_{1}, …, j_{m}) is an (ordered) subsequence of (i_{1}, …, i_{l}). The symbols “<”, “>”, “≤” and “≥” will henceforth be used in conjunction with this order in the obvious way. It will turn out that the Bruhat order will be forced on us by the way inversion works in H. The following lemma will be used in the proof of the main theorem of this section below.

Lemma 2.1 Let s be a generating involution of a Coxeter group W and w ∈ W such that sw < w. Suppose x < w. Then:

(a) If sx < x, then sx < sw.

(b) If sx > x, then sx ≤ w and x ≤ sw.

Thus, in either case, sx ≤ w. Proof It is a standard fact from the theory of Coxeter groups (in fact, a corollary of the Exchange Condition) that if ℓ(sw) < ℓ(w) for a generating involution s ∈ W and an element w ∈ W, then w has a reduced expression beginning with s. We know that x can be represented by a subexpression of w. Thus, either x is a subexpression of sw or else a reduced expression for x begins with s, forcing sx to be a subexpression of the (reduced) expression sw (which is the same as the original reduced expression for w without the first letter). In this case, sx ≤ sw. The properties (a) and (b) follow immediately, (b) corresponding to the first case and (a) to the second.

Theorem 2.2 For all w ∈ W,

(T_{w^{−1}})^{−1} = ε_{w}q_{w}^{−1} ∑_{x≤w} ε_{x}R_{x,w}(q)T_{x},

where ε_{x} := (−1)^{ℓ(x)}, q_{x} := q^{ℓ(x)}, R_{x,w}(q) ∈ [q] is a polynomial of degree ℓ(w) − ℓ(x) in q, and R_{w,w}(q) = 1.

Proof The treatment follows Humphreys [1].

The proposition is clear when w = 1, and also when s = w is of length 1, setting R_{1,s} := q − 1, because we know what T_{s^{−1}}^{−1} is. The proof will be by induction on ℓ(w). We are also interested in finding an algorithm to compute the R-polynomials. In the case x ≰ w, we define R_{x,w} to be 0.

Now assume ℓ(w) > 0, and write w = sv for some s of length 1, such that ℓ(v) < ℓ(w), giving ε_{w} = −ε_{v} and q_{w} = q_{v}q. Using the inductive hypothesis, we now have:

(T_{w^{−1}})^{−1} = (T_{v^{−1}}T_{s})^{−1}
= T_{s}^{−1}(T_{v^{−1}})^{−1}

= q^{−1}(T_{s} − (q − 1)T_{1}) (ε_{v}q_{v}^{−1} ∑_{y≤v} ε_{y}R_{y,v}T_{y})

= ε_{w}q_{w}^{−1} [(q − 1) ∑_{y≤v} ε_{y}R_{y,v}T_{y} − ∑_{y≤v} ε_{y}R_{y,v}T_{s}T_{y}] .  (1)

The second sum in (1) involves two sorts of terms, according as sy > y or sy < y. In the former case, we get simply ε_{y}R_{y,v}T_{sy}. In the latter case, we get instead

(q − 1)ε_{y}R_{y,v}T_{y} + qε_{y}R_{y,v}T_{sy},

the first term of which cancels with a term in the first half of (1). Thus (1) can be rewritten as the sum of 3 different kinds of terms:

y ≤ v, y < sy  (q − 1)ε_{y}R_{y,v}T_{y},  (2)
y ≤ v, y < sy  − ε_{y}R_{y,v}T_{sy},  (3)
y ≤ v, y > sy  − qε_{y}R_{y,v}T_{sy}.  (4)

Since y < w in each case, we can invoke Lemma 2.1, with y in the role of x. Hence sy ≤ w. From the subexpression characterisation of the Bruhat ordering, it is clear that any element of the form x ≤ w is expressible as y such that y ≤ v or as sy such that y ≤ v, or possibly both. It is now enough to compare coefficients of T_{x} to establish the theorem.

Suppose first that x ≤ w with x > sx, implying that ℓ(sx) = ℓ(x) − 1. Here, T_{x} cannot occur as in case (2) because x > sx, and similarly it cannot occur as in case (4). In this case, T_{x} does occur in a term of type (3), because, writing x = sy, we have x > sx ⇒ y < sy, and also y ≤ v, for otherwise y would have to have a reduced expression beginning with s, contrary to y < sy. (This fact follows from the Deletion Condition for Coxeter groups, a corollary of which is that any given expression for an element of the group has a subexpression which is a reduced expression for the same element.) The coefficient of T_{x} is now clear from case (3), and it is −ε_{y}R_{y,v}, or equivalently ε_{x}R_{sx,sw}. Since ℓ(sw) < ℓ(w), we know the degree of this to be ℓ(sw) − ℓ(sx), i.e. ℓ(w) − ℓ(x). In particular, if x = w, we have y = v and R_{v,v} = 1 by induction. Thus R_{x,w} has the required properties.

The other case is when x < w and x < sx, implying ℓ(sx) = ℓ(x) + 1. There are two subcases to consider.

(a) If sx < v, we obtain both x < sx < v and sx ≤ v, so it is immediate that T_{x} occurs as a term of type (2) and as a term of type (4). The combined coefficient is

(q − 1)ε_{x}R_{x,v} − qε_{sx}R_{sx,v}.

By induction,

deg qR_{sx,v} = ℓ(v) − ℓ(sx) + 1 = (ℓ(w) − 1) − (ℓ(x) + 1) + 1 = ℓ(w) − ℓ(x) − 1,

whereas

deg(q − 1)R_{x,v} = ℓ(v) − ℓ(x) + 1 = (ℓ(w) − 1) − ℓ(x) + 1 = ℓ(w) − ℓ(x).

Thus the combined coefficient has degree ℓ(w) − ℓ(x) as required, and

R_{x,w} := (q − 1)R_{x,sw} + qR_{sx,sw}.

(b) In the other subcase, sx ≰ v, and T_{x} occurs as in a term of type (2) but not as a term of type (4) as before. The coefficient is thus ε_{x}(q−1)R_{x,v}. Since, by convention, R_{sx,v} = 0 in this case, the above definition of R_{x,w} works equally well.

Computing the R-polynomials

This is now easy given the work done in the proof of Theorem 2.2. To compute R_{x,w}, we use induction on ℓ(w). We also know that R_{w,w} = 1 for all w ∈ W, and R_{x,w} = 0 unless x ≤ w. We have to compute R_{x,w}, assuming that R_{y,z} are all known for ℓ(z) < ℓ(w). Fix a generating involution s such that sw < w. There are two cases, according as x < sx or x > sx, and Lemma 2.1 is now applicable. A: x < w, sx < x, hence, by 2.1, sx < sw. The proof of 2.2 now demonstrates that R_{x,w} = R_{sx,sw}, which

is known since sw < w. B: x < w, x < sx, hence, by 2.1, sx ≤ w and x ≤ sw. The proof of 2.2 now gives

R_{x,w} = (q − 1)R_{x,sw} + qR_{sx,sw},

both terms of which are known by induction.

It is also possible to have alternate versions of the above two equations, with s occurring on the right instead of the left. This is entirely straightforward.

An involution on H

In this section, we define and investigate ι, which is a ring homomorphism from H to H of order 2. The action of ι on A is -linear, and sends q^{c} to q^{−c} for any c. (I use this definition for forward compatibility with the extended version of A later.) The effect of ι on T_{w} is to send it to (T_{w^{−1}})^{−1}. (Note that there are three levels of inversion going on here!) The effect on the whole of H extends additively. Proposition 2.3

The operation ι is a ring homomorphism whose square is the identity on H.

Proof It is easy to check that ι^{2}(T_{s}) = T_{s}:

ι^{2}(T_{s}) = ι((T_{s})^{−1})
= ι(q^{−1}T_{s} − (1 − q^{−1})T_{1})
= q(T_{s})^{−1} − (1 − q)T_{1}
= q(q^{−1}T_{s} − (1 − q^{−1})T_{1}) − (1 − q)T_{1}
= T_{s} − (q − 1)T_{1} − (1 − q)T_{1}
= T_{s}.

It follows that if we can establish ι to be a ring homomorphism, then ι^{2} will be the identity on the whole of H, since ι^{2} fixes A, and the T_{s} generate H as an algebra. The first step in this is:

ι(T_{s}T_{w}) = ι(T_{s})ι(T_{w})  (5)

for a generating involution s and a general element w ∈ W.

If ℓ(sw) > ℓ(w), then we have simply

ι(T_{s}T_{w}) = ι(T_{sw}) = (T_{w^{−1}s}^{−1}) = T_{s}^{−1}(T_{w^{−1}})^{−1} = ι(T_{s})ι(T_{w}).

If, on the other hand, ℓ(sw) < ℓ(w), write v = (sw)^{−1}, so w^{−1} = vs. Now

ι(T_{s}T_{w}) = ι(qT_{sw} + (q − 1)T_{w}) = q^{−1}T_{v}^{−1} + (q^{−1} − 1)(T_{w^{−1}})^{−1}.

Note that q^{−1} − 1 = −q^{−1}(q − 1), and T_{w^{−1}} = T_{vs} = T_{v}T_{s} has inverse T_{s}^{−1}T_{v}^{−1}. Using the expression calculated earlier for T_{s}^{−1}, we get

ι(T_{s}T_{w}) = q^{−2}(q^{2} − q + 1)T_{v}^{−1} − (q − 1)q^{−2}T_{s}T_{v}^{−1}.

Also

ι(T_{s})ι(T_{w}) = T_{s}^{−1}(T_{w^{−1}})^{−1} = (T_{s})^{−2}T_{v}^{−1}.

Substituting T_{s}^{−1} and then substituting T_{s}^{2} = (q − 1)T_{s} + qT_{1}, (5) can be verified.

It is then easy to prove by induction on ℓ(w′) that

ι(T_{w′}T_{w}) = ι(T_{w′})ι(T_{w})

for all w, w′ ∈ W, proceeding as follows.

If ℓ(w′) > 1, find a generating involution s such that ℓ(w′s) < ℓ(w′). Then ι(T_{w′}T_{w}) = ι(T_{w′s})ι(T_{s}T_{w}) by induction (think of T_{s}T_{w} as an A-linear sum of basis elements T_{v}). Using (5), we get

ι(T_{w′s})ι(T_{s})ι(T_{w}) = ι(T_{w′s}T_{s})ι(T_{w}) = ι(T_{w′})ι(T_{w}),

as required.

3: Kazhdan-Lusztig polynomials

The C-basis

In this section, we construct a new basis of H with some convenient properties, including invariance under the map ι constructed in §2. This basis plays a crucial part in the construction of relatively lowdimensional representations of H arising from the structure of the underlying Coxeter group W.

Defining the C-basis from the T -basis will simultaneously define a family of polynomials (the Kazhdan-Lusztig polynomials) denoted by P_{x,w} for x, w ∈ W, reminiscent of the R-polynomials but subtler. They have applications in other areas, such as algebraic geometry, where they are closely connected with the structure of singularities of Schubert varieties. It is conjectured by Kazhdan and Lusztig that all the coefficients of the P_{x,w} are positive.

The treatment of the proofs of uniqueness and existence of the C-basis in Kazhdan-Lusztig [1] is shorter than the one offered here, but it does not attempt to motivate the inductive calculating formula for the Kazhdan-Lusztig polynomials. The proofs given here will be more constructive and will follow the outline of Humphreys [1], but with some of the gaps filled in.

The symbols W and H retain their usual meaning. We will also use a bar above an expression to denote the result of operating by ι, analogous to the use of the bar representing conjugation of complex numbers. We will also find it very convenient to introduce a square root of q to the ring A of §2. From now on, A will denote the extended ring [q^{\frac{1}{2}} , q^{− \frac{1}{2}} ].

Theorem 3.1

For each w ∈ W there exists a unique element C_{w} ∈ H having the following two properties: (a)

ι(C_{w}) = C_{w},

(b)

C_{w} = ε_{w}qw^{\frac{1}{2}} ∑_{x≤w} ε_{x}q_{x}^{−1}\overline{P}_{x,w}T_{x},

where P_{w,w} = 1 and P_{x,w}(q) ∈ [q] has degree ≤ \frac{1}{2}(ℓ(w) − ℓ(x) − 1) if x < w. Proof The proof is somewhat lengthy. We will tackle uniqueness first, which is the easier part, and then a proof of existence will be given, which at the same time constructs the Kazhdan-Lusztig polynomials. We will be particularly interested in the case where the degree bound on the polynomials is attained; this is only possible if ℓ(w) and ℓ(x) have different parities. In the case where P_{x,w} has the maximum allowable degree, we write x ≺ w. In the case where x ≰ w, we define P_{x,w} := 0, as in the case of the R-polynomials in §2. The expression μ(x, w) will denote the coefficient of the highest power of q occurring in P_{x,w}. Uniqueness For an arbitrary, but fixed w ∈ W, we prove the uniqueness of

C_{w} = a(x, w) ∑_{x≤w} \overline{P}_{x,w}T_{x}, where a(x, w) := ε_{w}ε_{x}qw^{\frac{1}{2}}q_{x}^{−1},  (1)

assuming that C_{w} has the properties (a) and (b) of the theorem. This reduces to showing that the polynomials P_{x,w} can only be chosen in one way. We proceed by induction on n := ℓ(w) − ℓ(x), the case n = 0 having been settled by hypothesis. We then assume P_{y,w} are all uniquely determined where x < y ≤ w, and show this forces the choice of P_{x,w}.

Start with formula (1), write y in place of x and apply ι to it (which requires the use of the inversion formula for T_{w} in §2). This process leaves the formula invariant by the hypothesis (a). This quickly gives

a(x, w) ε_{w}q_{w}^{− \frac{1}{2}} ∑_{x≤y≤w} ε_{x}R_{x,y}P_{y,w}T_{x}.

By equating coefficients of T_{x} with the original coefficient in C_{w} we obtain:

ε_{w}qw^{\frac{1}{2}}ε_{x}q_{x}^{−1}\overline{P}_{x,w} = ε_{w}q_{w}^{− \frac{1}{2}} ∑_{x≤y≤w} ε_{x}R_{x,y}P_{y,w}.

Cancelling the signs and multiplying both sides by qx^{\frac{1}{2}} yields:

qw^{\frac{1}{2}}q_{x}^{− \frac{1}{2}} \overline{P}_{x,w} = q_{w}^{− \frac{1}{2}} qx^{\frac{1}{2}} ∑_{x≤y≤w} R_{x,y}P_{y,w}.

Now we move the term for y = x from the right to the left, using the fact that R_{x,x} = 1:

qw^{\frac{1}{2}}q_{x}^{− \frac{1}{2}} \overline{P}_{x,w} − q_{w}^{− \frac{1}{2}} qx^{\frac{1}{2}} P_{x,w} = q_{w}^{− \frac{1}{2}} qx^{\frac{1}{2}} ∑_{x<y≤w} R_{x,y}P_{y,w}.  (2)

We assume by induction that all the P_{y,w}(x < y ≤ w) are uniquely determined, and argue that P_{x,w} is uniquely determined. Since x < w (hence ℓ(x) < ℓ(w)), it is clear that the first term is a polynomial in q^{\frac{1}{2}} (recall the degree bounds on P_{x,w}), and for similar reasons, the second term is a polynomial in q^{− \frac{1}{2}} with no constant term. There is thus no cancellation between the two terms, and P_{x,w} is uniquely determined. Existence This will be trickier than the uniqueness above. The idea will be to prove the existence of C_{w} by induction on n := ℓ(w). We will dispose of the cases n = 0 and n = 1 directly. It is easy to check that C_{1} = T_{1} does the job for n = 0. To get inspiration for C_{s}, we recall the inversion formula for T_{s}:

T_{s}^{−1} = q^{−1}T_{s} − (1 − q^{−1})T_{1}.

Applying ι to this, we find that ι sends T_{s} − qT_{1} to q^{−1}(T_{s} − qT_{1}). Multiplying the first expression by q^{− \frac{1}{2}} , we obtain an element fixed by ι. Thus

C_{s} := q^{− \frac{1}{2}} (T_{s} − qT_{1})

is the required definition. Having disposed of these two base cases, we now proceed with the induction proper.

In the proof, s is a generating involution such that ℓ(sw) < ℓ(w), and v denotes sw. Here, C_{v} has already been constructed, and we have, using the notation in equation (1),

a(x, w) = −q^{\frac{1}{2}} a(x, v).

A crude approach would be to pick C_{w} = C_{s}C_{v}, imitating the structure of the T -basis. This doesn’t work in general, so we want to subtract “correction terms”. The actual definition is as follows:

C_{w} := C_{s}C_{v} − ∑_{{z≺v \atop sz<z}} μ(z, v)C_{z}.  (3)

It is immediate that C_{w} as defined above is ι-invariant (recall that μ(z, v) is an integer). We already know that C_{s} = q^{− \frac{1}{2}} T_{s} − q^{\frac{1}{2}} T_{1}, and so, by a simple inductive argument on ℓ(w), and recalling the multiplication relations for the T -basis, it is not hard to see that C_{w} is a linear combination of T_{x} with x ≤ w. The problem is to determine the coefficients. The coefficient of T_{w} is easy to find, because it can only occur in the product T_{s}C_{v}; it is

q^{− \frac{1}{2}} a(v, v)\overline{P}_{v,v} = q^{− \frac{1}{2}} qv^{\frac{1}{2}} q_{v}^{−1} = q_{w}^{− \frac{1}{2}} .

This agrees with the expression in Theorem 3.1 because, by definition, P_{w,w} = 1.

Next, choose a fixed x < w. There are two possibilities: T_{x} can occur in C_{s}C_{v} either straightforwardly (from the T_{1} component of C_{s}) in C_{v}, provided x ≤ v, or else indirectly (from the T_{s} component) in T_{s}C_{v}, provided sx ≤ v. In the latter case, the T_{x} could arise from T_{s} multiplying by T_{x} or T_{sx}, depending on the length conditions which determine the multiplication of the T -basis.

In the first case, assume that x < sx, so T_{s}T_{sx} = qT_{x} + (q − 1)T_{sx} and q^{− \frac{1}{2}} T_{s}C_{v} involves T_{x} with coefficient

q^{− \frac{1}{2}} qa(sx, v)\overline{P}_{sx,v} = q^{\frac{1}{2}} (−q^{−1})a(x, v)\overline{P}_{sx,v} = q^{−1}a(x, w)\overline{P}_{sx,v}.

Now, −q^{\frac{1}{2}} T_{1}C_{v} involves T_{x} in C_{s}C_{v} with coefficient:

−q^{\frac{1}{2}} a(x, v)\overline{P}_{x,v} = a(x, w)\overline{P}_{x,v}.

There are no other relevant terms, because T_{s}T_{x} doesn’t yield any coefficient of T_{x} in this case. Combining, we find the coefficient to be:

q^{−1}a(x, w)\overline{P}_{sx,v} + a(x, w)\overline{P}_{x,v}.  (4)

In the other case, sx < x, so T_{s}T_{sx} = T_{x} and T_{s}T_{x} = qT_{sx} + (q − 1)T_{x}. The respective coefficients of T_{x} in q^{− \frac{1}{2}} T_{s}C_{v} are thus:

q^{− \frac{1}{2}} a(sx, v)\overline{P}_{sx,v} = q^{− \frac{1}{2}} (−q)a(x, v)\overline{P}_{sx,v} = a(x, w)\overline{P}_{sx,v},
(q − 1)q^{− \frac{1}{2}} a(x, v)\overline{P}_{x,v} = (q^{−1} − 1) a(x, w) \overline{P}_{x,v}.

As for −q^{\frac{1}{2}} T_{1}C_{v}, it involves T_{x} with coefficient:

−q^{\frac{1}{2}} a(x, v)\overline{P}_{x,v} = a(x, w)\overline{P}_{x,v}.

Combining, we find the coefficient of T_{x} in C_{s}C_{v} to be

a(x, w)\overline{P}_{sx,v} + q^{−1}a(x, w)\overline{P}_{x,v}.  (5)

The coefficient of T_{x} in the sum is:

− ∑_{{z≺v \atop sz<z}} μ(z, v)a(x, z)\overline{P}_{x,z} = − ∑_{{z≺v \atop sz<z}} μ(z, v)qz^{\frac{1}{2}} q_{w}^{− \frac{1}{2}} a(x, w)\overline{P}_{x,z},

because ε_{z}ε_{w} = 1 when z ≺ v = sw. (Recall that for z ≺ v, it is necessary that ℓ(z) and ℓ(v) have different parities.)

We can now exploit the similarities between (4) and (5) by setting c = 0 when x < sx and c = 1 when sx < x. We are now ready for a unified expression for P_{x,w}, as stated in Kazhdan-Lusztig [1]:

P_{x,w} := q^{1−c}P_{sx,v} + q^{c}P_{x,v} − ∑_{{z≺v \atop z<sz}} μ(z, v)q_{z}^{− \frac{1}{2}} qw^{\frac{1}{2}}P_{x,z}.  (6)

It remains to check that the degree hypothesis is satisfied by the above P_{x,w}. This is not done in Humphreys [1], except in outline. We prove below that

P_{x,w} ≤ \frac{1}{2}(ℓ(w) − ℓ(x) − 1),

where x and w are generic elements of the Coxeter group W, and x < w.

We proceed by induction on n = ℓ(w), the case n = 0 being vacuous, and the case n = 1 being trivially verifiable from the explicit formula for C_{s} given earlier. We now prove it for P_{x,w} given that it is known for elements of smaller length than w.

The sum part of equation (6) causes few problems. If z ≺ v gives rise to a nonzero term in the sum, it is necessary that z ≤ v < w, and thus we know by induction that P_{x,z} satisfies

deg P_{x,z} ≤ \frac{1}{2}(ℓ(z) − ℓ(x) − 1),

except possibly for one term in which z = x, and hence of course sx < x. Otherwise,

deg μ(z, v)q_{z}^{− \frac{1}{2}} qw^{\frac{1}{2}}P_{x,z} ≤ \frac{1}{2}(ℓ(w) − ℓ(x) − 1),

as required (except in the one problem case).

Now we deal with the first two terms in the right hand side of (6). There are four cases, since the terms vary according as x < sx or x > sx. (Three of the cases are straightforward.) Firstly, we suppose that x < sx, and so c = 0. Hence ℓ(sx) = ℓ(x) + 1 and, by choice of s, ℓ(sw) = ℓ(v) = ℓ(w) − 1.

deg q^{1−c}P_{sx,v} = 1 + deg P_{sx,v}

≤ 1 + \frac{1}{2}(ℓ(v) − ℓ(sx) − 1)

≤ \frac{1}{2}(ℓ(w) − ℓ(x) − 1)

deg q^{c}P_{x,v} = deg P_{x,v}

≤ \frac{1}{2}(ℓ(v) − ℓ(x) − 1)

≤ \frac{1}{2}(ℓ(w) − ℓ(x) − 2)

Now suppose that sx < x, so c = 1. We get

deg q^{1−c}P_{sx,v} = deg P_{sx,v}

≤ \frac{1}{2}(ℓ(v) − ℓ(sx) − 1)

= \frac{1}{2}(ℓ(w) − 1 − ℓ(x) + 1 − 1)

≤ \frac{1}{2}(ℓ(w) − ℓ(x) − 1),

as required.

The last case is a bit more complicated:

deg q^{c}P_{x,v} = 1 + deg P_{x,v}

≤ 1 + \frac{1}{2}(ℓ(v) − ℓ(x) − 1)

≤ 1 + \frac{1}{2}(ℓ(w) − 1 − ℓ(x) − 1).

We now have a problem. It is possible that the above exceeds the limit by 1/2, i.e. it could equal (ℓ(w) − ℓ(x))/2. If this limit is reached, it must be true that x ≺ v. By hypothesis, sx < x. Thus x satisfies the conditions to be one of the terms over which the sum in (6) is taken. From the formula (6), we see this term to be

μ(x, v)q_{x}^{− \frac{1}{2}} qw^{\frac{1}{2}}P_{x,x},

i.e.

μ(x, v)q^{\frac{1}{2} (ℓ(w)−ℓ(x))}.

Happily, this cancels the term of highest degree in the “problem” term from earlier on, thus preserving the degree bound.

Multiplication Formulas

Having gone to all the trouble of constructing the C-basis, we now consider H as a module spanned by the C_{w} and act the original T -basis on it. This will eventually turn out to have some very convenient properties. Proposition 3.2 Let s, w ∈ W such that s is a generating involution of W. Then:

(a) If sw < w then

T_{s}C_{w} = −C_{w}.

(b) If w < sw then

T_{s}C_{w} = qC_{w} + q^{\frac{1}{2}} C_{sw} + q^{\frac{1}{2}} ∑_{{z≺w \atop sz<z}} μ(z, w)C_{z}.

Proof We prove (b) first, since it is easier.

Rewrite (3) with w in the role of v, and sw in the role of w to obtain

C_{sw} = C_{s}C_{w} − ∑_{{z≺w \atop sz<z}} μ(z, w)C_{z}.

Substitute the known expression

C_{s} = q^{− \frac{1}{2}} T_{s} − q^{\frac{1}{2}} T_{1}

and rewrite with T_{s}C_{w} on the left (multiplying throughout by q^{\frac{1}{2}} ), to obtain (b).

Now consider (a), assuming sw < w, so ℓ(w) ≥ 1. If ℓ(w) = 1, we have w = s, and

T_{s}C_{s} = q^{− \frac{1}{2}} T_{s}^{2} − q^{\frac{1}{2}} T_{s}
= q^{− \frac{1}{2}} ((q − 1)T_{s} + qT_{1}) − q^{\frac{1}{2}} T_{s}
= −q^{− \frac{1}{2}} T_{s} + q^{\frac{1}{2}} T_{1}
= −C_{s}.

Now the inductive step. We have s(sw) > sw, so, applying (b),

T_{s}C_{sw} = qC_{sw} + q^{\frac{1}{2}} C_{w} + q^{\frac{1}{2}} ∑_{{z≺sw \atop sz<z}} μ(z, sw)C_{z},

or

C_{w} = q^{− \frac{1}{2}} T_{s}C_{sw} − q^{\frac{1}{2}} C_{sw} − ∑_{{z≺sw \atop sz<z}} μ(z, sw)C_{z}.

For each z in the sum, sz < z < w, so T_{s}C_{z} = −C_{z} by induction. Hence

\begin{aligned}T_{s}C_{w} & = q^{− \frac{1}{2}} [(q − 1)T_{s} + qT_{1}]C_{sw} − q^{\frac{1}{2}} T_{s}C_{sw} + ∑_{{z≺sw \atop sz<z}} μ(z, sw)C_{z} \\ & = q^{\frac{1}{2}} C_{sw} − q^{− \frac{1}{2}} T_{s}C_{sw} + ∑_{{z≺sw \atop sz<z}} μ(z, sw)C_{z} \\ & = −C_{w}. \end{aligned} .

Example: A_{2}

As an example I present explicitly the C-basis for the Hecke algebra corresponding to the Coxeter group of type A_{2} (isomorphic to the symmetric group of degree 3). In the subscripts of either basis, e denotes the identity element, and 1 and 2 denote the generating involutions. (Note that T_{1} does not represent the multiplicative identity in H as it did earlier.) We now have

\begin{aligned}C_{e} & = T_{e} \\ C_{1} & = −q^{\frac{1}{2}} T_{e} + q^{− \frac{1}{2}} T_{1} \\ C_{2} & = −q^{\frac{1}{2}} T_{e} + q^{− \frac{1}{2}} T_{2} \\ C_{12} & = qT_{e} − T_{1} − T_{2} + q^{−1}T_{12} \\ C_{21} & = qT_{e} − T_{1} − T_{2} + q^{−1}T_{21} \\ C_{121} & = −q^{\frac{3}{2}} T_{e} + q^{\frac{1}{2}} T_{1} + q^{\frac{1}{2}} T_{2} − q^{− \frac{1}{2}} T_{12} − q^{− \frac{1}{2}} T_{21} + q^{− \frac{3}{2}} T_{121}. \end{aligned}

Working with the C-basis in practice

In principle, equation (6) can be used to calculate the Kazhdan-Lusztig polynomials inductively. However, the multiplication formulas between the T -basis and C-basis which were defined earlier only require knowledge of μ(z, w) when z ≺ w. Lemma 3.3

(a) If ℓ(w) − ℓ(z) = 1, then z ≺ w ⟺ z < w, and this implies that P_{z,w} = 1.

(b) If ℓ(w) − ℓ(z) = 2, then P_{z,w} = 1 if z < w, otherwise P_{z,w} = 0. Proof

First, we prove (a). Suppose z < w. Then the degree bound for P_{z,w} is automatically achieved, given that the polynomial is not zero. It is an easy consequence of (6) that for any a, b ∈ W, P_{a,b} has constant term 1 if a ≤ b, and in particular is not zero. Thus z < w ⇒ z ≺ w. Conversely, if z ≮ w, P_{z,w} = 0 and z ⊀ w.

Now consider (b). We know from the degree bounds that P_{z,w} can only have degree 0 (or be zero itself). Using an argument similar to the one above, we have that if P_{z,w} is nonzero (equivalent to z < w), it must equal 1.

The following lemma is very useful in working out exactly when a ≺ b for a, b ∈ W. It comes in left-handed and right-handed forms. I only prove the former, since the proof of the latter is entirely similar. Lemma 3.4

(a) Let x, y, s ∈ W such that s is a generating involution of W and x < y, sy < y, sx > x. Then x ≺ y ⟺ y = sx, and this implies μ(x, y) = 1.

(b) Let x, y, s ∈ W such that s is a generating involution of W and x < y, ys < y, xs > x. Then x ≺ y ⟺ y = xs, and this implies μ(x, y) = 1.

Proof of (a) Under the hypotheses, we have T_{s}C_{y} = −C_{y}. Recall that

C_{y} = ∑_{u≤y} ε_{u}ε_{y}qy^{\frac{1}{2}} q_{u}^{−1}\overline{P}_{u,y}T_{u}.  (7)

We obtain two cases, according as sx ≤ y or not, but they will be treated together, regarding d as a variable taking value 1 if sx ≤ y, and 0 otherwise.

Comparing coefficients of T_{sx} on both sides of (7), we get, on the right,

dε_{x}ε_{y}qy^{\frac{1}{2}} q_{x}^{−1}q^{−1}\overline{P}_{sx,y}T_{sx}.

The relevant coefficients on the left arise from terms like T_{s}T_{x} and, if sx ≤ y, from T_{s}T_{sx}.

The coefficient of T_{sx} is now

ε_{x}ε_{y}qy^{\frac{1}{2}} q_{x}^{−1}\overline{P}_{x,y} + d(q − 1)ε_{sx}ε_{y}qy^{\frac{1}{2}} q_{sx}^{−1}\overline{P}_{sx,y},

i.e.

ε_{x}ε_{y}qy^{\frac{1}{2}} q_{x}^{−1} (\overline{P}_{x,y} − dq^{−1}(q − 1)\overline{P}_{sx,y}) .

Now, equating coefficients,

\begin{aligned}dq^{−1}\overline{P}_{sx,y} & = \overline{P}_{x,y} + d(q^{−1} − 1)\overline{P}_{sx,y} \\ \overline{P}_{x,y} & = d\overline{P}_{sx,y} \\ P_{x,y} & = dP_{sx,y}. \end{aligned}

In the case sx ≤ y, this gives P_{x,y} = P_{sx,y}. Otherwise, this gives P_{x,y} = 0, but we also have by convention that P_{sx,y} = 0. Hence in either case, we have P_{x,y} = P_{sx,y}.

If sx ≠ y, we have

deg P_{x,y} = deg P_{sx,y} ≤ \frac{1}{2}(ℓ(y) − ℓ(x) − 2) < \frac{1}{2}(ℓ(y) − ℓ(x) − 1),

hence it is not true that x ≺ y.

Now suppose sx = y. From P_{x,y} = P_{sx,y} we immediately get

P_{x,y} = P_{y,y} = 1,

hence x ≺ y and μ(x, y) = 1.

Example: A_{3}

We are interested in finding out exactly when a ≺ b for a, b ∈ W = A_{3}. (In this case, W ≅ S_{4}.) It does not take too long to calculate the Bruhat order for A_{3} in full, and work out when sx < x and when xs < x for all combinations of x ∈ W and s a generating involution of W. When this is done, Lemmas 3.3 and 3.4 can be applied very easily to many different cases. It is then clear that there are only two interesting pairs of values for a and b: a = 13, b = 13213 and a = 2, b = 2132. (Of course 2 is a shorthand for s_{2}, and so on, and e is the identity.) In all other cases, P_{a,b} is clearly equal to 1.

In the other two cases we have:

P_{13,13213} = P_{3,3213} + qP_{13,3213}
= 1 + q
P_{2,2132} = P_{e,132} + qP_{2,132}
= 1 + q.

These results will suffice to calculate the relevant representations of type A_{3} later on.

4: Cells and Representations

Cells

We are now in a position to define the cells of a Coxeter group W. There are three kinds of cell (left, right, and two-sided). Each kind of cell is an equivalence class of a corresponding equivalence relation on the group, and the set of cells of a given type has a partial order imposed on it. This partial order is compatible with the multiplication formulas involving the C-basis in §3, and we can exploit this to find relatively low-dimensional representations of the Hecke algebra.

The first goal is to define the preorders ≤_{L}, ≤_{R} and ≤_{LR} on the group W. These will be reflexive and transitive, but not in general antisymmetric. However, such a preorder does yield an equivalence relation such that the preorder is antisymmetric on the equivalence classes.

We will write x—w to mean that either x ≺ w or w ≺ x. We also define, for each w ∈ W, subsets of S, the set of generators for W:

L(w) := {s ∈ S | sw < w}, R(w) := {s ∈ S | ws < w}.

In particular, L(e) = ∅ = R(e), and L(w_{∘}) = S = R(w_{∘}), where w_{∘} is the unique element of greatest length in W.

We now define x≤_{L}w to mean there is a chain x = x_{0}, x_{1}, …, x_{r} = w such that x_{i}—x_{i+1} and L(x_{i}) ⊈ L(x_{i+1}) for 0 ≤ i < r. We define the relation x∼_{L}w to mean both x≤_{L}w and w≤_{L}x. It is easy to check that this is an equivalence relation. The equivalence classes are called the left cells of W.

The relations x≤_{R}w, x∼_{R}w, and right cells are defined entirely analogously.

We also define x≤_{LR}w to mean there exists a chain x = x_{0}, x_{1}, …, x_{r} = w such that for i < r, either x_{i}≤_{L}x_{i+1} or x_{i}≤_{R}x_{i+1}. This gives the equivalence relation x∼_{LR}w, and the equivalence classes in this case are called two-sided cells. It is immediate that two-sided cells are unions of (a) left cells and (b) right cells.

It will turn out, using the theory developed in §2 and §3, that with each cell of each type, we can associate a representation of H, and so, by specialising q^{\frac{1}{2}} → 1, we obtain a representation of W. The dimension of the representation will turn out to be the size of the cell, and hence will be small compared to |W |. Notice that we could just as well have specialised q^{\frac{1}{2}} → −1.

Example: A_{3} We now list the left cells, right cells and two-sided cells for the Coxeter group of type A_{3}. The left cells will be used later to derive representations of the associated Hecke algebra. Again, e denotes the identity, and 1, 2, 3 the generating involutions of the group.

Left Cells

The rows give the cells, and they are yoked together to indicate which cells union to give the two-sided cells.

{ e }
{ 132132 }
\{ \begin{matrix}2132 & 312 \\ 13 & 213 \end{matrix} \}
\{ \begin{matrix}1 & 21 & 321 \\ 2 & 12 & 32 \\ 3 & 23 & 123 \end{matrix} \}
\{ \begin{matrix}13213 & 3213 & 1213 \\ 121 & 3212 & 32132 \\ 232 & 1323 & 12132 \end{matrix} \}

Right Cells

{ e }
{ 132132 }
\{ \begin{matrix}2132 & 213 \\ 13 & 312 \end{matrix} \}
\{ \begin{matrix}1 & 12 & 123 \\ 2 & 23 & 21 \\ 3 & 32 & 321 \end{matrix} \}
\{ \begin{matrix}13213 & 1323 & 3212 \\ 121 & 1213 & 12132 \\ 232 & 3213 & 32132 \end{matrix} \}

The two-sided cells are obvious from this information.

It should be remarked that the cells, although they seem easy to understand, in fact have subtle connections to Lie theory and other areas. For example, in the Coxeter groups of type A, the cells are closely connected with the Robinson-Schensted correspondence between the elements of the group and “standard Young tableaux”. For example, in each left cell and in each right cell there is exactly one element w such that w^{2} = 1. A connection with Lie theory is mentioned in Lusztig [1], where a sketch proof of the following result is given:

Theorem 4.1 Assume that W is a finite Weyl group, containing elements y and w such that y≤_{L}w and y and w are not in the same left cell. Then y and w are not in the same two-sided cell. Proof Amazingly, this relies on deep results on infinite-dimensional representations of the complex Lie algebra g with W as a Weyl group! The reader is referred to Lusztig [1] for more details.

W -graphs

In Kazhdan-Lusztig [1], the authors introduce the notion of a W -graph. We will be concerned with W -graphs associated to left cells, although the properties of those associated to right cells will be completely analogous.

To each element z in a left cell Z of the Coxeter group W, we assign a vertex, and to this vertex is associated a subset of the generating involutions S of W. Since we are dealing with left cells, we shall specify this set to be L(z). Two vertices a and b will be joined by an (undirected) edge labelled with the integer m, defined to be μ(a, b) if a ≺ b, or m = μ(b, a) if b ≺ a, or 0 otherwise. (Of course at most one of a ≺ b and b ≺ a can occur by length considerations.) Edges of strength 0 are omitted.

The W -graphs arising from left cells of A_{3} are as follows.

-

1 — 2 — 3
1 3 — 2
2 3 — 1 3 — 1 2

1 2 3

In this case, left cells in the same two-sided cell give the same graph.

Another property of the C-basis With our new perspective on cells, we return our attention to the multiplication formulas involving the T -basis and C-basis as in Proposition 3.2. In that proposition, the result of (a) is easy to understand but the result of (b) appears complicated and random. What 3.2 (b) said was:

If w < sw then

T_{s}C_{w} = qC_{w} + q^{\frac{1}{2}} C_{sw} + q^{\frac{1}{2}} ∑_{{z≺w \atop sz<z}} μ(z, w)C_{z}.

Now look at the C_{z} occurring with non-zero coefficients in this expression. I claim that for each such z, we have z≤_{L}w. We have that s ∈ L(sw) and s ∈ L(z) where z ≺ w and sz < z. The first part follows from w < sw, so s(sw) < sw, and the second part is obvious. However, we also have w < sw, so s ∉ L(w). Hence L(sw) ⊈ L(w), and L(z) ⊈ L(w), for z in the sum. Hence all the C_{z} in the expression satisfy the required property.

This casts a new light on 3.2 (b); it is now seen to have a “triangular” nature with respect to ≤_{L}. This will be exploited in the construction of representations from the cells.

Representations from left cells

Although everything we shall say about representations from cells will be done in the case of left cells, it all goes through for right cells and two-sided cells in a similar way.

Let Z be a left cell of W, and define I_{Z} to be the A-span of all C_{w} such that w ∈ Z and all C_{x} such that x≤_{L}w for some w ∈ Z. The remarks above about the “triangular” nature of the multiplication formulae immediately show that I_{Z} is an ideal of H. Now define I′_{Z} to be the span of the C_{x} such that x≤_{L}w for some w ∈ Z but x ∉ Z. Lemma 4.2 The A-module I′_{Z} is an ideal of H. Proof

Suppose v≤_{L}x≤_{L}w ∈ Z, where v ∈ Z and x ∉ Z. By definition of Z, we also have w≤_{L}v. Hence
w≤_{L}v≤_{L}x,

so by transitivity, w≤_{L}x. We are now in the situation where x≤_{L}w and w≤_{L}x, forcing x ∈ Z contrary to hypothesis.

Thus, if x≤_{L}w ∈ Z where x ∉ Z multiplying C_{x} on the left by T_{s} must result in a sum of the form

∑_{y} α_{y}C_{y},

where y≤_{L}x≤_{L}w ∈ Z but y ∉ Z.

The main claim quickly follows.

It is clear that I′_{Z} ⊆ I_{Z}, so we can form the quotient module

M_{Z} := I_{Z}/I′_{Z}.

When we speak of the representation of H coming from the left cell Z, we mean one afforded by this module.

Representations of the Hecke algebra of type A_{3}

I now present the complete set of representations of the Hecke algebra corresponding to the Coxeter group of type A_{3}. This task is less formidable than it seems at first because, in this case, left cells contained in the same two-sided cell give rise to equivalent representations; in fact, one representation can be obtained from another by conjugating by a permutation matrix. We therefore study one representation from each two-sided cell. It will turn out, as always in type A, that the representations we obtain will be irreducible, and so will the specialisations giving the representations of the Coxeter group of type A_{3}.

It will also be useful to know that the set {e, s_{1}, s_{1}s_{2}, s_{1}s_{2}s_{3}, s_{1}s_{3}} is a complete set of conjugacy class representatives for the Coxeter group of type A_{3}.

It is clear (by construction) that M_{Z} has a basis in bijection with the set of C_{z} where z ∈ Z and hence the dimension of M_{Z} is equal to |Z|. We can thus predict from the information about the cells that the dimensions of the representations arising will be 1, 1, 2, 3 and 3. It turns out in type A that such representations, when specialised, are precisely the irreducible representations of the group over .

The easiest representations to construct are the 1-dimensional ones. First we consider the representation arising from the cell {e}. This maps T_{1}, T_{2} and T_{3} to the matrix (q), and gives the trivial representation of the Coxeter group.

Next we have the cell {132132}. This sends T_{1}, T_{2} and T_{3} to (−1) and hence gives the sign representation for the Coxeter group.

For the two dimensional representation we study the left cell {2132, 312}. We get a representation as follows:

\begin{aligned}T_{1} & → & ( \begin{matrix}q & 0 \\ q^{\frac{1}{2}} & −1 \end{matrix} ) & T_{2} & → & ( \begin{matrix}−1 & q^{\frac{1}{2}} \\ 0 & q \end{matrix} ) & T_{3} & → & ( \begin{matrix}q & 0 \\ q^{\frac{1}{2}} & −1 \end{matrix} ) \\ s_{1} & → & ( \begin{matrix}1 & 0 \\ 1 & −1 \end{matrix} ) & s_{2} & → & ( \begin{matrix}−1 & 1 \\ 0 & 1 \end{matrix} ) & s_{3} & → & ( \begin{matrix}1 & 0 \\ 1 & −1 \end{matrix} ) \\ s_{1}s_{3} & → & ( \begin{matrix}1 & 0 \\ 0 & 1 \end{matrix} ) & s_{1}s_{2} & → & ( \begin{matrix}−1 & 1 \\ −1 & 0 \end{matrix} ) & s_{1}s_{2}s_{3} & → & ( \begin{matrix}0 & −1 \\ −1 & 0 \end{matrix} ) \end{aligned}

The character associated with this is (2, 0, −1, 0, 2) (with the conjugacy classes ordered as defined).

Now consider the left cell {13213, 3213, 1213}. The associated representation gives the following:

\begin{aligned}T_{1} & → & ( \begin{matrix}−1 & q^{\frac{1}{2}} & 0 \\ 0 & q & 0 \\ 0 & 0 & 1 \end{matrix} ) & T_{2} & → & ( \begin{matrix}q & 0 & 0 \\ q^{\frac{1}{2}} & −1 & 0 \\ q^{\frac{1}{2}} & 0 & −1 \end{matrix} ) & T_{3} & → & ( \begin{matrix}−1 & 0 & q^{\frac{1}{2}} \\ 0 & −1 & 0 \\ 0 & 0 & q \end{matrix} ) \\ s_{1} & → & ( \begin{matrix}−1 & 1 & 0 \\ 0 & 1 & 0 \\ 0 & 0 & −1 \end{matrix} ) & s_{2} & → & ( \begin{matrix}1 & 0 & 0 \\ 1 & −1 & 0 \\ 1 & 0 & −1 \end{matrix} ) & s_{3} & → & ( \begin{matrix}−1 & 0 & 1 \\ 0 & −1 & 0 \\ 0 & 0 & 1 \end{matrix} ) \\ s_{1}s_{3} & → & ( \begin{matrix}1 & −1 & −1 \\ 0 & −1 & 0 \\ 0 & 0 & 1 \end{matrix} ) & s_{1}s_{2} & → & ( \begin{matrix}0 & −1 & 0 \\ 1 & −1 & 0 \\ −1 & 0 & 1 \end{matrix} ) & s_{1}s_{2}s_{3} & → & ( \begin{matrix}0 & 1 & 0 \\ −1 & 1 & 1 \\ 1 & 0 & 0 \end{matrix} ) \end{aligned}

Here, the associated character is (3, −1, 0, 1, −1).

Finally, we look at the cell {1, 21, 321}. In this case, the representation gives:

\begin{aligned}T_{1} & → & ( \begin{matrix}−1 & q^{\frac{1}{2}} & 0 \\ 0 & q & 0 \\ 0 & 0 & q \end{matrix} ) & T_{2} & → & ( \begin{matrix}q & 0 & 0 \\ q^{\frac{1}{2}} & −1 & q^{\frac{1}{2}} \\ 0 & 0 & q \end{matrix} ) & T_{3} & → & ( \begin{matrix}q & 0 & 0 \\ 0 & q & 0 \\ 0 & q^{\frac{1}{2}} & −1 \end{matrix} ) \\ s_{1} & → & ( \begin{matrix}−1 & 1 & 0 \\ 0 & 1 & 0 \\ 0 & 0 & 1 \end{matrix} ) & s_{2} & → & ( \begin{matrix}1 & 0 & 0 \\ 1 & −1 & 1 \\ 0 & 0 & 1 \end{matrix} ) & s_{3} & → & ( \begin{matrix}1 & 0 & 0 \\ 0 & 1 & 0 \\ 0 & 1 & −1 \end{matrix} ) \\ s_{1}s_{3} & → & ( \begin{matrix}−1 & 1 & 0 \\ 0 & 1 & 0 \\ 0 & 1 & −1 \end{matrix} ) & s_{1}s_{2} & → & ( \begin{matrix}0 & −1 & 1 \\ 1 & −1 & 1 \\ 0 & 0 & 1 \end{matrix} ) & s_{1}s_{2}s_{3} & → & ( \begin{matrix}0 & 0 & −1 \\ 1 & 0 & −1 \\ 0 & 1 & −1 \end{matrix} ) \end{aligned}

The associated character is (3, 1, 0, −1, −1).

From this information it is easy to check using character-theoretic methods that we have found all the irreducible representations of the Coxeter group of type A_{3}.

References

R.W. Carter

1. Coxeter Groups and Hecke Algebras, lecture notes for an M.Sc. course.

2. Simple Groups of Lie Type, J. Wiley & Sons, London, 1972. J.E. Humphreys

1. Reflection Groups and Coxeter Groups, Cambridge University Press, 1990. D. Kazhdan, G. Lusztig

1. Representations of Coxeter Groups and Hecke Algebras, Invent. Math. 53 (1979), 165–184. G. Lusztig

1. On a Theorem of Benson and Curtis, J. Alg. 71 (1981), 490–498. J. Tits

1. Théorème de Bruhat et sous-groupes paraboliques, Académie des Sciences, Séance du 16 avril, 1962.