In this chapter we describe functions for dealing with finite Coxeter
groups as permutation groups of root systems. A suitable reference for the
general theory is, for example, the volume of Bourbaki Bou68. Finite
Coxeter groups coincide with finite real reflection groups. If a finite
Coxeter group can be defined over the rational numbers (it is a rational
reflection group), it is called a **Weyl group**.

Root systems in the sense of Bourbaki play an important role in mathematics as they classify semi-simple Lie algebras and algebraic groups. Each one defines a Weyl group: a root system is a set of roots (see the chapter on finite reflection groups) on which the Weyl group has a faithful permutation representation. We treat at the same time other finite Coxeter groups as well as Weyl groups by using a slight generalization of the notion of root system.

Let us now give the precise definitions. Let `V` be a real vector space,
*V ^{∨}* its dual. We will denote by

For any *r∈ R*, we have *(r ^{∨},r)=2* and the reflection

We will only consider **reduced** root systems, i.e., such that the only
elements of `R` colinear with a root *r* are *r* and *-r*.

A root system `R` is called **crystallographic** if *(r ^{∨},s)* is an
integer, for any

The dimension of the subspace *V _{R}* of

The subgroup *W=W(R)* of GL*(V)* generated by the reflections with
roots in `R` is a finite Coxeter group (see chapter Coxeter groups ---
below, we will describe explicitly how to obtain the Coxeter generators
from the root system). If the root system is crystallographic, the
representation `V` of `W` is defined over the rational numbers, thus `W` is
a Weyl group. All other finite-dimensional (complex) representations of a
Weyl group `W` can also be realized over the rational numbers. Weyl groups
can be characterized amongst finite Coxeter groups by the fact that all
numbers *m(i,j)* in the Coxeter matrix are in *{2,3,4,6}*.

We identify `V` with *V ^{∨}* by choosing a

`CartanMat`

described below.

1 2 3 n 1 2 3 n A_n o---o---o-- . . . --o B_n o=<=o---o-- . . . --o 1 o \ 4 n 1 2 3 n D_n 3 o---o--- . . . --o C_n o=>=o---o-- . . . --o / 2 o 1 2 1 2 3 4 1 3 4 5 6 G_2 0->-0 F_4 o---o=>=o---o E_6 o---o---o---o---o 6 | o 2 1 3 4 5 6 7 1 3 4 5 6 7 8 E_7 o---o---o---o---o---o E_8 o---o---o---o---o---o---o | | o 2 o 2

These diagrams encode the presentation of the Coxeter group `W` as
follows: the vertices represent the generating reflections *s _{i}*; an edge
is drawn between

To complete the classification of finite Coxeter groups, we need to add the following Coxeter diagrams:

1 2 1 2 3 1 2 3 4 I_2(m) o---o H_3 o---o---o H_4 o---o---o---o m 5 5

where a single edge has the value *m(i,j)* written above if *m(i,j)∉
{2,3,4,6}*. These correspond to non-crystallographic groups, excepted for
the special cases *I _{2}(3)=A_{2}*,

Let us now describe how the root systems are encoded in these diagrams. Let
`R` be a root system in `V`. Then we can choose a linear form on `V` which
vanishes on no element of `R`. According to the sign of the value of this
linear form on a root *r ∈ R* we call *r* **positive** or **negative**. Then
there exists a unique subset of the set of positive roots, called the set
of **simple roots**, such that any positive root is a linear combination with
non-negative coefficients of simple roots. It can be shown that any two
sets of simple roots (corresponding to different choices of linear forms as
above) can be transformed into each other by a unique element of *W(R)*.
Hence, since the pairing between *V* and *V ^{∨}* is

The indices for the rows of *C* label the nodes of the diagram. The edges,
for *i ≠ j*, are given as follows. If *C _{ij}* and

It is now important to note that, conversely, the whole root system can be
recovered from the simple roots. The reflections in *W(R)* corresponding to
the simple roots are called **simple** reflections. They are precisely the
generators for which the Coxeter diagram encodes the defining relations of
*W(R)*. Each root is in the orbit of a simple root, so that `R` is obtained
as the orbit of the simple roots under the group generated by the simple
reflections. The restriction of the simple reflections to *V _{R}* is
determined by the Cartan matrix, so

