Finite Coxeter groups, Weyl groups, crystallographic root systems

Chevie.Weyl — Module

Finite Coxeter groups are the finite complex reflection groups which can be defined on a real vector space V.

Weyl groups are the finite Coxeter groups which can be defined over a rational vector space V (thus over the integers).

Like finite complex reflection groups, finite Coxeter groups are implemented as groups of permutations of a set of roots. The particular crystallographic root systems for Weyl groups play an important role in mathematics as they classify semi-simple Lie algebras and algebraic groups.

Let us give precise definitions. Let V be a real vector space and Vⱽ its dual. A root system is a finite set of vectors R⊂ V (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, so that the formula x↦ x-rⱽ(x)r defines a reflection sᵣ:V→ V with root r and coroot rⱽ.
The reflection sᵣ stabilizes R.

The subgroup W=W(R) of GL(V) generated by the reflections sᵣ for r∈ R is a finite Coxeter group. We require reduced root systems, that is such that the only elements of R colinear with r∈ R are r and -r; for Weyl groups, we also require that the root system be crystallographic, that is rⱽ(s) is an integer, for any s∈ R,rⱽ∈ Rⱽ.

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 R is not the union of two orthogonal subsets; equivalently the representation of W on the subspace generated by R is irreducible. If R is reducible then the corresponding Coxeter group is the direct product of the Coxeter groups associated with the irreducible components of R.

Let us now describe how a root system R and a presentation of the corresponding W are encoded in a Cartan matrix or a Dynkin diagram. We can choose a linear form on V which does not vanish on any element of R. Depending on 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 positive roots, the simple roots, such that any positive root is a linear combination with non-negative coefficients of the roots in Π. 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). If S is the set of reflections with respect to the simple roots, then (W,S) is a Coxeter system. These generating reflections are called Coxeter generators or simple reflections.

