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!

Subsections

  1. CartanMat
  2. CartanType
  3. CartanName
  4. PrintDynkinDiagram
  5. CoxeterGroup
  6. Operations and functions for Coxeter groups

75.1 CartanMat

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( typek, nk ). One can use as argument a computed list of types by ApplyFunc( CartanMat, [ type1, n1, ... , typek, nk ] ).

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

75.2 CartanType

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", etcldots) 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, m] is actually returned for a component of type 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).

75.3 CartanName

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

75.4 PrintDynkinDiagram

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

75.5 CoxeterGroup

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 C=simpleCoroots*TransposedMat(simpleRoots) must be a valid Cartan matrix. The dimension of V can be greater than Length(C). The length of 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(C) is equivalent to

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

75.6 Operations and functions for Coxeter groups

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(W). See the explicit description in ChevieClassInfo.

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