Hecke Algebras

Introduction

Let $(W,S)$ be a Coxeter system with $S$ finite and $W$ finite, and let $k$ be a commutative ring with identity. The Hecke algebra $H_q(W)$ is the $k[q^{\pm1}]$-algebra generated by elements $T_s$, one for each $s\in S$, subject to the braid relations of $W$ and the quadratic relations

$$ T_s^2 = (q-1)T_s + q , \qquad s\in S . $$

At $q = 1$ the quadratic relation becomes $T_s^2 = 1$ and the braid relations become the presentation of $W$, so $H_1(W) = k[W]$ is the group algebra of Group Algebras: the Hecke algebra is a one-parameter deformation of the group algebra of a finite Coxeter group, and the two are isomorphic after extending scalars to a large enough field, so that the representation theory of $W$ governs that of $H_q(W)$ for generic $q$. The algebra carries a symmetrising form with respect to which it is a symmetric algebra in the sense of Frobenius Algebras, and this is the sense in which it belongs to the category Symmetric Linear Algebras: the multiplication is not commutative in general, but the algebra is symmetric as an associative algebra with a trace.

The article is the fourteenth of the corpus and the first of the category Symmetric Linear Algebras after the articles of that category written above it, of which The Symmetric Algebra and Symmetric Powers supply the conventions for the polynomial ring and the divided powers on which the Hecke algebra of type $A$ acts. It develops the presentation and the standard basis with the multiplication rule, the symmetrising form and the structure theorem, the origin of the algebra in the Tits system of a group with a BN-pair, the deformation theorem of Tits and the parametrisation of the simple modules, the degenerate cases $q = 0$ and the nilCoxeter algebra, and the Kazhdan–Lusztig basis with the cells into which the algebra is organised.

The article is algebraic throughout. The permutation module $k[G/B]$ and its endomorphism algebra, which is the algebraic form of the Hecke algebra of a Tits system, are built from the coset action of a group, an object of Buildings and Tits Systems. What is deferred is the analytic theory: the convolution algebra of a locally compact group, the Haar measure, the spherical functions and the Satake isomorphism, the affine Hecke algebras and the Iwahori–Hecke algebras of a $p$-adic group, and the representation theory of the Hecke algebra at a root of unity with its crystals and its categorical statements, all of which use the measure, the limit or the geometry of a building and belong to Part III and ,and Analysis on Groups. Where the classical development of the affine case is mentioned below, the mention is a forward reference and nothing in the argument uses it. No manifold, no distance, no form and no topological object appears.

Throughout, $(W,S)$ is a Coxeter system with $S$ finite, $m_{st}$ the order of $st$, $l(w)$ the length and $\leq$ the Bruhat order, $W$ is finite unless stated, $k$ is a commutative ring with identity, $q$ is an indeterminate and $k[q^{\pm1}]$ is the ring of Laurent polynomials in $q$; the parameter is written $q$ in the classical notation, and no quadratic form occurs in this article, the forms of Part II being written $\mathrm{Cl}(V,Q)$ there.

Coxeter Systems

Definition. A Coxeter system is a pair $(W,S)$ with $W$ a group generated by a set $S$ and the presentation

$$ W = \langle s\in S \mid s^2 = 1,\ (st)^{m_{st}} = 1 \text{ for } s\neq t\rangle , $$

where $m_{st} = m_{ts}\in\{2,3,\dots\}\cup\{\infty\}$ and $m_{st} = \infty$ means that no relation between $s$ and $t$ is imposed. The elements of $S$ are the simple reflections, and $m_{st}$ is the order of $st$. The group $W$ is a Coxeter group, and the system is finite if $W$ is finite.

Definition. The length of $w\in W$ is the least number $l(w)$ of simple reflections whose product is $w$, such that an expression $w = s_1\cdots s_l$ with $l = l(w)$ is a reduced word for $w$; and the Bruhat order is the partial order $\leq$ on $W$ in which $x\leq w$ if some subword of a reduced word for $w$ is a reduced word for $x$.

Proposition. The length function is well defined and satisfies $l(ws) = l(w)\pm1$ for $s\in S$, with $l(ws) = l(w)+1$ if and only if $ws > w$ in the Bruhat order, and $l(ws) = l(w)-1$ if and only if $ws < w$. The parity of $l(w)$ is the parity of the number of occurrences of each $s\in S$ in any expression for $w$.

