Let (W,S) be a finite Coxeter system as in the previous chapter. For a
given element w in W, the length l(w) is defined to be the 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 computational
purposes, it might be better to use the permutation of an element w on
the root vectors. The functions CoxeterWord
and PermCoxeterWord
will
do the conversion of one form into the other.
gap> W := CoxeterGroup( "D", 4 );; gap> p := PermCoxeterWord( 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> CoxeterWord( W, p ); [ 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 CoxeterWord
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 ReducedCoxeterWord
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); this can be computed
very effectively from the permutation, since it is also given by the
number of positive roots mapped to negative roots by w, i.e., by the
number of i in {1,ldots,N} such that i^w > N. This is what does
the function CoxeterLength
in the following example where we also show
how to compute the unique element of maximal length in W.
gap> LongestCoxeterWord( W ); # the (unique) longest element in W [ 1, 2, 3, 1, 2, 3, 4, 3, 1, 2, 3, 4 ] gap> w0 := LongestCoxeterElement( W ); # = PermCoxeterWord( 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> CoxeterLength( W, w0 ); 12
There is another way of computing a reduced word which is more canonical
for some purposes. For any set I of generators, let w_I be the
unique element of maximal length which can be made in the generators I.
(Note that this element is an involution.) Now take any w in W and
compute the set L(w) of all generators s such that l(sw)
We give an example of some other commands:
The last line tells us that there is 1 element of length 0, there are 4
elements of length 4, etc.
For many basic functions (like
returns the permutation on the root vectors determined by an element
which is given as a list w of integers representing the standard
generators of the Coxeter group W.
See also CoxeterWord.
This function requires the package "chevie" (see RequirePackage).
returns a reduced word in the standard generators of the Coxeter group
W determined by the permutation w on the root vectors.
For the definition of the Brieskorn normal form, see the introduction to
this chapter. If the global variable
See also PermCoxeterWord and ReducedCoxeterWord.
This function requires the package "chevie" (see RequirePackage).
returns the length of the permutation w, which corresponds to an
element in the Coxeter group W, as a reduced expression in the standard
generators.
returns a reduced expression for an element of the Coxeter group W,
which is given as a list w of integers where each entry
This function requires the package "chevie" (see RequirePackage).
The set of generators s such that l(sw)
See also RightDescentSet.
This function requires the package "chevie" (see RequirePackage).
The set of generators s such that l(ws)< l(w), given as a list of
integers.
See also LeftDescentSet.
This function requires the package "chevie" (see RequirePackage).
returns the set of reflections in the Coxeter group W (as
permutations). The
This function requires the package "chevie" (see RequirePackage).
returns the unique element of maximal length of the Coxeter group W as
a permutation.
This function requires the package "chevie" (see RequirePackage).
returns a reduced expression in the standard generators for the unique
element of maximal length of the Coxeter group W.
This function requires the package "chevie" (see RequirePackage).
Let W be an irreducible Coxeter group.
This function requires the package "chevie" (see RequirePackage).
returns as a list of permutations the list of all elements of W of
length l.
The result of the computation of elements of a given length is stored in
the component
This function requires the package "chevie" (see RequirePackage).
returns the list of all elements in the Coxeter group W. The ordering
is the same as that given by concatenating the lists of elements of
length 0,1,ldots obtained by the function
This function requires the package "chevie" (see RequirePackage).
returns a list of representatives of the conjugacy classes of the Coxeter
group W. Each element in this list is given as a word in the standard
generators, where the generator s_i is represented by the number i in
a list. Each representative has the property that it is of minimal
length in its conjugacy class.
This function requires the package "chevie" (see RequirePackage).
returns information about the conjugacy classes of the finite Coxeter
group W. The result is a record with three components:
For a general description of the conjugacy classes in the Weyl groups,
see Car72. The relevance of taking representatives of minimal
length is explained in GP93.
See also ChevieCharInfo.
This function requires the package "chevie" (see RequirePackage).
returns
This function requires the package "chevie" (see RequirePackage).
Let w be a permutation of the roots of the Coxeter datum W acting on
the vector space V.
This function requires the package "chevie" (see RequirePackage).
Let w be a permutation of the roots of the Coxeter datum W acting on
the vector space Vdual.
We continue the example from
This function requires the package "chevie" (see RequirePackage).
Let M be a linear transformation of the vector space V on which the
Coxeter datum W acts which preserves the set of roots.
We continue the example from
This function requires the package "chevie" (see RequirePackage).
Let M be a linear transformation of the vector space Vdual on which
the Coxeter datum W acts which preserves the set of coroots.
We continue the example from
This function requires the package "chevie" (see RequirePackage).
LeftDescentSet
. Brieskorn
Bri71 has noticed that w_{L(w)} divides w, in the sense that
l(w_{L(w)})+l(w_{L(w)}w)=l(w). We can now divide w by w_{L(w)} and
continue this process with the quotient. In this way, we obtain a
reduced expression w=w_{L_1} cdots w_{L_r} where L_i=L(w_{L_i} cdots
w_{L_r}) for all i, which we call the Brieskorn normal form of w
(and where we use the lexicographically smallest expression for each
w_{L_i}). The CHEVIE package will use this form if you set
CHEVIE.BrieskornNormalForm:= true;
. When you load CHEVIE this
variable is initialized with false
(see also CoxeterWord).
gap> List( Reflections( W ), i -> CoxeterWord( W, i ) );
[ [ 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 ], [ 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> l := List( [1 .. W.N+1], x -> CoxeterElementsLength( W, x-1 ) );;
gap> List( l, Length );
[ 1, 4, 9, 16, 23, 28, 30, 28, 23, 16, 9, 4, 1 ]
CoxeterElementsLength
, Reflections
,
Bruhat
, etc.) we have chosen the convention that if the input is an
element of a Coxeter group, then this element should by given as a
permutation (and similarly for the output). As a rule of thumb one
should keep in mind that, if in some application one has to do a lot of
computations with Coxeter group elements then using the low level GAP
functions for permutations is usually much faster than manipulating
lists of reduced expressions. For example, suppose we are given an
element w in W and a generator s_i and we want to check if
l(s_iw)i^wW.N
than to work with a
reduced expression and check the condition
Length( ReducedCoxeterWord( W, Concatenation( [i], w ) ) )
Subsections
76.1 PermCoxeterWord
PermCoxeterWord( W , w )
gap> W := CoxeterGroup( "G", 2 );;
gap> PermCoxeterWord( W, [1,2,1] );
( 1,12)( 2, 4)( 3, 9)( 6, 7)( 8,10)
CoxeterWord( W , w )
gap> W := CoxeterGroup( "A", 3 );;
gap> w := ( 1,11)( 3,10)( 4, 9)( 5, 7)( 6,12);;
gap> w in W;
true;
gap> CHEVIE.BrieskornNormalForm := true;;
gap> CoxeterWord( W, w );
[ 1, 3, 2, 1, 3 ]
gap> CHEVIE.BrieskornNormalForm := false;;
gap> CoxeterWord( W, w );
[ 1, 2, 3, 2, 1 ]
CHEVIE.BrieskornNormalForm
is set
to false
(which is automatically the case when you load CHEVIE),
the result of CoxeterWord
is the lexicographically smallest reduced
word for~w.
CoxeterLength( W , w )
gap> W := CoxeterGroup( "F", 4 );;
gap> p := PermCoxeterWord( W, [ 1, 2, 3, 4, 2 ] );
( 1,44,38,25,20,14)( 2, 5,40,47,48,35)( 3, 7,13,21,19,15)
( 4, 6,12,28,30,36)( 8,34,41,32,10,17)( 9,18)(11,26,29,16,23,24)
(27,31,37,45,43,39)(33,42)
gap> CoxeterLength( W, p );
5
gap> CoxeterWord( W, p );
[ 1, 2, 3, 2, 4 ]
This function requires the package "chevie" (see RequirePackage).
ReducedCoxeterWord( W , w )
i
in this
list represents the i
-th standard generator of W.
gap> W := CoxeterGroup( "E", 6 );;
gap> ReducedCoxeterWord( W, [ 1, 1, 1, 1, 1, 2, 2, 2, 3 ] );
[ 1, 2, 3 ]
LeftDescentSet( W, w )
gap> W := CoxeterGroup( "A", 2 );;
gap> w := PermCoxeterWord( W, [ 1, 2 ] );;
gap> LeftDescentSet( W, w );
[ 1 ]
RightDescentSet( W, w )
gap> W := CoxeterGroup( "A", 2 );;
gap> w := PermCoxeterWord( W, [ 1, 2 ] );;
gap> RightDescentSet( W, w );
[ 2 ]
Reflections( W )
i
-th entry in this list is the reflection along the
i
-th root in W.roots
.
gap> W := CoxeterGroup( "B", 2 );; W.roots;
[ [ 1, 0 ], [ 0, 1 ], [ 1, 1 ], [ 2, 1 ], [ -1, 0 ], [ 0, -1 ],
[ -1, -1 ], [ -2, -1 ] ]
gap> Reflections( W );
[ (1,5)(2,4)(6,8), (1,3)(2,6)(5,7), (2,8)(3,7)(4,6), (1,7)(3,5)(4,8),
(1,5)(2,4)(6,8), (1,3)(2,6)(5,7), (2,8)(3,7)(4,6), (1,7)(3,5)(4,8) ]
LongestCoxeterElement( W )
gap> LongestCoxeterElement( CoxeterGroup( "A", 4 ) );
( 1,14)( 2,13)( 3,12)( 4,11)( 5,17)( 6,16)( 7,15)( 8,19)( 9,18)(10,20)
LongestCoxeterWord( W )
gap> LongestCoxeterWord( CoxeterGroup( "A", 4 ) );
[ 1, 2, 1, 3, 2, 1, 4, 3, 2, 1 ]
HighestShortRoot( W )
HighestShortRoot
computes the
unique short root of maximal height of W. Note that if all roots have
the same length then this is the unique root of maximal height, which can
also be obtained by W.roots[W.N]
. An error message is returned for W
not irreducible.
gap> W := CoxeterGroup( "G", 2 );; W.roots;
[ [ 1, 0 ], [ 0, 1 ], [ 1, 1 ], [ 1, 2 ], [ 1, 3 ], [ 2, 3 ],
[ -1, 0 ], [ 0, -1 ], [ -1, -1 ], [ -1, -2 ], [ -1, -3 ],
[ -2, -3 ] ]
gap> HighestShortRoot( W );
4
gap> W1 := CoxeterGroup( "A", 1, "B", 3 );;
gap> HighestShortRoot( W1 );
Error, group is not irreducible
in
HighestShortRoot( W1 ) called from
main loop
brk>
CoxeterElementsLength( W, l )
gap> W := CoxeterGroup( "G", 2 );;
gap> e := CoxeterElementsLength( W, 6 );
[ ( 1, 7)( 2, 8)( 3, 9)( 4,10)( 5,11)( 6,12) ]
gap> e[1] = LongestCoxeterElement( W );
true
elts
of the record of W. Thus W.elts[lw+1]
contains
the list of all elements of length lw in W. There are a number of
Kazhdan-Lusztig polynomials and bases) which refer to the ordering of the elements in these lists in
W.elts
.
CoxeterWords( W )
CoxeterElementsLength
.
gap> CoxeterWords( CoxeterGroup( "G", 2 ) );
[ [ ], [ 2 ], [ 1 ], [ 2, 1 ], [ 1, 2 ], [ 2, 1, 2 ], [ 1, 2, 1 ],
[ 2, 1, 2, 1 ], [ 1, 2, 1, 2 ], [ 2, 1, 2, 1, 2 ],
[ 1, 2, 1, 2, 1 ], [ 1, 2, 1, 2, 1, 2 ] ]
CoxeterConjugacyClasses( W )
gap> CoxeterConjugacyClasses( CoxeterGroup( "F", 4 ) );
[ [ ],
[ 1, 2, 1, 3, 2, 1, 3, 2, 3, 4, 3, 2, 1, 3, 2, 3, 4, 3, 2, 1, 3, 2,
3, 4 ], [ 2, 3, 2, 3 ], [ 2, 1 ],
[ 2, 3, 2, 3, 4, 3, 2, 1, 3, 4 ],
[ 3, 2, 4, 3, 2, 1, 3, 2, 4, 3, 2, 1 ], [ 4, 3 ],
[ 1, 2, 1, 4, 3, 2, 1, 3, 2, 3 ],
[ 3, 2, 1, 4, 3, 2, 1, 3, 2, 3, 4, 3, 2, 1, 3, 2 ],
[ 3, 2, 4, 3, 2, 1, 3, 2 ], [ 4, 3, 2, 1 ], [ 1 ],
[ 2, 3, 2, 3, 4, 3, 2, 3, 4 ], [ 1, 4, 3 ], [ 4, 3, 2 ],
[ 2, 3, 2, 1, 3 ], [ 3 ], [ 1, 2, 1, 3, 2, 1, 3, 2, 3 ],
[ 2, 1, 4 ], [ 3, 2, 1 ], [ 2, 4, 3, 2, 3 ], [ 1, 3 ], [ 3, 2 ],
[ 2, 3, 2, 3, 4, 3, 2, 1, 3, 2, 4, 3, 2, 1 ], [ 2, 4, 3, 2, 1, 3 ] ]
See also ChevieClassInfo.
ChevieClassInfo( W )
classtext
contains CoxeterConjugacyClass(W)
, classnames
contains
corresponding names for the classes, and classparams
gives
Character tables for Coxeter groups).
gap> W := CoxeterGroup( "D", 4 );;
gap> ChevieClassInfo( W );
rec(
classtext :=
[ [ ], [ 1, 2 ], [ 1, 2, 3, 1, 2, 3, 4, 3, 1, 2, 3, 4 ], [ 1 ],
[ 1, 2, 3 ], [ 1, 2, 4 ], [ 1, 4 ], [ 2, 4 ],
[ 1, 3, 1, 2, 3, 4 ], [ 1, 3 ], [ 1, 2, 3, 4 ], [ 1, 3, 4 ],
[ 2, 3, 4 ] ],
classparams :=
[ [ [ [ 1, 1, 1, 1 ], [ ] ] ], [ [ [ 1, 1 ], [ 1, 1 ] ] ],
[ [ [ ], [ 1, 1, 1, 1 ] ] ], [ [ [ 2, 1, 1 ], [ ] ] ],
[ [ [ 1 ], [ 2, 1 ] ] ], [ [ [ 2 ], [ 1, 1 ] ] ],
[ [ [ 2, 2 ], '+' ] ], [ [ [ 2, 2 ], '-' ] ],
[ [ [ ], [ 2, 2 ] ] ], [ [ [ 3, 1 ], [ ] ] ],
[ [ [ ], [ 3, 1 ] ] ], [ [ [ 4 ], '+' ] ], [ [ [ 4 ], '-' ] ] ]
,
classnames := [ "1111.", "11.11", ".1111", "211.", "1.21", "2.11",
"22.+", "22.-", ".22", "31.", ".31", "4.+", "4.-" ] )
Bruhat( W, y, w[, ly, lw] )
true
, if the element y is less than or equal to the element
w of the Coxeter group W for the Bruhat order, and false
otherwise
(y is less than w if a reduced expression for y can be extracted
from one for w). Both y and w must be given as permutations on the
root vectors of W. The optional arguments ly, lw can contain the
length of the elements y and w. (In a computation with many calls to
Bruhat
this may speed up the computation considerably.) See cite[(5.9)
and (5.10)]Hum90 for further properties of the Bruhat order.
gap> W := CoxeterGroup( "H", 3 );;
gap> w := PermCoxeterWord( W, [ 1, 2, 1, 3 ] );;
gap> b := Filtered( Elements( W ), i -> Bruhat( W, i, w,
> CoxeterLength( W, i ), 4 ) );;
gap> List( b, x -> CoxeterWord( W, x ) );
[ [ ], [ 3 ], [ 2 ], [ 2, 1 ], [ 2, 3 ], [ 2, 1, 3 ], [ 1 ],
[ 1, 3 ], [ 1, 2 ], [ 1, 2, 1 ], [ 1, 2, 3 ], [ 1, 2, 1, 3 ] ]
MatXPerm( W, w )
MatXPerm
returns the matrix of a linear
transformation of V which acts trivially on the orthogonal of the
coroots and has same effect as w on the simple roots. Only the image of
the simple roots by w is used.
gap> W := CoxeterGroup(
> [ [ 2, 0,-1, 0, 0, 0, 1 ], [ 0, 2, 0,-1, 0, 0, 0 ],
> [-1, 0, 2,-1, 0, 0,-1 ], [ 0,-1,-1, 2,-1, 0, 0 ],
> [ 0, 0, 0,-1, 2,-1, 0 ], [ 0, 0, 0, 0,-1, 2, 0 ] ],
> [ [ 1, 0, 0, 0, 0, 0, 0 ], [ 0, 1, 0, 0, 0, 0, 0 ],
> [ 0, 0, 1, 0, 0, 0, 0 ], [ 0, 0, 0, 1, 0, 0, 0 ],
> [ 0, 0, 0, 0, 1, 0, 0 ], [ 0, 0, 0, 0, 0, 1, 0 ] ] );;
gap> w0 := LongestCoxeterElement( W );;
gap> mx := MatXPerm( W, w0 );
[ [ 0, 0, 0, 0, 0, -1, 1 ], [ 0, -1, 0, 0, 0, 0, 2 ],
[ 0, 0, 0, 0, -1, 0, 3 ], [ 0, 0, 0, -1, 0, 0, 4 ],
[ 0, 0, -1, 0, 0, 0, 3 ], [ -1, 0, 0, 0, 0, 0, 1 ],
[ 0, 0, 0, 0, 0, 0, 1 ] ]
MatYPerm( W, w )
MatYPerm
returns the matrix of a linear
transformation of Vdual which acts trivially on the orthogonal of the
roots and has same effect as w on the simple coroots. Only the image
of the simple coroots by w is used.
MatXPerm
and obtain:
gap> my := MatYPerm( W, w0 );
[ [ 0, 0, 0, 0, 0, -1, 0 ], [ 0, -1, 0, 0, 0, 0, 0 ],
[ 0, 0, 0, 0, -1, 0, 0 ], [ 0, 0, 0, -1, 0, 0, 0 ],
[ 0, 0, -1, 0, 0, 0, 0 ], [ -1, 0, 0, 0, 0, 0, 0 ],
[ 1, 2, 3, 4, 3, 1, 1 ] ]
PermMatX( W, M )
PermMatX
returns the corresponding permutation of the roots; it signals an error
if M does not normalize the set of roots.
MatXPerm
and obtain:
gap> PermMatX( W, mx ) = w0;
true
PermMatX( W, M )
PermMatY
returns the corresponding permutation of the coroots; it
signals an error if M does not normalize the set of coroots.
MatYPerm
and obtain:
gap> PermMatY( W, my ) = w0;
true
April 1997