In **GAP3** the Cartan matrix corresponding to one of the above irreducible
root systems (with the specified labeling) is returned by the command
`CartanMat`

which takes as input a string giving the type (e.g., `"A"`

,
`"B"`

, *...*, `"I"`

) and a positive integer giving the rank. For type
*I _{2}(m)*, we give as a third argument the integer

`DiagonalMat`

.
The function `CoxeterGroup`

takes as input some data which determine the
roots and the coroots and produces a **GAP3** permutation group record, where
the Coxeter group is represented by its faithful permutation action on the
root system `R`, with additional components holding information about `R`
and the additional components which makes it also a Coxeter group record.
If we label the positive roots by `[1 .. N]`

, and the negative roots by
`[N+1 .. 2*N]`

, then each simple reflection is represented by the
permutation of `[ 1 .. 2*N ]`

which it induces on the roots.

The function `CoxeterGroup`

has several forms; in one of them, the argument
is the Cartan matrix of the root system This constructs a root system where
the simple roots are the canonical basis of `V`, and the matrix of the
coroots expressed in the dual basis of *V ^{∨}* is then equal to the Cartan
matrix.

If one only wants to work with Cartan matrices with a labeling as specified
by the above list, the function call can be simplified. Instead of
`CoxeterGroup( CartanMat("D", 4 ) )`

the following is also possible.

gap> W := CoxeterGroup( "D", 4 ); # Coxeter group of typeDCoxeterGroup("D",4) gap> PrintArray(CartanMat(W)); [[ 2, 0, -1, 0], [ 0, 2, -1, 0], [-1, -1, 2, -1], [ 0, 0, -1, 2]]_{4}

Also, the Coxeter group record associated to a direct sum of irreducible root systems with the above standard labeling can be obtained by listing the types of the irreducible components:

gap> W := CoxeterGroup( "A", 2, "B", 2 );; gap> PrintArray(CartanMat(W)); [[ 2, -1, 0, 0], [-1, 2, 0, 0], [ 0, 0, 2, -2], [ 0, 0, -1, 2]]

The same record is constructed by applying `CoxeterGroup`

to the matrix
`CartanMat("A",2,"B",2)`

or to ```
DiagonalMat(CartanMat("A",2),
CartanMat("B",2))
```

, or even by calling
`CoxeterGroup("A",2)*CoxeterGroup("B",2)`

The following sections give more details on how to work with the elements
of `W` and different representations for them (permutations, reduced
expressions, matrices).

- CartanMat for Dynkin types
- CoxeterGroup
- Operations and functions for finite Coxeter groups
- HighestShortRoot
- PermMatY
- Inversions
- ElementWithInversions
- DescribeInvolution
- ParabolicSubgroups
- ExtendedReflectionGroup

`CartanMat( `

`type`, `n` )

returns the Cartan matrix of Dynkin type `type` and rank `n`. Admissible
types are the strings `"A"`

, `"B"`

, `"C"`

, `"D"`

, `"E"`

,
`"F"`

, `"G"`

, `"H"`

, `"I"`

, `"Bsym"`

, `"Gsym"`

, `"Fsym"`

,
`"Isym"`

, `"B?"`

, `"G?"`

, `"F?"`

, `"I?"`

.

gap> C := CartanMat( "F", 4 );; gap> PrintArray( C ); [[ 2, -1, 0, 0], [-1, 2, -1, 0], [ 0, -2, 2, -1], [ 0, 0, -1, 2]]

For type *I _{2}(m)*, which is in fact an infinity of types depending on
the number

`CartanMat( "I", 2, ``m` )

:

gap> CartanMat( "I", 2, 5 ); [ [ 2, E(5)^2+E(5)^3 ], [ E(5)^2+E(5)^3, 2 ] ]

The types like `"Bsym"`

specify (non crystallographic) root systems where
all roots have the same length, which is necessary for some automorphisms
to exist, like the outer automorphism of *B _{2}* which exchanges the two
generating reflections:

gap> CartanMat("Bsym",2); [ [ 2, -E(8)+E(8)^3 ], [ -E(8)+E(8)^3, 2 ] ]

Finally, for irreducible root systems which have two root lengths, the
forms like `"B?"`

allow to specify arbitrary root systems (up to a
scalar) by giving explicitly as a third argument the coefficient by
which to multiply the second conjugacy class of roots compared to the
default Cartan matrix for that type.