Pro. The well-definedness of the length and the parity statement are the standard elementary theory of Coxeter groups, recorded where the root system of $(W,S)$ is attached to $W$: the reflection representation provides the roots $\alpha_s$ and the length is the number of positive roots sent to negative roots, which is independent of the chosen expression. The equality $l(ws) = l(w)+1$ in the increasing case follows from the same description, since the roots sent negative by $ws$ are those sent negative by $w$ together with $\alpha_s$ when it is not already one of them.

Remark. The Coxeter graph of $(W,S)$ has $S$ as its vertices and an edge between $s$ and $t$ whenever $m_{st}\geq3$, the edge labelled by $m_{st}$ when $m_{st}\geq4$; the connected components of the graph correspond to the direct factors of $W$, and $W$ is finite exactly for the types classified. In this article only the presentations and the length function are used, and the classification enters through the finiteness of $W$, needed so that the Hecke algebra be a finitely generated module.

Example. For $W = S_n$ with $S = \{s_1,\dots,s_{n-1}\}$ the adjacent transpositions, $m_{s_is_j} = 3$ for $|i-j| = 1$ and $m_{s_is_j} = 2$ for $|i-j|\geq2$, and $l(w)$ is the number of inversions of the permutation $w$. The type is $A_{n-1}$, and it is the type of the symmetric group and of the general linear group over a finite field, which is the example of the next section.

The Presentation and the Standard Basis

Definition. Let $(W,S)$ be a Coxeter system with $S$ finite and let $A = k[q^{\pm1}]$. The Hecke algebra $H_q(W)$ is the $A$-algebra with generators $T_s$, $s\in S$, and relations

$$ T_sT_tT_s\cdots = T_tT_sT_t\cdots \quad (\text{$m_{st}$ factors on each side}), \qquad T_s^2 = (q-1)T_s + q . $$

At $q = 1$ the relations are those of $W$, so that $H_1(W) = k[W]$.

Definition. For $w\in W$ with reduced word $w = s_1\cdots s_l$, set $T_w = T_{s_1}\cdots T_{s_l}$; the braid relations are exactly the statement that $T_w$ does not depend on the reduced word chosen, so that the assignment is well defined.

Theorem (the standard basis). The elements $T_w$, $w\in W$, form a basis of $H_q(W)$ as an $A$-module; consequently $H_q(W)$ is free of rank $\lvert W\rvert$ over $A$ and is a deformation of the group algebra $k[W]$ over the ring $k[q^{\pm1}]$. The multiplication is determined by

$$ T_wT_s = \begin{cases} T_{ws}, & l(ws) = l(w)+1,\\[2pt] q\,T_{ws} + (q-1)T_w, & l(ws) = l(w)-1 .\end{cases} $$

Proof (outline). One shows that the submodule spanned by the $T_w$ is closed under right multiplication by the generators: if $l(ws) = l(w)+1$ the product is $T_{ws}$ by definition, while if $l(ws) = l(w)-1$ one writes $w = w's$ with $l(w) = l(w')+1$ and computes

$$ T_wT_s = T_{w'}T_s^2 = T_{w'}\bigl((q-1)T_s + q\bigr) = (q-1)T_{w'}T_s + qT_{w'} = (q-1)T_w + qT_{ws}, $$

which is the displayed rule. The relations of $W$ ensure that the rule is compatible with the braid relations, and the uniqueness of the reduced word decomposition makes the resulting multiplication associative; the freeness of the resulting module follows from the triangular form of the rule, which expresses each product $T_wT_s$ in terms of the $T$-basis with leading term $T_{ws}$. The case $W = S_3$, where the algebra has rank $6$, is explicit: the six elements $T_1$, $T_{s_1}$, $T_{s_2}$, $T_{s_1s_2}$, $T_{s_2s_1}$, $T_{s_1s_2s_1} = T_{w_0}$ are linearly independent over $A$, the quadratic relations hold for each generator, the braid relation $T_{s_1}T_{s_2}T_{s_1} = T_{s_2}T_{s_1}T_{s_2}$ holds, and the multiplication so defined is associative.

