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 play an important role in mathematics; they classify semi-simple Lie algebras and algebraic groups. A root system is a set of roots defining reflections (see the chapter on finite reflection groups) generating the Weyl group. We treat at the same time other finite Coxeter groups by using a generalization of root systems to the non-crystallographic (non-rational) case.
We give now the definitions. Let V be a real vector space, V∨ its dual and let ( , ) be 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 (r∨,r)=2 is equivalent to the condition that we have 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
Reflection(r,r∨) is a finite Coxeter group (see chapter Coxeter
groups --- we describe explicitly below 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, in which case all finite-dimensional (complex)
representations of W can be realized over the rational numbers. Weyl
groups are characterized amongst finite Coxeter groups by the fact that all
numbers m(i,j) in the Coxeter matrix are in {2,3,4,6}.
If 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 set S of generating reflections; an
edge is drawn between s and t if the order m(s,t) of st is greater
than 2; the edge is single if m(s,t)=3, double if m(s,t)=4, triple if
m(s,t)=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(s,t) written above if m(s,t)∉ {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, 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 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 important to note that, conversely, the whole root system can be recovered from the simple roots: the set S of reflections in W(R) corresponding to the simple roots are called simple reflections. They are precisely the generators corresponding to the vertices of the Coxeter diagram. 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.
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 (that is in GAP3, a list of lists) 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).
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 ]
).
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:
roots: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:
N:
rootLengths:List([1..SemisimpleRank(W)], i->W.rootLengths[i]*W.cartan[i])/2.
orbitRepresentative:roots, which
for each root, gives the smallest index of a root in the same
W-orbit.
orbitRepresentativeElements:roots, which
for the i-th root, gives an element w of W of minimal length
such that i=orbitRepresentative[i]^w.
matgens:
generators: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:
=:simpleRoots and simpleCoroots agree
(independently of the value of any other bound fields).
Print:
Size:ReflectionDegrees).
Elements:Concatenation( List( [1..W.N], i -> CoxeterElements(W, i))))
ConjugacyClasses: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:PositionClass, ClassInvariants, FusionConjugacyClasses:DecompositionMatrix(W,p):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:
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
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>
BadPrimes( W )
BadPrimes( R )
Let W be a Weyl group. A prime is bad for W if it divides a
coefficient on the simple roots of some root. The function BadPrimes
returns the list of primes which are bad for W.
Alternately the argument can be a set of integer vectors and then the function returns all prime numbers which divide one of their entries.
gap> W:=CoxeterGroup("E",8);
CoxeterGroup("E",8)
gap> BadPrimes(W);
[ 2, 3, 5 ]
gap> BadPrimes(W.roots{[1..50]});
[ 2 ]
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
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 ]
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 ]
DescribeInvolution( W, w )
Given an involution w of a Coxeter group W, by a theorem of Richardson
(rich82) there is a unique parabolic subgroup P of W such that
that w is the longest element of P, and is central in P.
DescribeInvolution returns I such that P=ReflectionSubgroup(W,I), 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
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 ] ]
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))
ClosedSubsystems( W )
Returns the poset (see Poset) of closed subsystems of the root system of W. Each subsystem is represented by the indices of the roots it contains.
gap> W:=CoxeterGroup("G",2);
CoxeterGroup("G",2)
gap> p:=ClosedSubsystems(W);
Poset with 12 elements
gap> Display(p);
1 2 3 4 5 6 7 8 9 10 11 12<1 4 7 10<4 10<
1 2 3 4 5 6 7 8 9 10 11 12<1 5 6 7 11 12<1 7<
1 2 3 4 5 6 7 8 9 10 11 12<2 6 8 12<6 12<
1 2 3 4 5 6 7 8 9 10 11 12<3 5 9 11<5 11<
1 2 3 4 5 6 7 8 9 10 11 12<4 10
1 2 3 4 5 6 7 8 9 10 11 12<1 7
1 2 3 4 5 6 7 8 9 10 11 12<6 12
1 2 3 4 5 6 7 8 9 10 11 12<5 11
1 2 3 4 5 6 7 8 9 10 11 12<2 8<
1 2 3 4 5 6 7 8 9 10 11 12<3 9<
1 4 7 10<1 7
1 5 6 7 11 12<6 12
1 5 6 7 11 12<5 11
2 6 8 12<2 8
3 5 9 11<3 9
gap3-jm