In this chapter we describe functions for dealing with root systems and finite Coxeter groups.

A suitable reference for the general theory is, for example, the volume of Bourbaki Bou68; an English reference is the book of Humphreys Hum90.

A **Coxeter group** is a group defined by a presentation of the form
[
leftlangle
s_1, ldots, s_n | (s_i s_j)^m(i,j)=1 quad mboxfor all i, j
rightrangle
]
for some integers *m(i,j)*, where *m(i,j)>1* for *i neq j* and
*m(i,i)=1* for all *i*. The matrix *{m(i,j)}_{i,j}* is called the
**Coxeter matrix**; the set of Coxeter matrices such that the defined group
is finite have been completely classified. A Coxeter group has a natural
representation on a real vector space *V* of dimension the number of
generators, its **reflection representation**, where the *s_i* act as
reflections (a **reflection** in a vector space *V* is an element of
*text{GL}(V)* of order 2 which leaves fixed a hyperplane). It turns
out that finite Coxeter groups are the same as finite real reflection
groups, i.e., finite groups generated by reflections in a real vector
space. The set of reflecting hyperplanes of a finite Coxeter group is in
fact related to the notion of a root system, and this carries slightly
more information than just the set of integers *m(i,j)* used in the
definition of Coxeter groups (by taking into account relative lengths of
the roots, see below). It is this underlying geometric structure by
which Coxeter groups appear in various areas of mathematics such as Lie
algebras and linear algebraic groups. In **GAP**, the objects we will
actually deal with are the Coxeter groups, together with their action on
a root system.

Let us now give the precise definitions. Let *V* be a vector space,
*Vdual* its dual. We will denote by *(;,;)* the natural pairing
between *Vdual* and *V*. A **root system** in *V* is a finite set of
vectors *R* (the **roots**), together with a map *rmapsto rdual* from *R*
to a subset *Rdual* of *Vdual* (the **coroots**) such that:

For any *r in R*, we have *(rdual,r)=2*, so that the map *V rightarrow
V*, *xmapsto x- (rdual,x) r* defines a reflection in *V* (that we will
call the **reflection with root r**), and this reflection stabilizes

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 *(rdual,r)* is an
integer, for any *r in R,rdual in Rdual*.

The dimension of the subspace *V_R* of *V* spanned by *R* will be called
the **semi-simple rank** of *R*.

**Remark.** For the study of Coxeter groups it would be sufficient to
consider root systems as certain subsets of Euclidean spaces which
contain a basis of that space. Our definition is motivated by the notion
of root data, which allow to describe connected reductive algebraic
groups over algebraically closed fields (see for example
cite[Ch.9]Spr81).

The subgroup *W=W(R)* of *mbox{GL}(V)* generated by the reflections with
roots in *R* is a finite Coxeter group given by a presentation as above.
(Below, we will describe explicitly how to obtain the set of generators
from the root system.) We call *W* a **crystallographic Coxeter** group (or
a **Weyl group**) if the underlying root system is crystallographic. This
condition is equivalent to the property that the reflection
representation of *W* is defined over the rational numbers. Weyl groups
can be characterized amongst finite Coxeter groups by the fact that all
numbers *m(i,j)* are in *{2,3,4,6}*. It turns out that all other
finite-dimensional (complex) representations of a Weyl group *W* can also
be realized over the rational numbers.

We identify *V* with *Vdual* by choosing a *W*-invariant bilinear form
*(;;;)*; then we have *rdual=2r/(r;r)*. A root system *R* is
irreducible if it is not the union of two orthogonal subsets. If *R* is
reducible then the corresponding Coxeter group is the direct product of
the Coxeter groups associated with the irreducible components of *R*. The
irreducible root systems, and also the finite irreducible Coxeter groups,
are classified by the following list of Dynkin diagrams. The labeling of
the nodes is exactly the same labeling as in the function `CartanMat`

described below.

1 2 3 n 1 2 3 n A_n o---o---o-- . . . --o B_n o=<=o---o-- . . . --ott |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 2tt |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

` `

tt |o 2 o 2bigskip These diagrams encode the presentations for Coxeter groups as follows: the vertices represent the1 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 4

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 in R* we call *r* **positive** or
**negative**. Then there exists a unique subset of the set of positive
roots, called the set of **fundamental roots**, such that any positive root
is a linear combination with non-negative coefficients of fundamental
roots. It can be shown that any two sets of fundamentals roots
(corresponding to different choices of linear forms as above) can be
transformed into each other by a unique element of *W(R)*, hence the
relative lengths and the angles between fundamental roots are independent
of any choice. Hence, if *{r_1,ldots,r_n}* is a set of fundamental
roots and if we define the **Cartan matrix** as being the *n* times *n*
matrix *C=((r_idual,r_j)_{ij})* then this matrix is in fact unique up to
simultaneous permutation of rows and columns. It is precisely this
matrix which is encoded in a Dynkin diagram, as follows.