Corollary. For a transcendental parameter $q$ the centre of $H_q(W)\otimes_Ak(q)$ has dimension $\lvert\operatorname{conj}(W)\rvert$ over $k(q)$, the number of conjugacy classes of $W$, which is also the number of irreducible characters of $W$; the centre is not in general spanned by the class sums $\sum_{w\in C}T_w$ over the conjugacy classes $C$ of $W$, as the computation for $W = S_3$ below shows, and the central elements are corrected combinations of the class sums. The algebra is commutative if and only if the Coxeter graph is disconnected, that is, if and only if $W$ is a direct product of copies of $S_2$; and $H_q(W)$ is generated as an algebra by the elements $T_s$.

Proof. Over the fraction field $k(q)$ with $q$ transcendental the algebra $H_q(W)$ is split semisimple with one simple component for each irreducible character of $W$, so its centre has dimension $\lvert\operatorname{Irr}(W)\rvert = \lvert\operatorname{conj}(W)\rvert$; the class sums fail to be central because a product $T_{s_1}T_{s_2}$ differs from $T_{s_2}T_{s_1}$ in the basis as soon as $m_{s_1s_2}\geq3$, the two being distinct basis elements, so that $T_{s_1}(T_{s_1}+T_{s_2})-(T_{s_1}+T_{s_2})T_{s_1} = T_{s_1s_2}-T_{s_2s_1}$; commutativity therefore requires $m_{st} = 2$ for every pair, which is the stated condition. Generation by the $T_s$ is by definition.

Example (rank one and the smallest non-commutative case). For $W = S_2 = \{1,s\}$ the algebra has basis $1,T_s$ with $T_s^2 = (q-1)T_s+q$; it is commutative, and over a field in which $q+1$ is invertible it is isomorphic to $k\times k$, the two factors corresponding to the one-dimensional modules on which $T_s$ acts by the scalars $q$ and $-1$, the two roots of $t^2-(q-1)t-q$. For $W = S_3$ the algebra has rank $6$ and its centre has rank $3$; the naive class sums are not central there, since $T_{s_1}(T_{s_1}+T_{s_2})-(T_{s_1}+T_{s_2})T_{s_1} = T_{s_1s_2}-T_{s_2s_1}$, while the three elements $1$, $T_{s_1s_2}+T_{s_2s_1}+(1-q)(T_{s_1}+T_{s_2})$ and $T_{w_0}+q(T_{s_1}+T_{s_2})$ commute with both generators and are linearly independent, so that they span the centre; this is the smallest case in which the algebra is non-commutative.

The Symmetrising Form and the Structure

Definition. The symmetrising form of $H_q(W)$ is the $A$-bilinear form $\langle-,-\rangle$ with

$$ \langle T_x,T_y\rangle = \tau(T_xT_y), \qquad\text{where}\qquad \tau(T_w) = \begin{cases}1, & w = 1,\\ 0, & w\neq1,\end{cases} $$

that is, $\tau$ is the $A$-linear functional that reads off the coefficient of $T_1$ in the standard basis and the form is the associated bilinear form.

Theorem. The functional $\tau$ is a trace: $\tau(T_xT_y) = \tau(T_yT_x)$ for all $x,y\in W$. The form $\langle-,-\rangle$ is symmetric, nondegenerate and associative: $\langle T_xT_y,T_z\rangle = \langle T_x,T_yT_z\rangle$. Moreover

$$ \langle T_x,T_y\rangle = \begin{cases} q^{l(x)}, & xy = 1,\\ 0, & xy\neq1 .\end{cases} $$

Consequently $H_q(W)$ is a symmetric algebra in the sense of Frobenius Algebras: it is a free $A$-module of finite rank carrying an associative, symmetric, nondegenerate bilinear form, and it is additionally a Frobenius algebra with the symmetrising form $\tau$ as its Frobenius form.

