75 Root systems and finite Coxeter groups

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 R. If R does not span V we also have to impose the condition that the map Vdual rightarrow Vdual, y mapsto y -(y,r)rdual stabilizes Rdual.

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-- . . . --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                                              ```
tt |
```                                                          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
```
tt |` `tt |
```
o 2                              o 2

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                  4           ```
bigskip These diagrams encode the presentations for Coxeter groups as follows: the vertices represent the s_i; an edge is drawn between s_i and s_j if m(i,j)>2; the edge is represented as a single bond if m(i,j)=3, a double bond if m(i,j)=4, a triple bond if m(i,j)=6 and as a single bond with the value m(i,j) written above if m(i,j)not in {2,3,4,6}. (We see that we can ignore the arrows indicating relative root lengths; thus, the diagrams of type B_n and C_n lead to identical presentations for Coxeter groups.) The last three diagrams correspond to non-crystallographic groups, excepted for the special cases I_2(3)=A_2, I_2(4)=B_2 and I_2(6)=G_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 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!

Previous Up Next
Index

GAP 3.4.4
April 1997