The indices for the rows of *C* label the nodes of the diagram. The
edges, for *i neq j*, are given as follows. If *C_{ij}* and *C_{ji}* are
integers such that *|C_{ij}| geq |C_{ji}|* the vertices are
connected by *|C_{ij}|* lines, and if *|C_{ij}|>1* then we put an
additional arrow on the lines pointing towards the node with label *i*.
In all other cases, we simply put a single line equipped with the unique
integer *p_{ij} geq 1* such that *C_{ij}C_{ji}=cos^2 (pi/p_{ij})*.

It is now important to note that, conversely, the whole root system can
be recovered from the set of fundamental roots. The reflections in
*W(R)* corresponding to the fundamental roots are called **fundamental**
(or **simple**) reflections. They are precisely the generators for which
the above Dynkin diagrams encode the defining relations of *W(R)*. It
can be shown that for each *r in R* there exist fundamental reflections
*s_{i_1}, dots, s_{i_m}* such that *s_{i_1} cdots s_{i_m}(r)* is a
fundamental root. Thus, all of *R* is obtained by applying repeatedly
simple reflections to a set of roots (starting with the set of
fundamental roots). The restriction of the simple reflections to *V_R*
is determined by the Cartan matrix, so *R* is determined by the Cartan
matrix and the set of fundamental roots.

In **GAP** 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"`

, *dots*, `"I"`

) and a positive integer giving the rank. For
type *I_2(m)*, we give as a third argument the integer *m*. This function
returns a matrix (i.e., a list of lists in **GAP**) with entries in
*{ZZ}* or in a cyclotomic extension of the rationals. Given two Cartan
matrices, their matrix direct sum (corresponding to the orthogonal direct
sum of the root systems) can be produced by the function `DirectSumMat`

.

The function `CoxeterGroup`

takes as input some data which determine the
roots and the coroots and produces a **GAP** permutation group record,
where the Coxeter group is represented by its faithful action on the root
system *R*, with additional components containing basic information about
*R* (a system of fundamental roots etc...).

The function `CoxeterGroup`

has several forms; in the first form, it is
assumed that the simple roots are the basis of *V* (the matrix of the
coroots expressed in the dual basis of *Vdual* is then equal to the
Cartan matrix); the argument is the Cartan matrix of the root system
(irreducible or not, and with any ordering of the simple roots).

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 type $D_4$ CoxeterGroup("D", 4) gap> PrintArray( W.cartan ); [ [ 2, 0, -1, 0 ], [ 0, 2, -1, 0 ], [ -1, -1, 2, -1 ], [ 0, 0, -1, 2 ] ]

(The matrix printed is the **Cartan matrix**.)

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 );; PrintArray( W.cartan ); [ [ 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 ```
DirectSumMat(CartanMat("A", 2),
CartanMat("B", 2))
```

.)

In the second more general form, one gives as argument to `CoxeterGroup`

two matrices, one whose lines are the roots expressed in a basis of *V*,
and the second whose lines are the coroots expressed in the corresponding
dual basis of *Vdual*. In this form, the roots need not generate *V*.

gap> W := CoxeterGroup( [ [ -1, 1, 0], [ 0, -1, 1 ] ], > [ [ -1, 1, 0], [ 0, -1, 1 ] ] ); CoxeterGroup([ [ -1, 1, 0 ], [ 0, -1, 1 ] ], [ [ -1, 1, 0 ], [ 0, -1, 1 ] ]) gap> MatXPerm( W, W.generators[1] ); [ [ 0, 1, 0 ], [ 1, 0, 0 ], [ 0, 0, 1 ] ]

(here we have represented the symmetric group on 3 letters as the
permutation of the basis vectors of *V* --- the semi-simple rank is 2).

The definition of root systems implies that every *w in W* induces a
permutation of the elements in *R*, and that the corresponding
permutation representation of *W* on *R* is faithful. If we label the
positive roots by `[1 .. N]`

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

,
then we can represent each fundamental reflection by the permutation of
`[ 1 .. 2*N ]`

which it induces on the root vectors. The representation
of *W* in **GAP** is as the permutation group defined by this faithful
permutation representation. All this is done by the command
`CoxeterGroup`

which produces a permutation group record containing the
relevant information (see the precise description in Section
CoxeterGroup). This record is all that the following programs and
commands need. See the following chapter for more details on how to work
with the elements in *W* and different representations for them
(permutations, reduced expressions, matrices).

We close this informal introduction with some remarks.

*bullet* Since, in the first place, the Coxeter group record is a group
record with the component `isPermGroup`

set to `true`

, all **GAP**
functions defined for permutation groups work for Coxeter groups, but
sometimes there are improvements, exploiting the particular nature of
these groups.

*bullet* There is a function `InfoChevie`

which is set equal to the
**GAP** function `Ignore`

when you load CHEVIE. If you redefine it by
`InfoChevie:=Print;`

then the CHEVIE functions will print some
additional information in the course of their computations.

*bullet* The user should observe limitations on storage for working with
these programs, e.g., the command `Elements`

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!

- CartanMat
- CartanType
- CartanName
- PrintDynkinDiagram
- CoxeterGroup
- Operations and functions for Coxeter groups

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

.

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 *m*, a third argument is needed specifying the integer *m* so the
syntax is in fact `CartanMat( "I", 2, `

:
`m` )

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