Proof. The rule of the standard basis shows that the coefficient of $T_1$ in $T_xT_y$ is zero unless $xy = 1$, and in that case equals $q^{l(x)}$: iterating the rule, the only way to reduce a reduced word for $xy$ to the identity is to reduce each generator in turn against its own inverse, each reduction producing a factor $q$. The displayed formula follows, and from it the symmetry $\tau(T_xT_y) = \tau(T_yT_x)$ is immediate, since both sides vanish unless $x = y^{-1}$. Nondegeneracy is the pairing of the basis with the inverse basis: $\langle T_x,T_{x^{-1}}\rangle = q^{l(x)}\neq0$ and all other pairings of $T_x$ with basis elements vanish. Associativity is the associativity of the multiplication together with the trace property. For the case $W = S_3$ the identity was checked on all $36$ pairs of basis elements: the coefficient of $T_1$ in $T_xT_y$ is $q^{l(x)}$ when $xy = 1$ and $0$ otherwise.

Corollary. The form $\langle-,-\rangle$ equips $H_q(W)$ with a duality that identifies the left and the right regular modules, and every projective $H_q(W)$-module is injective; the algebra is self-injective, hence a quasi-Frobenius algebra in the terminology of Frobenius Algebras.

Remark. The bilinear form and the trace are the algebraic substitutes for the counting of the double cosets of the next section: in the geometric situation $\tau$ counts the double cosets contained in a given one, and the trace property is the statement that the algebra of a Tits system is symmetric. The Frobenius algebra structure is the object through which the Hecke algebra is a symmetric linear algebra, and its finite-dimensional representation theory — the projective and injective modules, the Cartan matrix and the decomposition matrix — is the subject of the articles of the category Linear Spaces over Linear Algebras that follow.

The Hecke Algebra of a Tits System

Definition. A Tits system in a group $G$ is a quadruple $(G,B,N,S)$ with $B$ and $N$ subgroups generating $G$, with $B\cap N$ normal in $N$, with $W = N/(B\cap N)$ generated by the image $S$ of a set of involutions of $N$, and satisfying: $sBs\neq B$ for every $s\in S$, and the exchange condition

$$ BsB\cdot BwB\subseteq BwB\cup BswB \qquad (s\in S,\ w\in W), $$

where $l(sw)>l(w)$. The group $W$ is the Weyl group of the system, $B$ is the Borel subgroup, and the exchange condition is equivalent to the statement that $W$ is a Coxeter group on $S$.

Example. Let $G = GL_n(\mathbb{F}_\ell)$ over the finite field with $\ell$ elements, let $B$ be the subgroup of upper triangular matrices and let $N$ be the subgroup of monomial matrices. Then the parameter of the associated Hecke algebra is $q = \ell$, the cardinality of the field. Then $W = N/(B\cap N)\cong S_n$, the subgroup $B\cap N$ consists of the diagonal matrices, and the pair $(B,N)$ is a Tits system of type $A_{n-1}$. The double cosets $BwB$ are the Bruhat cells of the flag variety, in the algebraic sense of a set of cosets.

Theorem (standard). Let $(G,B,N,S)$ be a Tits system with finite $W$, and let $k$ be a field. Let $H(G,B)$ be the $k$-vector space with basis the double cosets $BwB$, $w\in W$, with the multiplication

$$ BwB\cdot Bw'B = \sum_{w''}c_{w,w'}^{w''}\,Bw''B , $$

the coefficients $c$ being determined by the exchange conditions of the system. Then $H(G,B)$ is isomorphic to the Hecke algebra $H_q(W)$ with $q = \lvert BsB/B\rvert$, which is independent of $s$; the isomorphism sends $T_w$ to the class of the double coset $BwB$ rescaled by the power of $q$ determined by $l(w)$. Equivalently, $H(G,B)\cong\operatorname{End}_{kG}\bigl(k[G/B]\bigr)$: the Hecke algebra is the endomorphism algebra of the permutation module on the cosets of $B$, that is, of the module $k[G/B]$.

Proof (outline). The exchange conditions give the rule $BwB\cdot BsB\subseteq BwsB\cup BwB$ with the coefficient of $BwB$ equal to $q$ in the second case, which is the quadratic relation in the form the multiplication rule takes after the normalisation $T_w = q^{l(w)/2}\,[BwB]$; the associativity is inherited from the multiplication of the double cosets. The identification with the endomorphisms of $k[G/B]$ is the standard one: a $kG$-endomorphism of $k[G/B]$ is determined by its value on the class of $B$, and the values are the elements fixed by $B$ on the right, that is the set of double cosets; composition is the convolution, which reproduces the multiplication of $H(G,B)$.