gap> CartanMat("B?",2,1); # the same as C2 [ [ 2, -1 ], [ -2, 2 ] ]

`CartanMat( `

`type1`, `n1`, ... , `typek`, `nk` )

returns the direct sum of `CartanMat( `

, `type1`, `n1` )*...*,
`CartanMat( `

. One can use as argument a computed list of
types by `typek`, `nk` )`ApplyFunc( CartanMat, [ `

.
`type1`, `n1`, ... , `typek`, `nk` ]
)

`CoxeterGroup( `

`C` )

`CoxeterGroup( `

`type1`, `n1`, ... , `typek`, `nk` )

`CoxeterGroup( `

`rec` )

This function returns a permutation group record containing the basic
information about the Coxeter group and the root system determined by its
arguments. In the first form the canonical basis of a real vector space `V`
of dimension `Length(`

is taken as simple roots, and the lines of the
matrix `C`)`C` express the set of coroots in the dual basis of *V ^{∨}*. The
matrix

The second form is equivalent to

`CoxeterGroup(CartanMat(`

.
`type1`, `n1`, ..., `typek`, `nk`))

The resulting record, that we will call a **Coxeter datum**, has additional
entries describing various information on the root system and Coxeter group
that we describe below.

The last form takes as an argument a record which has a field `coxeter`

and
returns the value of this field. This is used to return the Coxeter group
of objects derived from Coxeter groups, such as Coxeter cosets, Hecke
algebras and braid elements.

We document the following entries in a Coxeter datum record which are guaranteed to remain present in future versions of the package. Other undocumented entries should not be relied upon, they may change without notice.

`isCoxeterGroup`

,`isDomain`

,`isGroup`

,`isPermGroup`

,`isFinite`

:

`true`

`cartan`

:

the Cartan matrix`C`

`roots`

:

the root vectors, given as linear combinations of simple roots. The first`N`

roots are positive, the next`N`

are the corresponding negative roots. Moreover, the first`SemisimpleRank(W)`

roots are the simple roots. The positive roots are ordered by increasing height.

`coroots`

:

the same information for the coroots. The coroot corresponding to a given root is in the same relative position in the list of coroots as the root in the list of roots.

`N`

:

the number of positive roots

`rootLengths`

:

the vector of length of roots the simple roots. The shortest roots in an irreducible subsystem are given the length 1. The others then have length 2 (or 3 in type*G*). The matrix of the_{2}`W`-invariant bilinear form is given by`List([1..SemisimpleRank(W)], i->W.rootLengths[i]*W.cartan[i])/2`

.

`orbitRepresentative`

:

this is a list of same length as`roots`

, which for each root, gives the smallest index of a root in the same`W`-orbit.

`orbitRepresentativeElements`

:

a list of same length as`roots`

, which for the*i*-th root, gives an element`w`of`W`of minimal length such that`i=orbitRepresentative[i]^w`

.

`matgens`

:

the matrices (in row convention --- that is the matrices operate**from the right**) of the simple reflections of the Coxeter group.

`generators`

:

the generators as permutations of the root vectors. They are given in the same order as the first`SemisimpleRank(W)`

roots.

