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) . In
*

`LeftDescentSet`

. Brieskorn
Bri71 has noticed that `CHEVIE.BrieskornNormalForm:= true;`

. When you load CHEVIE this
variable is initialized with `false`

(see also CoxeterWord).
*
We give an example of some other commands:
*

*
*

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 ]

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 `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) . Then it is more efficient to represent *

`i^wW.N`

than to work with a
reduced expression and check the condition
*
Length( ReducedCoxeterWord( W, Concatenation( [i], w ) ) )*

```
```

```
```

` Subsections`

```
```
- PermCoxeterWord
- CoxeterWord
- CoxeterLength
- ReducedCoxeterWord
- LeftDescentSet
- RightDescentSet
- Reflections
- LongestCoxeterElement
- LongestCoxeterWord
- HighestShortRoot
- CoxeterElementsLength
- CoxeterWords
- CoxeterConjugacyClasses
- ChevieClassInfo
- Bruhat
- MatXPerm
- MatYPerm
- PermMatX
- PermMatY

## 76.1 PermCoxeterWord

`PermCoxeterWord( ``W` , `w` )

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`.

gap> W := CoxeterGroup( "G", 2 );;
gap> PermCoxeterWord( W, [1,2,1] );
( 1,12)( 2, 4)( 3, 9)( 6, 7)( 8,10)

See also CoxeterWord.

This function requires the package "chevie" (see RequirePackage).

## 76.2 CoxeterWord

`CoxeterWord( ``W` , `w` )

returns a reduced word in the standard generators of the Coxeter group
`W` determined by the permutation `w` on the root vectors.

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 ]

For the definition of the Brieskorn normal form, see the introduction to
this chapter. If the global variable `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`.

See also PermCoxeterWord and ReducedCoxeterWord.

This function requires the package "chevie" (see RequirePackage).

## 76.3 CoxeterLength

`CoxeterLength( ``W` , `w` )

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.

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).
## 76.4 ReducedCoxeterWord

`ReducedCoxeterWord( ``W` , `w` )

returns a reduced expression for an element of the Coxeter group `W`,
which is given as a list `w` of integers where each entry `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 ]

This function requires the package "chevie" (see RequirePackage).

## 76.5 LeftDescentSet

`LeftDescentSet( ``W`, `w` )

The set of generators *s* such that *l(sw)*, given as a list of
integers.

*
*

* gap> W := CoxeterGroup( "A", 2 );;
gap> w := PermCoxeterWord( W, [ 1, 2 ] );;
gap> LeftDescentSet( W, w );
[ 1 ] *

*
*
See also RightDescentSet.

This function requires the package "chevie" (see RequirePackage).

## 76.6 RightDescentSet

`RightDescentSet( ``W`, `w` )

The set of generators *s* such that *l(ws)< l(w)*, given as a list of
integers.

gap> W := CoxeterGroup( "A", 2 );;
gap> w := PermCoxeterWord( W, [ 1, 2 ] );;
gap> RightDescentSet( W, w );
[ 2 ]

See also LeftDescentSet.

This function requires the package "chevie" (see RequirePackage).

## 76.7 Reflections

`Reflections( ``W` )

returns the set of reflections in the Coxeter group `W` (as
permutations). The `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) ]

This function requires the package "chevie" (see RequirePackage).

## 76.8 LongestCoxeterElement

`LongestCoxeterElement( ``W` )

returns the unique element of maximal length of the Coxeter group `W` as
a permutation.

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)

This function requires the package "chevie" (see RequirePackage).

## 76.9 LongestCoxeterWord

`LongestCoxeterWord( ``W` )

returns a reduced expression in the standard generators for the unique
element of maximal length of the Coxeter group `W`.

gap> LongestCoxeterWord( CoxeterGroup( "A", 4 ) );
[ 1, 2, 1, 3, 2, 1, 4, 3, 2, 1 ]

This function requires the package "chevie" (see RequirePackage).

## 76.10 HighestShortRoot

`HighestShortRoot( ``W` )

Let `W` be an irreducible Coxeter group. `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>

This function requires the package "chevie" (see RequirePackage).

## 76.11 CoxeterElementsLength

`CoxeterElementsLength( ``W`, `l` )

returns as a list of permutations the list of all elements of `W` of
length `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

The result of the computation of elements of a given length is stored in
the component `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`

.

This function requires the package "chevie" (see RequirePackage).

## 76.12 CoxeterWords

`CoxeterWords( ``W` )

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 `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 ] ]

This function requires the package "chevie" (see RequirePackage).

## 76.13 CoxeterConjugacyClasses

`CoxeterConjugacyClasses( ``W` )

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.

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.
This function requires the package "chevie" (see RequirePackage).

## 76.14 ChevieClassInfo

`ChevieClassInfo( ``W` )

returns information about the conjugacy classes of the finite Coxeter
group `W`. The result is a record with three components: `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.-" ] )

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).

## 76.15 Bruhat

`Bruhat( ``W`, `y`, `w`[, `ly`, `lw`] )

returns `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 ] ]

This function requires the package "chevie" (see RequirePackage).

## 76.16 MatXPerm

`MatXPerm( ``W`, `w` )

Let `w` be a permutation of the roots of the Coxeter datum `W` acting on
the vector space `V`. `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 ] ]

This function requires the package "chevie" (see RequirePackage).

## 76.17 MatYPerm

`MatYPerm( ``W`, `w` )

Let `w` be a permutation of the roots of the Coxeter datum `W` acting on
the vector space *Vdual*. `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.

We continue the example from `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 ] ]

This function requires the package "chevie" (see RequirePackage).

## 76.18 PermMatX

`PermMatX( ``W`, `M` )

Let `M` be a linear transformation of the vector space `V` on which the
Coxeter datum `W` acts which preserves the set of roots. `PermMatX`

returns the corresponding permutation of the roots; it signals an error
if `M` does not normalize the set of roots.

We continue the example from `MatXPerm`

and obtain:

gap> PermMatX( W, mx ) = w0;
true

This function requires the package "chevie" (see RequirePackage).

## 76.19 PermMatY

`PermMatX( ``W`, `M` )

Let `M` be a linear transformation of the vector space *Vdual* on which
the Coxeter datum `W` acts which preserves the set of coroots.
`PermMatY`

returns the corresponding permutation of the coroots; it
signals an error if `M` does not normalize the set of coroots.

We continue the example from `MatYPerm`

and obtain:

gap> PermMatY( W, my ) = w0;
true

This function requires the package "chevie" (see RequirePackage).

GAP 3.4.4

April 1997