This is the origin of the Hecke algebra and of the name of its parameter: the algebra is the endomorphism algebra of a permutation module, it is a deformation of the group algebra $k[W]$, and the parameter $q = \lvert BsB/B\rvert$ is the cardinality of a cell of the geometry. The same algebra arises over a non-finite ground field or a local field as the algebra of a Tits system of a group with a BN-pair, and there the analysis of the associated spherical functions uses the measure and the limit; the algebraic statement is the one recorded here, andandare the articles that fix the boundary of the analytic theory in Part III.

Deformation and the Simple Modules

Theorem (Tits' deformation theorem, standard). Let $(W,S)$ be a finite Coxeter system and let $K$ be a field of characteristic $0$. Then for all but finitely many values of $q$ — the excluded values being the roots of unity of small order — the $K$-algebra $H_q(W)$ obtained by specialising the parameter is semisimple and isomorphic to $K[W]$; in particular, for such $q$ the simple $H_q(W)$-modules are in bijection with the irreducible $K$-representations of $W$, the bijection preserving dimensions.

Proof (outline). The algebra $H_q(W)$ is free of finite rank over $K[q^{\pm1}]$ and is a deformation of $K[W]$; Tits' argument tracks a complete set of primitive idempotents of $K[W]$ through the deformation, showing that they deform to a set of orthogonal idempotents summing to one in $H_q(W)\otimes_{K[q^{\pm1}]}K(q)$. The specialisation at a value of $q$ in $K$ is then semisimple provided the denominators that occur are invertible, which fails only at the finitely many excluded values.

Corollary. For generic $q$ the number of simple $H_q(W)$-modules equals the number of conjugacy classes of $W$; the trivial $K[W]$-module deforms to the trivial module of $H_q(W)$ on which every $T_s$ acts by the scalar $q$, and the sign module deforms to the module on which every $T_s$ acts by $-1$; the trivial and the sign module are the two one-dimensional simple modules for every specialisation of $q$.

Proof. The count is Tits' theorem together with the number of conjugacy classes, and the two displayed actions satisfy the quadratic relation: $q^2 = (q-1)q+q$ for the trivial one and $1 = -(q-1)+q$ for the sign one.

Remark (the degenerate values). At a root of unity the algebra need not be semisimple, and its representation theory at such a value is the modular theory of the Hecke algebra, whose cells and crystals are the deep part of the subject; the classification of the simple modules at a root of unity is due to Kazhdan–Lusztig's conjectures in the Lie-theoretic case and to the theory of the canonical basis in general, and it is where the algebra interacts with Quantum Groups, which is its quantum-group counterpart in the category Linear Algebras above. That theory uses the structure of the crystal and the geometry of a building, hence Part III, and it is not used here.

The Degenerate Cases: $q = 0$ and the NilCoxeter Algebra

Definition. The specialisation of $H_q(W)$ at $q = 0$ is the $0$-Hecke algebra $H_0(W)$, the $k$-algebra with generators $T_s$ and relations $T_s^2 = -T_s$; writing $\pi_s = -T_s$ the relations read $\pi_s^2 = \pi_s$ together with the braid relations, so that $H_0(W)$ is the monoid algebra of the $0$-Hecke monoid, the monoid with generators $\pi_s$ and the braid relations and the idempotent relations.

Proposition. The $0$-Hecke algebra $H_0(W)$ has basis $\{\pi_w : w\in W\}$ with $\pi_w = \pi_{s_1}\cdots\pi_{s_l}$ for a reduced word, and the multiplication is

$$ \pi_w\pi_s = \begin{cases}\pi_{ws}, & l(ws) = l(w)+1,\\ \pi_w, & l(ws) = l(w)-1.\end{cases} $$

The algebra has exactly $\lvert W\rvert$ simple modules, all one-dimensional, indexed by the elements of $W$, and $\pi_w$ acts on the module indexed by $u$ by $1$ if $uw = u$ and $0$ otherwise.

Proof. The multiplication rule is the specialisation of the standard rule at $q = 0$, and the basis statement follows as in the general case. A one-dimensional module is a character, determined by the images $a_s$ of the $\pi_s$ subject to $a_s^2 = a_s$ and the braid relations, so each $a_s\in\{0,1\}$; the compatibility with the braid relations gives the cells of the monoid, and the standard construction of the $\lvert W\rvert$ characters by the "bottom" elements of the left cells exhibits them all.

Definition. The nilCoxeter algebra $N(W)$ is the $k$-algebra with generators $u_s$ and the braid relations together with $u_s^2 = 0$; it is the associated graded of the filtration of $H_q(W)$ by length, it has basis $\{u_w\}$ with $u_w = u_{s_1}\cdots u_{s_l}$, and its multiplication is $u_wu_s = u_{ws}$ if $l(ws) = l(w)+1$ and $0$ otherwise.

Proposition. The nilCoxeter algebra is nilpotent, with $u_w = 0$ for $l(w) > l(w_0)$ when $W$ is finite; the $0$-Hecke algebra and the nilCoxeter algebra are related by the change of the idempotent relation, and both are deformations of the same monoid of the reduced words. The algebra $H_q(W)$ is filtered by length with associated graded the nilCoxeter algebra tensored with $k[q^{\pm1}]$.

Proof. The statement on nilpotence follows because a product of more than $l(w_0)$ generators is zero by the rule in a finite $W$; the filtration statement is by the degree in the $T_s$ and the identification of the graded pieces is the rule with the leading term $T_{ws}$.

The Kazhdan–Lusztig Basis

Theorem (Kazhdan–Lusztig, standard). Let $(W,S)$ be a finite Coxeter system and write $\iota$ for the ring involution of $H_q(W)$ with $\iota(q) = q^{-1}$ and $\iota(T_w) = (T_{w^{-1}})^{-1}$. There is a unique basis $\{C'_w : w\in W\}$ of $H_q(W)$ over the Laurent polynomials in $q^{1/2}$ such that

$$ C'_w = \sum_{y\leq w}(-1)^{l(w)-l(y)}q^{(l(w)-l(y))/2}\,P_{y,w}(q)\,T_y , \qquad \iota(C'_w) = C'_w , $$

where $P_{y,w}(q)\in\mathbb{Z}[q]$ are the Kazhdan–Lusztig polynomials, with $P_{w,w} = 1$, with $P_{y,w} = 0$ unless $y\leq w$ and $l(y)\equiv l(w)$ modulo $2$, and with the degree of $P_{y,w}$ at most $(l(w)-l(y)-1)/2$ for $ypositivity is what defines the cells of the algebra.

Definition. For $x,y\in W$ write $x\preceq_L y$ if the coefficient of $C'_x$ in $C'_sC'_y$ is non-zero for some $s\in S$; the equivalence classes of the transitive closure are the left cells, and the analogous relations on the right and on both sides give the right cells and the two-sided cells. A cell representation of $H_q(W)$ is the representation on the span of a left cell.

Proposition. The left cells are the smallest subsets of $W$ stable under the left action of the Hecke algebra in the sense of the cells of the $C'$-basis; each left cell carries a representation of $H_q(W)$ by the action of the basis, and the cell representations are the building blocks of the representation theory of the algebra, with the simple modules appearing as the head of the cell representations when the relevant parameters are specialised.

Proof (outline). The statements are the standard theory of the cells; the stability is a formal consequence of the definitions and the positivity theorem. The identification of the cell representations with the composition factors of the algebra at the specialisations is the content of the Kazhdan–Lusztig conjectures, proved by them, and it uses the identification of the Hecke algebra with a quotient of the enveloping algebra of a complex semisimple Lie algebra, that is with the module category ; the details of that identification belong to the Lie-theoretic development and are not used here.

Example (type $A$). For $W = S_n$ the left cells are the sets of permutations with a fixed descent set, and the cell representations are the representations of $H_q(S_n)$ that are the quantum analogues of the permutation modules on the parabolic subgroups; the Kazhdan–Lusztig polynomials of type $A$ compute the dimensions of the intersection cohomology groups of the Schubert cells, a geometric statement of Part II. The Kazhdan–Lusztig basis is also the point of contact of the Hecke algebra with the Macdonald and Hall–Littlewood polynomials, whose definition uses the action of the Hecke algebra of type $A$ on the polynomial ring and the traces of that action.

Summary

Let $(W,S)$ be a Coxeter system with finite $W$ and let $A = k[q^{\pm1}]$. The Hecke algebra $H_q(W)$ is generated by the $T_s$, $s\in S$, subject to the braid relations of $W$ and the quadratic relations $T_s^2 = (q-1)T_s+q$; at $q = 1$ it is the group algebra $k[W]$, so it is a one-parameter deformation of the group algebra of a Coxeter group. The elements $T_w$, $w\in W$, one for each element, defined from reduced words, form a basis and the algebra is free of rank $\lvert W\rvert$, with the multiplication rule

$$ T_wT_s = T_{ws}\ \ (l(ws) = l(w)+1), \qquad T_wT_s = qT_{ws}+(q-1)T_w\ \ (l(ws) = l(w)-1). $$

The algebra is commutative exactly when the Coxeter graph is disconnected; it is a symmetric algebra and a Frobenius algebra with the trace $\tau$ taking $T_w$ to the coefficient of $T_1$, with respect to which $\langle T_x,T_y\rangle = q^{l(x)}$ when $xy = 1$ and $0$ otherwise, the form being symmetric, nondegenerate and associative, so that the algebra is self-injective. It arises as the algebra $H(G,B)$ of a Tits system with Weyl group $W$ and parameter $q = \lvert BsB/B\rvert$, that is as $\operatorname{End}_{kG}(k[G/B])$, the endomorphism algebra of the permutation module on the cosets of the Borel subgroup, with $GL_n$ over a finite field of $q$ elements of type $A_{n-1}$ as the classical example. By Tits' deformation theorem the algebra is semisimple for characteristic-$0$ coefficients and generic $q$ and its simple modules are in bijection with the irreducible representations of $W$; the trivial and the sign modules are one-dimensional for every $q$; at a root of unity the algebra is not semisimple in general, and its representation theory there is the modular theory of the Hecke algebra, tied to Quantum Groups and to Part III. The specialisation $q = 0$ gives the $0$-Hecke algebra, the monoid algebra of the $0$-Hecke monoid with $\pi_s^2 = \pi_s$ and $\lvert W\rvert$ one-dimensional simple modules, while the relation $u_s^2 = 0$ gives the nilCoxeter algebra, the associated graded of the length filtration. Finally the Kazhdan–Lusztig basis $\{C'_w\}$ with the Kazhdan–Lusztig polynomials $P_{y,w}$ is characterised by a duality and a positivity condition, its multiplication constants are non-negative integral polynomials, and the cells they define organise the representations of the algebra; the deep statements about the cells at specialisations of $q$ useand Part III and are deferred.

