![[prev]](go_prev_btn.gif)
In this chapter we describe functions for dealing with finite Weyl groups, associated Hecke algebras over a ring of Laurent polynomials, and their representations.
A finite Weyl group is a group with a presentation of the form langles_1, ..., s_n | (s_i s_j)^(m(i,j))=1 for all i, j rangle where the m(i,j) are integers contained in { 2, 3, 4, 6 } and where m(i,i)=1 for all i. These groups play a significant role in various areas of mathematics such as reflection groups, Lie algebras and linear algebraic groups. Each Weyl group is a direct product of indecomposable Weyl groups which are in turn classified by means of the well--known Dynkin diagrams.
The Hecke algebra H corresponding to a finite Weyl group as above is defined as follows. Let A be a commutative ring and q_1, ..., q_n inA such that q_i=q_j whenever s_i and s_j are conjugate in W. Then H is the associative A--algebra with 1 with generators a_1, ..., a_n and defining relations of the form a_i^2=q_i 1 + (q_i-1) a_i for all i and a_i a_j a_i ... = a_j a_i a_j ... m(i,j) factors on each side.
Usually, A is chosen to be the ring of Laurent polynomials in an indeterminate v, and all q_i are chosen to be v^2. For each w inW we define an element T_w inH as follows. If w=s_(i_1) cdotss_(i_k) is a reduced expression, for some for some i_j in{1,ldots,n}, then we let T_w := T_(a_(i_1)) cdotsT_(a_(i_k)). It can be shown that T_w is indeed independent of the choice of the reduced expression. The elements T_w, w inW, form an A--basis of the algebra H.
A suitable reference for the general theory is, for example, the book by J.E.Humpreys on `Reflection Groups and Coxeter Groups' (Cambridge Studies in advanced Mathematics 29). A good reference for applications of Weyl groups and Hecke algebras are Chapters 1,2 in the book by Shi Jian-Yi on `The Kazhdan-Lusztig Cells in Certain Affine Weyl Groups' (Springer Lecture Notes in Mathematics 1179).
At first, let us describe in an informal way some examples of how these programs can be used.
The starting point for our programs is to specify a Cartan matrix. This is a
square matrix corresponding to a (finite) root system R in some
Euclidean space V with (i,j)-entry given by 2(r_i,r_j)/(r_i,r_i)
where r_i and r_j are fundamental roots in R. The
Cartan matrices for the indecomposable root system of type A_n, B_n,
C_n, D_n, G_2, F_4, E_6, E_7,
E_8 are accessible through the function CartanMat.
gap> RequirePackage( "weyl" );
gap> C := CartanMat( "D", 4 );;
gap> PrintArray( last );
[ [ 2, 0, -1, 0 ],
[ 0, 2, -1, 0 ],
[ -1, -1, 2, -1 ],
[ 0, 0, -1, 2 ] ]
The Cartan matrices corresponding to the non-crystallographic groups are now
also available under the names H_3, H_4 and I_2(m).
Given two Cartan matrices, their matrix direct sum (corresponding to the
orthogonal direct sum of the root systems) is produced by using the function
DirectSumCartanMat. This Cartan matrix conversely determines the
root system and hence also the corresponding Weyl group W, i.e., the
finite subgroup of the full orthogonal group of V generated by the
reflections along the vectors in R. We choose a basis of V
consisting of the fundamental root vectors, and express every root vector as
a linear combination of and every reflection matrix with respect to this
basis. This is performed by the functions RootSystem and SimpleReflectionMatrices.
gap> S:=SimpleReflectionMatrices(C);
[ [ [ -1, 0, 0, 0 ], [ 0, 1, 0, 0 ], [ 1, 0, 1, 0 ], [ 0, 0, 0, 1 ] ],
[ [ 1, 0, 0, 0 ], [ 0, -1, 0, 0 ], [ 0, 1, 1, 0 ], [ 0, 0, 0, 1 ] ],
[ [ 1, 0, 1, 0 ], [ 0, 1, 1, 0 ], [ 0, 0, -1, 0 ], [ 0, 0, 1, 1 ] ],
[ [ 1, 0, 0, 0 ], [ 0, 1, 0, 0 ], [ 0, 0, 1, 1 ], [ 0, 0, 0, -1 ] ] ]
gap> R := Rootsystem(C);
[ [ 1, 0, 0, 0 ], [ 0, 1, 0, 0 ], [ 0, 0, 1, 0 ], [ 0, 0, 0, 1 ],
[ 1, 0, 1, 0 ], [ 0, 1, 1, 0 ], [ 0, 0, 1, 1 ], [ 1, 1, 1, 0 ],
[ 1, 0, 1, 1 ], [ 0, 1, 1, 1 ], [ 1, 1, 1, 1 ], [ 1, 1, 2, 1 ] ]
We notice that the root vectors in R are ordered by increasing
height (and that only the positive root vectors are returned; whenever the
negative roots are needed, they can be computed by simply typing -R).
If we label the (positive) roots by their position in the above list, and the
negative roots by the next consecutive numbers, then we can also represent
each fundamental reflection by the permutation which it induces on the root
vectors.
gap> P := PermRepresentationRoots( S, R );
[ ( 1,13)( 3, 5)( 6, 8)( 7, 9)(10,11)(15,17)(18,20)(19,21)(22,23),
( 2,14)( 3, 6)( 5, 8)( 7,10)( 9,11)(15,18)(17,20)(19,22)(21,23),
( 1, 5)( 2, 6)( 3,15)( 4, 7)(11,12)(13,17)(14,18)(16,19)(23,24),
( 3, 7)( 4,16)( 5, 9)( 6,10)( 8,11)(15,19)(17,21)(18,22)(20,23) ]
This is maybe the most fundamental command, and in fact, every function which has to perform computations with group elements in W, does so by working with this (faithful) permutation representation of W. The procedure up to now can be abbreviated by one command, namely
gap> W := Weyl(C);;
which produces a record with entries:
isWeylGroup:
is set to true.
cartan:
contains the Cartan matrix C.
dim:
contains the length of C.
degree:
number of positive and negative roots.
N:
number of positive roots.
roots:
contains the root system R.
matgens:
contains the matrix generators S.
permgens:
contains the permutation generators P.
This record is all that the following programs and commands need. For a given
element w inW, the length l(w) is defined
to be smallest integer k such that w can be written as a
product of k fundamental reflections. Such an expression of shortest
possible length will be called a reduced word for w. A user might be
interested to think of the elements of W as such words in the
generating fundamental reflections. For these programs, we represent a word
simply as a list of integers corresponding to the fundamental roots, e.g.,
[] is the identity element, and [1], [2], etc.
represent the reflection along the first, the second etc. fundamental root
vector. For other purposes, it might be better to see the permutation of an
element w on the root vectors. The functions WeylWordPerm
and PermWeylWord will do the conversion of one form into the
other.
gap> PermWeylWord( W, [ 1, 3, 2, 1, 3 ] );
( 1,14,13, 2)( 3,17, 8,18)( 4,12)( 5,20, 6,15)( 7,10,11, 9)(16,24)
(19,22,23,21)
gap> WeylWordPerm( W, last );
[ 1, 3, 1, 2, 3 ]
We notice that the word we started with and the one that we ended up with,
are not the same. But of course, they represent the same element of W.
The reason for this difference is that the function WeylWordPerm
always computes a reduced word which is the lexicographically smallest among
all possible expressions of an element of W as a word in the
fundamental reflections! The function ReducedWeylWord does the
same but with an arbitrary word as input (and not with a permutation). In
particular, the element used in the above example has length 5. Sometimes, it
is not necessary to compute a reduced word for an element w and one
is only interested in the length l(w). The crucial point of working
with the permutation representation of W on R is that l(w)
can be computed very fast and effectively from the permutation, since it also
given by the number of positive roots mapped to negative roots by w,
i.e., by the number of i in{ 1,... ,N } such that
i^w > N.
gap> LongestWeylWord( W ); # the (unique) longest element in W
[ 1, 2, 3, 1, 2, 3, 4, 3, 1, 2, 3, 4 ]
gap> PermWeylWord( W, last );
( 1,13)( 2,14)( 3,15)( 4,16)( 5,17)( 6,18)( 7,19)( 8,20)( 9,21)(10,22)
(11,23)(12,24)
gap> WeylLengthPerm( W, last );
12
These are the most basic functions available. We now give an example of how the other commands do work.
gap> WeylReflections( W ); # all reflections in W
[ [ 1 ], [ 2 ], [ 3 ], [ 4 ], [ 1, 3, 1 ], [ 2, 3, 2 ], [ 3, 4, 3 ],
[ 1, 2, 3, 1, 2 ], [ 1, 3, 4, 3, 1 ], [ 2, 3, 4, 3, 2 ],
[ 1, 2, 3, 4, 3, 1, 2 ], [ 3, 1, 2, 3, 4, 3, 1, 2, 3 ] ]
gap> WeylElements( W );;
#I Order = 192
gap> List( last, Length );
[ 1, 4, 9, 16, 23, 28, 30, 28, 23, 16, 9, 4, 1 ]
The last line tells us that there is 1 element of length 0, there are 4 elements of length 4, etc.
gap> WeylConjugacyClasses( W );
#I Number of cosets = 8
#I Number of cosets = 6
#I Number of cosets = 2
#I 30 elements to consider
#I Still 18 elements to consider
#I 13 conjugacy classes found
[ [ ], [ 1 ], [ 1, 2 ], [ 1, 3 ], [ 1, 4 ], [ 2, 4 ], [ 1, 2, 3 ],
[ 1, 2, 4 ], [ 1, 3, 4 ], [ 2, 3, 4 ], [ 1, 2, 3, 4 ],
[ 1, 3, 1, 2, 3, 4 ], [ 1, 2, 3, 1, 2, 3, 4, 3, 1, 2, 3, 4 ] ]
This are the representatives of the conjugacy classes of minimal length.
gap> LeftCells( W );;
#I Order = 192
#I R(w) = [ ] : Size = 1, 1 new cell
#I R(w) = [ 1 ] : Size = 7, 2 new cells
#I R(w) = [ 1, 2 ] : Size = 17, 2 new cells
#I R(w) = [ 1, 2, 3 ] : Size = 7, 2 new cells
#I R(w) = [ 1, 2, 3, 4 ] : Size = 1, 1 new cell
#I R(w) = [ 1, 2, 4 ] : Size = 23, 5 new cells
#I R(w) = [ 1, 3 ] : Size = 17, 2 new cells
#I R(w) = [ 1, 3, 4 ] : Size = 7, 2 new cells
#I R(w) = [ 1, 4 ] : Size = 17, 2 new cells
#I R(w) = [ 2 ] : Size = 7, 2 new cells
#I R(w) = [ 2, 3 ] : Size = 17, 2 new cells
#I R(w) = [ 2, 3, 4 ] : Size = 7, 2 new cells
#I R(w) = [ 2, 4 ] : Size = 17, 2 new cells
#I R(w) = [ 3 ] : Size = 23, 5 new cells
#I R(w) = [ 3, 4 ] : Size = 17, 2 new cells
#I R(w) = [ 4 ] : Size = 7, 2 new cells
gap> last[3];
[ [ [ 2, 4, 3, 1 ], [ 3, 2, 4, 3, 1 ], [ 1, 3, 2, 4, 3, 1 ] ],
[ [ 0 ], [ 1, 0 ], [ 0, 1, 0 ] ] ]
This is a left cell consisting of three elements with the corresponding matrix of mu_(x,y), the coefficient of v^((l(y)-l(x)-1)) in the Kazhdan-Lusztig polynomial P_(x,y)(v^2).
gap> LeftCellRepresentation( W, last, E(4) );;
gap> PrintArray( last );
[ [ [ -1, 0, 0 ], [ 0, -1, 0 ], [ 0, E(4), -1 ] ],
[ [ -1, E(4), 0 ], [ 0, -1, 0 ], [ 0, 0, -1 ] ],
[ [ -1, 0, 0 ], [ E(4), -1, E(4) ], [ 0, 0, -1 ] ],
[ [ -1, E(4), 0 ], [ 0, -1, 0 ], [ 0, 0, -1 ] ] ]
The corresponding left cell representation with the indeterminate v
replaced by E(4).
Of course, the user should observe limitations on storage for working with
these programs, e.g., the command WeylElements applied to a Weyl
group of type E_8 will try to compute all elements as words in the
fundamental reflections. Every computer will run out of memory!
Some good examples to see how long the programs will take for computations in big Weyl groups are the following.
LeftCells( Weyl( CartanMat( "F", 4 ) ) );
(which takes roughly 5 hours cpu time on a HP computer)
or
WeylConjugacyClasses( Weyl( CartanMat( "E", 8 ) ) ) ;
(which takes a few days...)
Finally, we give an example of some computations with Hecke algebras. We start with the Weyl group of type A_4.
gap> W := Weyl( CartanMat("A",4) );;
We wish to work over the ring of Laurent polynomials in an indeterminate v, and we want to have u=v^2 as a parameter for the generic Hecke algebra H of W.
gap> v := Indeterminate( Rationals );; v.name := "v";;
gap> Hecke( W, v^2 );
From v we can build arbitrary Laurent polynomials by using the
operations +, -, *, and ^.
gap> 2*v+3*v^-2-7*(v+v^-1)*(3*v^2-1);
-21*v^3 - 12*v + 7*v^(-1) + 3*v^(-2)
The command Hecke produces an additional component T
in the record of W which gives, for an element w inW,
the corresponding basis element T_w in H. Computations like
the following are possible.
gap> W.T([1]);
(v^0)*T([ 1 ])
gap> last^2; # the quadratic relation for a standard base element
(v^2)*T([ ])+(v^2 - 1)*T([ 1 ])
gap> h := W.T([1,2,3,4]);
(v^0)*T([ 1, 2, 3, 4 ])
gap> inv := h^-1;
(1 - 4*v^(-2) + 6*v^(-4) - 4*v^(-6) + v^(-8))*T([ ])+(-v^(-2) + 3*v^(
-4) - 3*v^(-6) + v^(-8))*T([ 1 ])+(-v^(-2) + 3*v^(-4) - 3*v^(-6) + v^(
-8))*T([ 2 ])+(-v^(-2) + 3*v^(-4) - 3*v^(-6) + v^(-8))*T([ 3 ])+(-v^(
-2) + 3*v^(-4) - 3*v^(-6) + v^(-8))*T([ 4 ])+(v^(-4) - 2*v^(-6) + v^(
-8))*T([ 1, 3 ])+(v^(-4) - 2*v^(-6) + v^(-8))*T([ 1, 4 ])+(v^(-4) -
2*v^(-6) + v^(-8))*T([ 2, 1 ])+(v^(-4) - 2*v^(-6) + v^(-8))*T(
[ 2, 4 ])+(v^(-4) - 2*v^(-6) + v^(-8))*T([ 3, 2 ])+(v^(-4) - 2*v^(
-6) + v^(-8))*T([ 4, 3 ])+(-v^(-6) + v^(-8))*T([ 1, 4, 3 ])+(-v^(
-6) + v^(-8))*T([ 2, 1, 4 ])+(-v^(-6) + v^(-8))*T([ 3, 2, 1 ])+(-v^(
-6) + v^(-8))*T([ 4, 3, 2 ])+(v^(-8))*T([ 4, 3, 2, 1 ])
gap> h*inv;
(v^0)*T([ ])
More clearly arranged, h is
(1 - 4*v^(-2) + 6*v^(-4) - 4*v^(-6) + v^(-8))*T([ ])
+(-v^(-2) + 3*v^(-4) - 3*v^(-6) + v^(-8))*T([ 1 ])
+(-v^(-2) + 3*v^(-4) - 3*v^(-6) + v^(-8))*T([ 2 ])
+(-v^(-2) + 3*v^(-4) - 3*v^(-6) + v^(-8))*T([ 3 ])
+(-v^(-2) + 3*v^(-4) - 3*v^(-6) + v^(-8))*T([ 4 ])
+(v^(-4) - 2*v^(-6) + v^(-8))*T([ 1, 3 ])
+(v^(-4) - 2*v^(-6) + v^(-8))*T([ 1, 4 ])
+(v^(-4) - 2*v^(-6) + v^(-8))*T([ 2, 1 ])
+(v^(-4) - 2*v^(-6) + v^(-8))*T([ 2, 4 ])
+(v^(-4) - 2*v^(-6) + v^(-8))*T([ 3, 2 ])
+(v^(-4) - 2*v^(-6) + v^(-8))*T([ 4, 3 ])
+(-v^(-6) + v^(-8))*T([ 1, 4, 3 ])
+(-v^(-6) + v^(-8))*T([ 2, 1, 4 ])
+(-v^(-6) + v^(-8))*T([ 3, 2, 1 ])
+(-v^(-6) + v^(-8))*T([ 4, 3, 2 ])
+(v^(-8))*T([ 4, 3, 2, 1 ])
Now we turn to some aspects about the representation theory of Hecke algebras. At first we compute the left cells of W.
gap> ce := LeftCells(W);;
#I Order = 120
#I R(w) = [ ] : Size = 1, 1 new cell
#I R(w) = [ 1 ] : Size = 4, 1 new cell
#I R(w) = [ 1, 2 ] : Size = 6, 1 new cell
#I R(w) = [ 1, 2, 3 ] : Size = 4, 1 new cell
#I R(w) = [ 1, 2, 3, 4 ] : Size = 1, 1 new cell
#I R(w) = [ 1, 2, 4 ] : Size = 9, 2 new cells
#I R(w) = [ 1, 3 ] : Size = 16, 3 new cells
#I R(w) = [ 1, 3, 4 ] : Size = 9, 2 new cells
#I R(w) = [ 1, 4 ] : Size = 11, 2 new cells
#I R(w) = [ 2 ] : Size = 9, 2 new cells
#I R(w) = [ 2, 3 ] : Size = 11, 2 new cells
#I R(w) = [ 2, 3, 4 ] : Size = 4, 1 new cell
#I R(w) = [ 2, 4 ] : Size = 16, 3 new cells
#I R(w) = [ 3 ] : Size = 9, 2 new cells
#I R(w) = [ 3, 4 ] : Size = 6, 1 new cell
#I R(w) = [ 4 ] : Size = 4, 1 new cell
We use LeftCellRepresentation to get the corresponding left
cell representations.
gap> l := List( last, i -> LeftCellRepresentation(W,i,v) );;
gap> c := WeylConjugacyClasses(W);
[ [ ], [ 1 ], [ 1, 3 ], [ 1, 2 ], [ 1, 2, 4 ], [ 1, 2, 3 ],
[ 1, 2, 3, 4 ] ]
gap> ch := List( l, i -> CharHeckeRepresentation(i,c) );;
The last command computes the character values on representatives of minimal length in the conjugacy classes.
gap> Set(last);
[ [ v^0, -v^0, v^0, v^0, -v^0, -v^0, v^0 ],
[ v^0, v^2, v^4, v^4, v^6, v^6, v^8 ],
[ 4*v^0, v^2 - 3, -2*v^2 + 2, -v^2 + 2, 2*v^2 - 1, v^2 - 1, -v^2 ],
[ 4*v^0, 3*v^2 - 1, 2*v^4 - 2*v^2, 2*v^4 - v^2, v^6 - 2*v^4,
v^6 - v^4, -v^6 ],
[ 5*v^0, 2*v^2 - 3, v^4 - 2*v^2 + 2, -2*v^2 + 1, -v^4 + v^2 - 1,
v^2, 0*v^0 ],
[ 5*v^0, 3*v^2 - 2, 2*v^4 - 2*v^2 + 1, v^4 - 2*v^2, v^6 - v^4 + v^2,
-v^4, 0*v^0 ],
[ 6*v^0, 3*v^2 - 3, v^4 - 4*v^2 + 1, v^4 - 2*v^2 + 1,
-2*v^4 + 2*v^2, -v^4 + v^2, v^4 ] ]
HeckeCharTable constructs a record of a character table, which
can be displayed using DisplayCharTable.
gap> t := HeckeCharTable( W, c, last );;
gap> DisplayCharTable(t);
H()
2 3 2 3 1 1 2 .
3 1 1 . 1 1 . .
5 1 . . . . . 1
1a 2a 2b 3a 6a 4a 5a
X.1 1 -1 1 1 -1 -1 1
X.2 1 v^2 v^4 v^4 v^6 v^6 v^8
X.3 4 v^2-3 -2v^2+2 -v^2+2 2v^2-1 v^2-1 -v^2
X.4 4 3v^2-1 2v^4-2v^2 2v^4-v^2 v^6-2v^4 v^6-v^4 -v^6
X.5 5 2v^2-3 v^4-2v^2+2 -2v^2+1 -v^4+v^2-1 v^2 0
X.6 5 3v^2-2 2v^4-2v^2+1 v^4-2v^2 v^6-v^4+v^2 -v^4 0
X.7 6 3v^2-3 v^4-4v^2+1 v^4-2v^2+1 -2v^4+2v^2 -v^4+v^2 v^4
To compute character values on other elements, we proceed as follows.
gap> w0 := LongestWeylWord(W);
[ 1, 2, 1, 3, 2, 1, 4, 3, 2, 1 ]
gap> wcl := WeylClassPolynomials( W, c, last );
[ 0, 0, v^8, v^10 - 2*v^8 + v^6, v^10 - v^8 + v^6 - v^4,
v^12 - v^10 + v^4 - v^2, v^12 - v^10 - v^2 + 1 ]
In order to get the values of the irreducible characters on T_(w_0),
we have to postmultiply the character table of H by wcl
regarded as a column vector:
gap> tr := TransposedMat([wcl]) * v^0;;
gap> t.irreducibles * tr;
[ [ v^0 ], [ v^20 ], [ 0*v^0 ], [ 0*v^0 ], [ v^8 ], [ v^12 ],
[ -2*v^10 ] ]
For any comments, suggestions of improvements I would be very grateful,
hfillAachen, November 1992, Meinolf Geck
newpage
This chapter contains the following sections:
![[up]](go_up_btn.gif)