`CartanMat( `

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

returns the direct sum of `CartanMat( `

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

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

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

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

`CartanType( `

`C` )

`CartanType( `

`D` )

returns the type of the Cartan Matrix `C`. The result is a list each
element of which describes an irreducible component of `C`, as pair
`[type,indices]`

where `type`

is the type (`"A"`

, `"B"`

, `"D"`

,
etc*ldots*) of the component and `indices`

the indices in `C` where it
sits, so that

` C{indices}{indices} = CartanMat( type, Length( indices ) )`

A triple `[type, indices, `

is actually returned for a component of
type `m`]*I_2(m)*. The `indices`

are arranged in the standard order in which
we give Dynkin diagrams.

gap> C := [ [ 2, 0, -1 ], [ 0, 2, 0 ], [ -1, 0, 2 ] ];; gap> CartanType( C ); [ [ "A", [ 1, 3 ] ], [ "A", [ 2 ] ] ]

The argument to `CartanType`

can also be a domain (i.e., `D` should be a
record with a field `operations.CartanType`

, and that function is then
called with `D` as argument --- this is used for Coxeter groups and
Coxeter cosets).

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

`CartanName( `

`type` )

`CartanName( `

`D` )

takes as argument a type `type` as returned by `CartanType`

. Returns the
name of the root system with that type, which is the concatenation of the
names of its irreducible components, with `x`

added in between.

gap> C := [ [ 2, 0, -1 ], [ 0, 2, 0 ], [ -1, 0, 2 ] ];; gap> CartanName( CartanType( C ) ); "A2xA1" gap> CartanName( CartanType( CartanMat( "I", 2, 7 ) ) ); "I2(7)"

The argument to `CartanName`

can also be a domain (i.e., `D` should be a
record with a field `operations.CartanName`

, and that function is then
called with `D` as argument --- this is used for Coxeter groups and
Coxeter cosets).

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

`PrintDynkinDiagram( `

`type` )

`PrintDynkinDiagram( `

`D` )

This is a purely descriptive routine, which, by printing the Dynkin
diagram of a type `type` (the result of `CartanType`

) shows how the
generators of the corresponding group are labeled on its Dynkin diagram.

gap> C := [ [ 2, 0, -1 ], [ 0, 2, 0 ], [ -1, 0, 2 ] ];; gap> t := CartanType( C ); [ [ "A", [ 1, 3 ] ], [ "A", [ 2 ] ] ] gap> PrintDynkinDiagram( t ); A2 1 - 3 A1 2 gap> PrintDynkinDiagram( CartanType( CartanMat( "E", 8) ) ); E8 2tt |

1 - 3 - 4 - 5 - 6 - 7 - 8

The argument to `PrintDynkinDiagram`

can also be a domain (i.e., `D`
should be a record with a field `operations.PrintDynkinDiagram`

, and that
function is then called with `D` as argument --- this is used for Coxeter
groups and Coxeter cosets).

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

`CoxeterGroup( `

`simpleRoots`, `simpleCoroots`[, `omega`] )

`CoxeterGroup( `

`C`[, "sc"][, `omega`] )

`CoxeterGroup( `

`type1`, `n1`, ... , `typek`, `nk`[, "sc"][, `omega`] )