Since the pairing between V and Vⱽ is W-invariant, if Π is a set of simple roots and if we define the Cartan matrix as being the n times n matrix C={rⱽ(r')} for r,r'∈Π, this matrix is independent of the chosen linear form up to simultaneous permutation of rows and columns. Since the action of sᵣ on r' for r,r'∈Π is given by sᵣ(r')=r'-C(r,r')r, the Cartan matrix determines the reflection representation of W.

For a crystallographic root system the Cartan matrix has integral entries, and in the basis Π (completed by a basis of the orthogonal), sᵣ has an integral matrix. All finite-dimensional (complex) representations of a finite Coxeter group can be realized over the field generated by the entries of the Cartan matrix.

The Cartan matrix is encoded in a Dynkin diagram, a tree with weighted edges and an orientation on edges of even weight >2, as follows. The vertices are indexed by the simple reflections; an edge is drawn between s and t if the order mₛₜ of st is greater than 2 and is given the weight mₛₜ. These weights are encoded by drawing the edge single for weight 3, double for weight 4 and triple for weight 6. The arrows indicate the relative root lengths (going from the longer to the shorter root) which may differ between different orbits of W on R. Alternately the Dynkin diagram can be obtained from the Cartan matrix as follows: if Cᵣₛ and Cₛᵣ are integers such that |Cₛᵣ|≥|Cᵣₛ|=1 there is an edge of weight |Cₛᵣ| from r to s with an arrow pointing to s if |Cₛᵣ|>1. Note that the Cartan matrices we consider here are not necessarily symmetric, contrary to the Cartan matrices we considered describing the reflection representation of a general Coxeter group; being symmetric corresponds to all roots being taken of the same length.

The irreducible crystallographic root systems are classified by the following list of Dynkin diagrams. The labeling of the nodes is the order of the generators and is shown by the function diagram.

Aₙ O—O—O—…—O   Bₙ O⇐ O—O—…—O  Cₙ O⇒ O—O—…—O  Dₙ O 2
   1 2 3 … n      1  2 3 … n     1  2 3 … n     ￨
                                              O—O—…—O
                                              1 3 … n

G₂ O⇛ O  F₄ O—O⇒O—O    E₆  O 2    E₇  O 2      E₈  O 2
   1  2     1 2 3 4        ￨          ￨            ￨
                       O—O—O—O—O  O—O—O—O—O—O  O—O—O—O—O—O—O
                       1 3 4 5 6  1 3 4 5 6 7  1 3 4 5 6 7 8

We get the Coxeter diagram, which describes the underlying Weyl group, if we ignore the arrows: we see that the root systems B_n and C_n correspond to the same Coxeter group (the Coxeter diagram is defined by the Coxeter matrix). Weyl groups can also be characterized as the finite Coxeter groups such that all off-diagonal entries of the Coxeter matrix are in {2,3,4,6}.

Here are the Coxeter diagrams for the finite Coxeter groups which are not crystallographic (I₂(e) is not crystallographic if e∉ {2,3,4,6}).

       e        5         5
I₂(e) O—O   H₃ O—O—O  H₄ O—O—O—O
      1 2      1 2 3     1 2 3 4

The function cartan gives the cartan matrix for an irreducible root system

julia> cartan(:D,4)
4×4 Matrix{Int64}:
  2   0  -1   0
  0   2  -1   0
 -1  -1   2  -1
  0   0  -1   2

julia> cartan(:I,2,5) # for type I₂(e) give e as 3rd argument
2×2 Matrix{Cyc{Int64}}:
       2  ζ₅²+ζ₅³
 ζ₅²+ζ₅³        2

Given two Cartan matrices c1 and c2, their matrix direct sum (corresponding to the orthogonal direct sum of the root systems) can be obtained by cat(c1,c2,dims=[1,2]).

The whole root system can be recovered from the simple roots and the corresponding coroots, since each root is in the orbit of a simple root. The restriction of the simple reflections to the span of R is determined by the Cartan matrix, so R is determined by the Cartan matrix and the set of simple roots.

The function rootdatum takes as arguments a matrix r whose lines represents the list of simple roots and another matrix cr whose lines are the corresponding coroots and produces a FiniteCoxeterGroup. Such an object is a permutation group containing in addition the description of a root system. cr*transpose(r) should be a Cartan matrix. Each element of the coxeter group is represented as the permutation it induces on the roots, coded as a permutation of 1:2N where we label the positive roots by 1:N, and the negative roots by N+1:2N.

If a single matrix argument is given to rootdatum it is taken as cr and r is taken to be the identity matrix; we get thus a particular root system where the roots are the canonical basis of V. For convenience, rootdatum(cartan(t...)) can be simplified to coxgroup(t...).

julia> W=coxgroup(:D,4) # same as rootdatum(cartan(:D,4))
D₄

julia> cartan(W)
4×4 Matrix{Int64}:
  2   0  -1   0
  0   2  -1   0
 -1  -1   2  -1
  0   0  -1   2

Also, the FiniteCoxeterGroup associated to a direct sum of irreducible root systems can be obtained as

julia> W=coxgroup(:A,2)*coxgroup(:B,2)
A₂×B₂

julia> cartan(W) # same as cat(cartan(:A,2), cartan(:B,2),dims=[1,2])
4×4 Matrix{Int64}:
  2  -1   0   0
 -1   2   0   0
  0   0   2  -2
  0   0  -1   2

The elements of a Weyl group are permutations of the roots:

julia> W=coxgroup(:D,4)
D₄

julia> p=W(1,3,2,1,3) # permutes the 24 roots
(1,14,13,2)(3,17,8,18)(4,12)(5,20,6,15)(7,10,11,9)(16,24)(19,22,23,21)

julia> word(W,p)
5-element Vector{Int64}:
 1
 3
 1
 2
 3

finally, a benchmark on julia 1.0.2

julia> @btime length(elements(coxgroup(:E,7)))
  531.385 ms (5945569 allocations: 1.08 GiB)

GAP3 for the same computation takes 2.2s