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; an English reference is the book of Humphreys Hum90.
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. Weyl groups play an important role in mathematics as they are associated to semi-simple Lie algebras and algebraic groups.
The notion of root systems in the sense of Bourbaki classifies semi-simple Lie algebras and algebraic groups, and each 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 systems of Bourbaki.
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∨.
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). W is a Weyl group if the underlying root system is crystallographic. This condition is equivalent to the property that the representation V 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) in the Coxeter matrix 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 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 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 | 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 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
These diagrams encode the presentations for Coxeter groups as follows: the vertices represent the si; an edge is drawn between si and sj 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)∉ {2,3,4,6}. (We see that we can ignore the arrows indicating relative root lengths; thus, the diagrams of type Bn and Cn lead to identical presentations for Coxeter groups.) The last three diagrams 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 the relative lengths and the angles between simple roots are independent of any choice. Hence, 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 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 ≠ 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 above Dynkin diagrams encode the defining relations of W(R). It can be shown that for each r ∈ R there exist simple reflections si1, ..., sim such that si1 ... sim(r) is a simple root. Thus, all of R is obtained by applying repeatedly simple reflections to a set of roots (starting with the set of simple roots). 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 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"
, ..., "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 GAP)
with entries in Z 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 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 simple 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 V∨ 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 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))
.)
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 V∨. 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; this is the form which allows to represent arbitrary reductive algebraic groups, where the integral elements of V plays the role of the groups of characters of a maximal torus, and the integral elements of V∨ the role of the one-parameter subgroups of that torus; the above example corresponds to the linear group in dimension 3).
The definition of root systems implies that every w ∈ 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 simple 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).
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 root systems where all roots have the
same length (which is necessary for some automorphisms to exists, 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,2); [ [ 2, -2 ], [ -1, 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 ]
)
.
This function requires the package "chevie" (see RequirePackage).
ReflectionType( C )
C should be the Cartan matrix of a finite Coxeter group. This function
returns the type of C, which is a list each element of which describes
an irreducible component of C; the elements of the list are records
with a field series
, the type ("A"
, "B"
, "D"
, etc...)
of the component, a field indices
, the indices in C where it sits, a
field rank
(equal to Length(indices)
for Coxeter groups), so that
C{indices}{indices} = CartanMat(series, Length(indices))
, and for
dihedral groups a field bond
giving the order of the braid relation
between the two generators. The function returns false
if C is not
the Cartan matrix of a finite Coxeter group.
gap> C := [ [ 2, 0, -1 ], [ 0, 2, 0 ], [ -1, 0, 2 ] ];; gap> ReflectionType( C ); [ rec( operations := ReflTypeOps, rank := 2, series := "A", indices := [ 1, 3 ] ), rec( operations := ReflTypeOps, rank := 1, series := "A", indices := [ 2 ] ) ]
ReflectionType( D )
The argument to ReflectionType
can also be a domain (i.e., D should
be a record with a field operations.ReflectionType
, and that function
is then called with D as argument --- this works for reflection groups
and Coxeter cosets).
This function requires the package "chevie" (see RequirePackage).
ReflectionName( type )
takes as argument a type type as returned by ReflectionType
. 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> ReflectionName( ReflectionType( C ) ); "A2xA1" gap> ReflectionName( ReflectionType( CartanMat( "I", 2, 7 ) ) ); "I2(7)"
ReflectionName( D )
The argument to ReflectionName
can also be a domain (i.e., D should
be a record with a field operations.ReflectionName
, and that function
is then called with D as argument --- this works for reflection groups
and Coxeter cosets).
This function requires the package "chevie" (see RequirePackage).
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 V∨. 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
:
simpleRoots
:
simpleCoroots
:
semisimpleRank
:
rank
:TransposedMat(.simpleRoots)
N
:
roots
:N
roots are
positive, the next N
are the corresponding negative roots.
Moreover, the first semisimpleRank
roots are the simple roots
corresponding to the rows of C. The positive roots are
ordered by increasing height.
coroots
:
rootLengths
:
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
roots.
omega
:
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).
78.5 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:
=
: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
:
Size
:ReflectionDegrees
).
Elements
:Concatenation( List( [1..W.N], i -> CoxeterElements(W, i)))
)
ReflectionType
:ReflectionType
of the Cartan matrix.
PrintDiagram
:
gap> C := [ [ 2, 0, -1 ], [ 0, 2, 0 ], [ -1, 0, 2 ] ];; gap> t := ReflectionType( C ); [ rec( operations := ReflTypeOps, rank := 2, series := "A", indices := [ 1, 3 ] ), rec( operations := ReflTypeOps, rank := 1, series := "A", indices := [ 2 ] ) ] gap> PrintDiagram( t ); A2 1 - 3 A1 2 gap> PrintDiagram( CoxeterGroup( "E", 8) ); E8 2 | 1 - 3 - 4 - 5 - 6 - 7 - 8
ReflectionName
:ReflectionName
of the ReflectionType
.
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
:
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
, LeftDescentSet
and RightDescentSet
also have a special implementation. Finally,
all functions for finite reflection groups are available for finite
Coxeter groups. Again, some of them are implemented by more
efficient methods, like MatXPerm
, Reflections
, ReflectionDegrees
,
ReflectionCharValue
.
These functions require the package "chevie" (see RequirePackage).
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, group is not irreducible in HighestShortRoot( W1 ) called from main loop brk>
This function requires the package "chevie" (see RequirePackage).
MatYPerm( W, w )
Let w be a permutation of the roots of the Coxeter datum W acting on
the vector space V∨. MatYPerm
returns the matrix of a linear
transformation of V∨ which acts trivially on the orthogonal of the
roots and has same effect as w on the simple coroots. Only the images
of the simple coroots by w is used.
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); [ [ 0, 0, 0, 0, 0, -1, 2 ], [ 0, -1, 0, 0, 0, 0, 2 ], [ 0, 0, 0, 0, -1, 0, 3 ], [ 0, 0, 0, -1, 0, 0, 4 ], [ 0, 0, -1, 0, 0, 0, 3 ], [ -1, 0, 0, 0, 0, 0, 2 ], [ 0, 0, 0, 0, 0, 0, 1 ] ]
This function requires the package "chevie" (see RequirePackage).
PermMatX( 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.
We continue the example from MatYPerm
and obtain:
gap> PermMatY( W, my ) = w0; true
This function requires the package "chevie" (see RequirePackage).
GAP 3.4.4