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-- . . . --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 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!
GAP 3.4.4