gap> W := CoxeterGroup( "A", 4 );; gap> PrintArray( W.cartan ); [[ 2, -1, 0, 0], [-1, 2, -1, 0], [ 0, -1, 2, -1], [ 0, 0, -1, 2]] gap> W.matgens; [ [ [ -1, 0, 0, 0 ], [ 1, 1, 0, 0 ], [ 0, 0, 1, 0 ], [ 0, 0, 0, 1 ] ], [ [ 1, 1, 0, 0 ], [ 0, -1, 0, 0 ], [ 0, 1, 1, 0 ], [ 0, 0, 0, 1 ] ], [ [ 1, 0, 0, 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> W.roots; [ [ 1, 0, 0, 0 ], [ 0, 1, 0, 0 ], [ 0, 0, 1, 0 ], [ 0, 0, 0, 1 ], [ 1, 1, 0, 0 ], [ 0, 1, 1, 0 ], [ 0, 0, 1, 1 ], [ 1, 1, 1, 0 ], [ 0, 1, 1, 1 ], [ 1, 1, 1, 1 ], [ -1, 0, 0, 0 ], [ 0, -1, 0, 0 ], [ 0, 0, -1, 0 ], [ 0, 0, 0, -1 ], [ -1, -1, 0, 0 ], [ 0, -1, -1, 0 ], [ 0, 0, -1, -1 ], [ -1, -1, -1, 0 ], [ 0, -1, -1, -1 ], [ -1, -1, -1, -1 ] ]

All permutation group operations are defined on Coxeter groups, as well as all functions defined for finite reflection groups. However, the following operations and functions have been specially written to take advantage of the particular structure of real reflection groups:

`=`

:

Two Coxeter data are equal if they are equal as permutation groups and the fields`simpleRoots`

and`simpleCoroots`

agree (independently of the value of any other bound fields).

`Print`

:

prints a Coxeter group in a form that can be input back in**GAP3**as a Coxeter group.

`Size`

:

uses the classification of Coxeter groups to work faster (specifically, uses the function`ReflectionDegrees`

).

`Elements`

:

returns the set of elements. They are computed using CoxeterElements. (Note that in an earlier version of the package the elements were sorted by length. You can get such a list by`Concatenation( List( [1..W.N], i -> CoxeterElements(W, i)))`

)

`ConjugacyClasses`

:

Uses classification of Coxeter groups to work faster, and the resulting list is given in the same order as the result of`ChevieClassInfo`

(see ChevieClassInfo). Each`Representative`

given by**CHEVIE**has the property that it is of minimal Coxeter length in its conjugacy class and is a "good" element in the sense of GM97.

`CharTable`

:

Uses the classification of Coxeter groups to work faster, and the result has better labeling than the default (see Classes and representations for reflection groups).

`PositionClass`

,`ClassInvariants`

,`FusionConjugacyClasses`

:

Use the classification of Coxeter groups to work faster.

`DecompositionMatrix(W,p)`

:

Returns the*p*-modular decomposition matrix for Weyl groups which have no component of type`D`

.

Similarly, all functions for abstract Coxeter groups are available for
finite Coxeter groups. However a few of them are implemented by more
efficient methods. For instance, an efficient way of coding
`IsLeftDescending(W,w,s)`

is `s^w>W.N`

(for reflection subgroups this has
to be changed slightly: elements are represented as permutations of the
roots of the parent group, so one needs to write `s^w>W.parentN`

, or
`W.rootRestriction[s^w]>W.N`

). The functions `CoxeterWord`

,
`CoxeterLength`

, `ReducedCoxeterWord`

, `IsLeftDescending`

,
`FirstLeftDescending`

, `LeftDescentSet`

and `RightDescentSet`

also have a
special implementation. Finally, some functions for finite reflection
groups which are implemented by more efficient methods, are
`ReflectionType`

, `ReflectionName`

, `MatXPerm`

, `Reflections`

,
`ReflectionDegrees`

, `ReflectionCharValue`

.

`PrintDiagram`

:

Prints the Dynkin diagram of the root system (a more specific information that the Coxeter diagram, since it includes an indication of the relative root lengths).

gap> C := [ [ 2, 0, -1 ], [ 0, 2, 0 ], [ -1, 0, 2 ] ];; gap> t := ReflectionType( C ); [ rec(rank := 2, series := "A", indices := [ 1, 3 ]), rec(rank := 1, series := "A", indices := [ 2 ]) ] gap> PrintDiagram( t ); A2 1 - 3 A1 2 gap> PrintDiagram( CoxeterGroup( "C", 3) ); C3 1 >=> 2 - 3

`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, CoxeterGroup("A",1,"B",3) should be irreducible in HighestShortRoot( W1 ) called from main loop brk>

`PermMatY( `

`W`, `M` )

Let `M` be a linear transformation of the vector space *V ^{∨}* on which
the Coxeter datum

`PermMatY`

returns the corresponding permutation of the coroots; it
signals an error if

gap> W:=ReflectionSubgroup(CoxeterGroup("E",7),[1..6]); ReflectionSubgroup(CoxeterGroup("E",7), [ 1, 2, 3, 4, 5, 6 ]) gap> w0:=LongestCoxeterElement(W);; gap> my:=MatYPerm(W,w0);; gap> PermMatY( W, my ) = w0; true

`Inversions( `

Returns the inversions of the element `W`, `w` )`w` of the finite Coxeter group `W`,
that is, the list of the indices of roots of the parent of `W` sent by `w`
to negative roots. The element `w` can also be given as a word *s _{1}...
s_{n}*, in which case the function returns inversions in the order of the
roots of the reflections

gap> W:=CoxeterGroup("A",3); CoxeterGroup("A",3) gap> Inversions(W,W.1^W.2); [ 1, 2, 4 ] gap> Inversions(W,[1,2,1]); [ 1, 4, 2 ]

`ElementWithInversions( `

`W`, `N` )

`W` should be a finite Coxeter group and `N` a subset of `[1..W.N]`

.
Returns the element `w` of `W` such that `N` is the list of indices of
positive roots which are sent to negative roots by `w`. Returns false if no
such element exists.

gap> W:=CoxeterGroup("A",2); CoxeterGroup("A",2) gap> List(Combinations([1..W.N]),N->ElementWithInversions(W,N)); [ (), (1,4)(2,3)(5,6), false, (1,5)(2,4)(3,6), (1,6,2)(3,5,4), (1,3)(2,5)(4,6), (1,2,6)(3,4,5), false ]

`DescribeInvolution( `

`W`, `w` )

Given an involution `w` of a Coxeter group `W`, by a theorem of Richardson
(rich82) there is a unique subset *I* of the reflections of `W` such
that `w` is the longest element of *W _{I}*, and that longest element is
central in

`Reflections(Parent(W))`

, so that
`w=LongestCoxeterElement(ReflectionSubgroup(W,I))`

.

gap> W:=CoxeterGroup("A",2); CoxeterGroup("A",2) gap> w:=LongestCoxeterElement(W); (1,5)(2,4)(3,6) gap> DescribeInvolution(W,w); [ 3 ] gap> w=LongestCoxeterElement(ReflectionSubgroup(W,[3])); true

`ParabolicSubgroups( `

`W` )

returns the list of all parabolic subgroups of `W`. These are the
conjugates of the groups returned by `ParabolicRepresentatives(W)`

; they
are also in bijection with the flats of the hyperplane arrangement defined
by `W`. To save memory, the list is given as a list of generating
reflections for each group. For each element `I`

of this list, one has to
call `ReflectionSubgroup(W,I)`

to actually get the corresponding group.

gap> ParabolicSubgroups(CoxeterGroup("A",3)); [ [ ], [ 1 ], [ 2 ], [ 3 ], [ 4 ], [ 5 ], [ 6 ], [ 1, 2 ], [ 1, 5 ], [ 2, 3 ], [ 3, 4 ], [ 1, 3 ], [ 2, 6 ], [ 4, 5 ], [ 1, 2, 3 ] ]

`ExtendedReflectionGroup( `

`W`, `M` )

This function creates an extended reflection group, which is represented as
an object with two field, one recording a reflection group `W` on a vector
space `V`, and the other a subgroup `M` of the linear group of `V` which
normalizes `W`. Actually `M` should normalize the set of roots of `W`. If
`W` is semisimple, that is `Rank(W)=SemisimpleRank(W)`

, then one can give
`M` as a group of permutations (of the roots of `W`), otherwise one must
give `M` as a matrix group.

gap> W:=CoxeterGroup("F",4); CoxeterGroup("F",4) gap> D4:=ReflectionSubgroup(W,[1,2,9,16]); ReflectionSubgroup(CoxeterGroup("F",4), [ 1, 2, 9, 16 ]) gap> t:=ReducedRightCosetRepresentatives(W,D4){[3,4]}; [ ( 2, 9)( 3,27)( 4, 7)( 5,11)(10,13)(12,15)(17,19)(20,22)(26,33) (28,31)(29,35)(34,37)(36,39)(41,43)(44,46), ( 2, 9,16)( 3, 4,31)( 5,11,18)( 6,13,10)( 7,27,28)( 8,15,12) (14,22,20)(17,19,21)(26,33,40)(29,35,42)(30,37,34)(32,39,36) (38,46,44)(41,43,45) ] gap> ExtendedReflectionGroup(D4,Group(t,())); Extended(D4<9,2,1,16>,(2,9),(2,9,16))

gap3-jm

08 Sep 2017