85 Root systems and finite Coxeter groups

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 ( , ) the natural pairing between V and V. A root system in V is a finite set of vectors R (the roots), together with a map r→ r from R to a subset R of V (the coroots) such that:

For any r∈ R, we have (r,r)=2 and the reflection V→ V: x→ x- (r,x) r with root r and coroot r stabilizes R. If R does not span V we also have to impose the condition that the dual reflection V → V: y → y -(y,r)r stabilizes R. Note that since (r,r)=2 we get true reflections (of order 2).

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 s∈ R,r∈ R --- these are the root systems considered by Bourbaki.

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

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 W-invariant bilinear form ( ; ); then we have r=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 crystallographic root systems are classified by the following list of Dynkin diagrams. We show the labeling of the nodes given by 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                                              |
                                                          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 si; an edge is drawn between si and sj if the order m(i,j) of sisj is greater than 2; the edge is single if m(i,j)=3, double if m(i,j)=4, triple if m(i,j)=6. The arrows indicate the relative root lengths when W has more than one orbit on R, as explained below; we get the Coxeter Diagram, which describes the underlying Weyl group, if we ignore the arrows: we see that the root systems Bn and Cn correspond to the same Coxeter group.

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 I2(3)=A2, I2(4)=B2 and I2(6)=G2.

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 W-invariant, if {r1,...,rn} is a set of simple roots and if we define the Cartan matrix as being the n times n matrix C={ri(rj)}ij, this matrix is 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 ≠ j, are given as follows. If Cij and Cji are integers such that |Cij| ≥ |Cji| the vertices are connected by |Cij| lines, and if |Cij|>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 pij ≥ 1 such that CijCji=cos2 (π/pij).

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 VR is determined by the Cartan matrix, so R is determined by the Cartan matrix and the set of simple roots.

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 I2(m), we give as a third argument the integer m. This function returns a matrix (i.e., a list of lists in GAP3) with entries in 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 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 type D4
    CoxeterGroup("D",4)
    gap> PrintArray(CartanMat(W));
    [[ 2,  0, -1,  0],
     [ 0,  2, -1,  0],
     [-1, -1,  2, -1],
     [ 0,  0, -1,  2]]

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

Subsections

  1. CartanMat for Dynkin types
  2. CoxeterGroup
  3. Operations and functions for finite Coxeter groups
  4. HighestShortRoot
  5. PermMatY
  6. Inversions
  7. ElementWithInversions
  8. DescribeInvolution
  9. ParabolicSubgroups
  10. ExtendedReflectionGroup

85.1 CartanMat for Dynkin types

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

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

85.2 CoxeterGroup

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(C) is taken as simple roots, and the lines of the matrix C express the set of coroots in the dual basis of V. The matrix C must be a valid Cartan matrix (see CartanMat). The length of C is called the semisimple rank of the Coxeter datum. This function creates a semisimple root system, where the length of C is also equal to the dimension of V, called the rank. The function ReflectionSubgroup can create a Coxeter group record where the rank is not equal to the semisimple rank.

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 G2). The matrix of the 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 ] ]

85.3 Operations and functions for finite Coxeter groups

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

85.4 HighestShortRoot

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> 

85.5 PermMatY

PermMatY( W, M )

Let M be a linear transformation of the vector space V on which the Coxeter datum W acts which preserves the set of coroots. PermMatY returns the corresponding permutation of the coroots; it signals an error if M does not normalize the set of coroots.

    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 

85.6 Inversions

Inversions( W, w ) Returns the inversions of the element 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 s1... sn, in which case the function returns inversions in the order of the roots of the reflections s1, s1 s2 s1,...,s1 s2... sn sn-1... s1.

    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 ]

85.7 ElementWithInversions

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 ]

85.8 DescribeInvolution

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 WI, and that longest element is central in WI. This function return I as the list of indices of its elements 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

85.9 ParabolicSubgroups

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

85.10 ExtendedReflectionGroup

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

Previous Up Next
Index

gap3-jm
08 Sep 2017