`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 a set of roots is given explicitly as the
lines of the matrix `simpleRoots`, representing vectors in a vector space
`V`, as well as a set of coroots as the lines of the matrix
`simpleCoroots` expressed in the dual basis of *Vdual*. The product

must be a valid
Cartan matrix. The dimension of `C`=`simpleCoroots`*TransposedMat(`simpleRoots`)`V` can be greater than `Length(`

.
The length of `C`)`C` is called the **semisimple rank** of the Coxeter datum,
while the dimension of `V` is called its **rank**.

In the second form `C` is a Cartan matrix, and the call
`CoxeterGroup(`

is equivalent to
`C`)

`CoxeterGroup(IdentityMat(Length(`

.
`C`)),`C`)

In this case, the root system is embedded in the lattice of integral
vectors of `V` like the root system of an adjoint algebraic reductive
group in the lattice of characters of a maximal torus.

If the optional `"sc"`

argument is given, the situation is reversed:
the simple coroots are given by the identity matrix, and the simple roots
by the transposed of `C` (this corresponds to the embedding of the root
system in the lattice of characters of a maximal torus in a **simply
connected algebraic group**).

The third form is equivalent to

`CoxeterGroup(CartanMat(`

.
`type1`, `n1`, ..., `typek`, `nk`)
[, "sc"][, `omega`])

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 argument `omega` in one of the first three forms can be used to
specify a group of automorphisms of the Coxeter datum, that is, a group
of invertible linear transformations of `V` which preserve the set of
roots and whose adjoint maps preserve the set of coroots. When the rank
is equal to the semisimple rank (we then say that the Coxeter datum is
semisimple), this can be given as a permutation group (on the roots).
Otherwise it must be given as a matrix group.

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`

`simpleRoots`

:

the matrix of simple roots

`simpleCoroots`

:

the matrix of simple coroots

`semisimpleRank`

:

the length of`C`

`rank`

:

the length of`TransposedMat(.simpleRoots)`

`N`

:

the number of positive roots

`roots`

:

the root vectors, given as linear combinations of fundamental roots (note that in a former version of the package only the positive roots were stored). The first`N`

roots are positive, the next`N`

are the corresponding negative roots. Moreover, the first`semisimpleRank`

roots are the fundamental roots corresponding to the rows of`C`. 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.

`rootLengths`

:

the vector of length of roots. The shortest roots in an irreducible subsystem are given the length 1, the others length 2 (or 3 in type*G_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) of the simple reflections of the Coxeter group with respect to the basis consisting of the fundamental root vectors.

`generators`

:

the generators as permutations of the root vectors. They are given in the same order as the first`semisimpleRank`

roots.

`omega`

:

the value of the argument`omega`if it has been specified. Otherwise unbound.

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

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

All permutation group operations are defined on Coxeter groups. However, the following operations and functions have been rewritten or added, respectively, 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). Also the fields .omega should be equal (if the field is absent ---`omega`

not specified --- this is considered specifying the trivial group).

`Print`

:

prints a Coxeter group in a form that can be input back in**GAP**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 CoxeterElementsLength. (Note that in an earlier version of the package the elements were sorted by length. You can still get such a list by`Concatenation( List( [1..W.N], i - CoxeterElementsLength(W, i)))`

)

`CartanType`

:

returns`CartanType`

of the Cartan matrix.

`PrintDynkinDiagram`

:

prints the Dynkin diagram corresponding to the Cartan matrix.

`CartanName`

:

returns the`CartanName`

of the`CartanType`

.

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

`CharTable`

:

Uses the classification of Coxeter groups to work faster, and the result has better labeling than the default (see Chapter Character tables for Coxeter groups).

`ChevieClassInfo`

:

Is part of the Coxeter groups operations record in order to have versions for Coxeter groups and Coxeter cosets. This function returns additional information on the classes which is contained in the character table, but this function returns it without first computing`CharTable(`

. See the explicit description in ChevieClassInfo.`W`)

`CharParams`

:

Is part of the Coxeter groups operations record in order to have versions for Coxeter groups and Coxeter cosets. This function returns the list of parameters for the irreducible characters of`W`: partitions for type`A`

, double partitions for type`B`

, etc... This is used by functions which return information for individual characters, like`FakeDegree`

,`SchurElement`

, etc...

`CharName`

:

Is part of the Coxeter groups operations record in order to have versions for Coxeter groups and Coxeter cosets. This function takes as argument a parameter for a character (see`CharParams`

) and returns a string which is used to label the character is various displayed tables.

`ChevieCharInfo`

:

This function returns additional information on the irreducible characters, see ChevieCharInfo for more details.

`PositionClass`

,`ClassInvariants`

,`FusionConjugacyClasses`

:

Use the classification of Coxeter groups to work faster.`PositionClass(W,x)`

returns the index of the conjugacy class of`x`in the list of the classes of`W`, see PositionClass.

These functions require the package "chevie" (see RequirePackage).
Previous Up Next

Index

GAP 3.4.4

April 1997