Summary of Notation

Symbol	Meaning
$(W,S)$	Coxeter system, simple reflections $S$
$m_{st}$	order of $st$ in $W$
$l(w)$, $\leq$	length function, Bruhat order
$w_0$	longest element of a finite $W$
$q$	Hecke parameter, an indeterminate (no quadratic form occurs here)
$A = k[q^{\pm1}]$	ring of Laurent polynomials
$H_q(W)$	Hecke algebra, free of rank $\lvert W\rvert$
$T_s$, $T_w$	generators, standard basis, $T_s^2 = (q-1)T_s+q$
$\tau$, $\langle-,-\rangle$	trace, $\tau(T_w) = \delta_{w,1}$; symmetrising form
$\langle T_x,T_y\rangle = q^{l(x)}\delta_{y,x^{-1}}$	evaluation of the symmetrising form
$H(G,B)$, $k[G/B]$	Hecke algebra of a Tits system, permutation module
$H_0(W)$, $\pi_s$, $\pi_w$	$0$-Hecke algebra and monoid, $\pi_s^2 = \pi_s$
$N(W)$, $u_s$, $u_w$	nilCoxeter algebra, $u_s^2 = 0$
$C'_w$, $P_{y,w}$	Kazhdan–Lusztig basis and polynomials
$\preceq_L$, left/right/two-sided cells	cell structure from the $C'$-basis