Coxeter Groups

Introduction

A Coxeter group is a group generated by involutions whose only relations specify the orders of the products of pairs of the generators. The definition is so simple that the class appears everywhere: the finite Coxeter groups are the finite groups generated by reflections, the symmetric groups are the Coxeter groups of type $A$, the dihedral groups are the Coxeter groups of type $I_2(m)$, and the affine Coxeter groups are the symmetry groups of the regular tilings and of the root lattices. Because the presentation is completely explicit, the combinatorial theory of a Coxeter group is accessible: there is a length function, a canonical rewriting procedure, and a classification of the finite and affine members of the class by their diagrams.

This article is the fourteenth of the corpus and the fifth of the group articles, below the foundational layer and Infinite Abelian Groups, Solvable and Nilpotent Groups, Combinatorial Group Theory and Infinite Groups. It uses the presentation theory and the word problem of Combinatorial Group Theory, the free products of Generators, Presentations and Free Products, and the permutation groups of Groups . The treatment here is of Coxeter groups as abstract groups with a presentation: the diagrams, the length function, the exchange and deletion conditions, Matsumoto's theorem, the word problem, the classification of the finite and affine Coxeter groups, and the orders of the finite ones. The realisation of a Coxeter group as a group generated by reflections of a vector space, and the Weyl groups with their root systems, require a bilinear form and a distance and belong to Part II; they are named and deferred.

Coxeter Systems and Diagrams

Coxeter Matrices and Systems

Definition. A Coxeter matrix on a finite set $S$ is a symmetric matrix $(m_{st})_{s,t \in S}$ with entries in $\{1,2,3,\ldots\} \cup \{\infty\}$ such that $m_{ss} = 1$ and $m_{st} \geq 2$ for $s \neq t$. The Coxeter group of the matrix is the group with the presentation

$$ W = \left\langle s \in S \;\middle|\; s^2 = 1 \text{ for all } s \in S,\ (st)^{m_{st}} = 1 \text{ for all } s \neq t \text{ with } m_{st} < \infty \right\rangle, $$

and the pair $(W, S)$ is a Coxeter system. The rank of the system is $|S|$. When $m_{st} = \infty$ no relation between $s$ and $t$ is imposed, and $st$ has infinite order.

Definition. The Coxeter diagram of $(W,S)$ is the graph with vertex set $S$, with an edge labelled $m_{st}$ between $s$ and $t$ whenever $m_{st} \geq 3$. The convention of the diagrams is to omit the label when $m_{st} = 3$, to write the value on the edge when $m_{st} \geq 4$, and to draw a heavy or dashed edge when $m_{st} = \infty$. The system is irreducible if the diagram is connected.

Proposition. Every Coxeter group splits as the free product of the Coxeter groups of the connected components of its diagram, so a Coxeter system is determined by its irreducible components.

Proof. The generators of two different components have no relation between them in the presentation, and a group presented by generators with no relation between two disjoint sets is the free product of the groups presented by the two sets, by the universal property of the free product.

Examples

Example (type $I_2(m)$). The Coxeter group of rank $2$ with $m_{st} = m$ has the presentation $\langle s,t \mid s^2 = t^2 = (st)^m = 1\rangle$, which is the dihedral group of order $2m$; the translation to the presentation $\langle r, s \mid r^m = s^2 = 1,\ srs = r^{-1}\rangle$ of Solvable and Nilpotent Groups is by $r = st$. The rank-$2$ Coxeter groups are therefore exactly the finite dihedral groups together with the infinite dihedral group $D_\infty$, the case $m = \infty$.

Example (type $A_n$). The Coxeter group with generators $s_1, \ldots, s_n$ and relations $s_i^2 = 1$, $(s_i s_{i+1})^3 = 1$ and $(s_i s_j)^2 = 1$ for $|i - j| \geq 2$ is isomorphic to the symmetric group $S_{n+1}$, with $s_i$ corresponding to the transposition $(i\ i+1)$.

Proof. The transpositions $(i\ i+1)$ satisfy the relations: they are involutions, $(s_i s_{i+1})^3 = 1$ is the braid relation $(i\ i+1)(i+1\ i+2)(i\ i+1) = (i+1\ i+2)(i\ i+1)(i+1\ i+2)$, and disjoint transpositions commute. Hence the map from the presented group to $S_{n+1}$ is well defined and surjective. For injectivity one uses the length function and the exchange condition below: every element of the presented group has a reduced expression $s_{i_1}\cdots s_{i_k}$ in which no letter can be deleted, and two such expressions are related by the braid relations; since the corresponding products of transpositions satisfy the same reduced-word combinatorics as the permutations they produce, a word representing the identity must reduce to the empty word, so the map is injective.

Example (the symmetric group as type $A$). The identification $A_n \cong S_{n+1}$ gives the Coxeter structure of the symmetric groups; $A_1 = S_2$, $A_2 = S_3$ (which is $I_2(3)$), and $A_3 = S_4$ are the smallest cases.

The Combinatorial Theory

The Length Function and Reduced Expressions

Definition. A word in $S$ is a sequence $s_1\cdots s_k$ of elements of $S$; the word is reduced if it is of the least length among all words representing the same element of $W$, and the length $\ell(w)$ of $w \in W$ is the length of a reduced word for $w$. By convention $\ell(1) = 0$.

Proposition. The length function satisfies

$$ \ell(ws) = \ell(w) + 1 \quad\text{or}\quad \ell(ws) = \ell(w) - 1 $$

for every $w \in W$ and $s \in S$, and $\ell(w) \equiv \ell(w') \pmod{2}$ whenever $w$ and $w'$ are related by a sequence of relations; hence $\varepsilon(w) = (-1)^{\ell(w)}$ is a well-defined map $W \to \{\pm 1\}$ and is a homomorphism.

Proof sketch. If $w = s_1\cdots s_k$ is reduced then $\ell(ws) \leq k+1$ and, if $\ell(ws) = k+1$, the word $s_1\cdots s_k s$ is reduced; the alternative $\ell(ws) = k-1$ occurs exactly when $s = s_k$. For the parity statement, each defining relation of the presentation has even total length in $S$: $s^2$ has length $2$ and $(st)^{m}$ has length $2m$, so all relations change the length parity by an even amount, and the length parity is therefore a homomorphism on the group.

Definition. The exchange condition holds in $(W,S)$ if, whenever $w = s_1 \cdots s_k$ is reduced and $s \in S$ satisfies $\ell(sw) < \ell(w)$, there is an index $i$ with

$$ sw = s_1 \cdots \widehat{s_i} \cdots s_k, $$

where the hat means the term is deleted.

Theorem (exchange and deletion conditions). The exchange condition holds in every Coxeter system. Consequently, if a word $s_1\cdots s_k$ is not reduced, then it contains two letters that cancel after a single deletion: there are indices $i < j$ with $s_i = s_j$ and

$$ s_1 \cdots s_k = s_1 \cdots \widehat{s_i} \cdots \widehat{s_j} \cdots s_k, $$

and iterating gives a reduced word for the same element.

Proof sketch. The deletion condition is a reformulation of the exchange condition, obtained by applying the exchange condition at the first letter where the length fails to increase; the exchange condition itself is proved by induction on $\ell(w)$ from the defining relations, using that in a rank-2 parabolic subgroup the two possible reductions of a word of length $2m$ are the two halves of the longest element.

Matsumoto's Theorem and the Word Problem

Definition. The braid moves in a Coxeter system replace a subword $stst\cdots$ of length $m_{st}$ by the subword $tsts\cdots$ of the same length, where the length is $m_{st}$ and the two words are the two alternating products of $s$ and $t$.

Theorem (Matsumoto). Two reduced words represent the same element of $W$ if and only if they are related by a sequence of braid moves.

Proof sketch. One shows by induction on the length that any two reduced words for $w$ are braid-equivalent, using the deletion condition: if the two words begin with different letters $s \neq t$, then $sw$ and $tw$ both have length $\ell(w)-1$, and the exchange condition produces positions at which the letters can be removed, reducing the problem to words of smaller length after a braid move at the beginning. The induction is on $\ell(w)$ and uses the rank-two case, in which the braid relation is exactly the defining relation $(st)^m = 1$.

Corollary (the word problem for Coxeter groups). The word problem is solvable for every finitely presented Coxeter group: given a word in $S$, apply the deletion condition repeatedly to reduce its length, and test whether the reduced word is empty.

Proof sketch. The deletion condition gives a terminating procedure: scan the word and, whenever a letter can be deleted, delete it; the length decreases strictly, so the procedure halts, and by the theorem the result is a reduced word for the same element. The word represents the identity exactly when its reduction is the empty word. The procedure is effective because the braid relations are the only identifications needed (Matsumoto).

Corollary. Coxeter groups are automatic in the sense of the theory of automatic groups: there is a finite automaton recognising the reduced words for the elements, and another recognising pairs of reduced words differing by one generator, so the word problem is solvable in quadratic time and the regular language of reduced words provides a normal form.

The combinatorial theory above is the reason Coxeter groups are the best-understood infinite groups: they have a canonical normal form, a solvable word problem, and a finite presentation whose relations are exactly the braid relations and the involutions.

Finite Coxeter Groups

The Classification

Theorem (classification of finite Coxeter groups). An irreducible Coxeter system $(W,S)$ is finite if and only if its diagram is one of the following, and the finite irreducible Coxeter diagrams are exactly these:

The list is due to Coxeter, and the group $I_2(m)$ is the dihedral group of order $2m$; the types $A_2 = I_2(3)$, $B_2 = I_2(4)$, $G_2 = I_2(6)$ and $A_3 = D_3$ are the coincidences among the small members of the list. The exceptional diagrams were given explicitly: $E_6$ is the diagram with a node joined to three branches of lengths $1, 2, 2$; $E_7$ and $E_8$ lengthen the branch of length $2$ to lengths $3$ and $4$; $F_4$ is the path with the double bond in the middle position, distinguishing it from $B_4$, whose double bond is at the end.

Theorem (order via the degrees). For a finite Coxeter group the reflection degrees $d_1, \ldots, d_n$ are the integers appearing in the table below, and

$$ |W| = d_1 d_2 \cdots d_n. $$

The verification accompanying this article recomputes each order as the product of the degrees and compares it with the closed formula: $2\cdot 3\cdots(n+1) = (n+1)!$ for $A_n$, $2^n n!$ for $B_n$, $2^{n-1}n!$ for $D_n$, and the exceptional products $1152$, $12$, $120$, $14400$, $51840$, $2903040$, $696729600$.

Corollary. A Coxeter group is finite if and only if it is generated by reflections of a finite-dimensional vector space; this realisation, and the construction of the reflection representation from the Coxeter matrix, requires a bilinear form and belongs to Part II. The abstract classification above is stated without it, in terms of the diagrams.

Parabolic Subgroups

Definition. A parabolic subgroup of $(W,S)$ is a subgroup generated by a subset $T \subseteq S$; it is denoted $W_T$.

Theorem. For $T \subseteq S$ the pair $(W_T, T)$ is a Coxeter system whose diagram is the subdiagram induced by $T$. The intersection $W_T \cap W_{T'}$ is $W_{T \cap T'}$, and the cosets of parabolic subgroups have canonical representatives: every element $w \in W$ has a unique decomposition $w = w^T w_T$ with $w_T \in W_T$ and $w^T$ of minimal length in its coset, and $\ell(w) = \ell(w^T) + \ell(w_T)$.

Proof sketch. The presentation of $W_T$ is the restriction of the presentation of $W$ to the generators in $T$, so there is a homomorphism $W_T \to W$, and it is injective by the exchange condition applied within the subdiagram. For the decomposition, the set of minimal-length coset representatives is characterised by the condition that it contains no generator $s \in T$ on the right; the product decomposition and the length additivity follow from the exchange condition.

Example. For type $A_n$ with $S = \{s_1,\ldots,s_n\}$, the parabolic subgroup generated by a subset $T$ corresponding to a composition of $n+1$ is a product of symmetric groups, and the coset representatives are the permutations with a prescribed descent pattern. The parabolic structure of the Coxeter system is the combinatorial form of the subgroup structure of the symmetric group.

Affine Coxeter Groups

Affine Diagrams

Definition. An irreducible Coxeter system is affine if its diagram is obtained from the diagram of an irreducible finite Coxeter group by adding one vertex, the added vertex being joined to the others as in the affine diagrams; the resulting types are $\widetilde A_n$ ($n \geq 2$), $\widetilde B_n$ ($n \geq 3$), $\widetilde C_n$, $\widetilde D_n$, $\widetilde E_6$, $\widetilde E_7$, $\widetilde E_8$, $\widetilde F_4$, $\widetilde G_2$ and $\widetilde A_1$.

Theorem (classification of affine Coxeter groups). An irreducible Coxeter system is infinite and has all proper parabolic subgroups finite if and only if its diagram is an affine diagram, and the affine diagrams are exactly the connected diagrams obtained by adding one vertex to a connected finite diagram. Equivalently, the affine Coxeter groups are the irreducible infinite Coxeter groups whose diagrams are positive semidefinite in the sense of the reflection representation, a formulation that belongs to Part II.

Example. The affine type $\widetilde A_1$ is the infinite dihedral group: the diagram is two vertices joined by an edge labelled $\infty$, and the group is $D_\infty = \mathbb{Z} \rtimes \mathbb{Z}/2$ of Infinite Groups. The affine type $\widetilde A_2$ has the presentation $$ \widetilde A_2 = \langle s_0, s_1, s_2 \mid s_i^2 = 1,\ (s_is_j)^3 = 1 \text{ for } i \neq j\rangle, $$ so it is generated by three involutions with pairwise products of order $3$; its finite parabolic subgroups are the copies of $A_1$, $A_2$ and $A_1 \times A_1$ generated by proper subsets of $\{s_0,s_1,s_2\}$. In general $\widetilde A_n$ is the semidirect product $S_{n+1} \ltimes \Lambda$, where the abelian group $\Lambda$ is free abelian of rank $n$; the identification of $\Lambda$ with the translation group of the reflection representation, and the construction of that representation, belong to Part II.

Theorem (growth of affine Coxeter groups). An affine Coxeter group is virtually abelian: it contains a free abelian subgroup of finite index. Consequently the affine Coxeter groups are exactly the infinite Coxeter groups of polynomial growth, the remaining infinite Coxeter groups having exponential growth; the growth is counted with respect to the length function $\ell$ above, so it is a purely combinatorial invariant of the presentation.

The geometric form of the last theorem — the reflection representation, its translation subgroup, the Tits cone and the geometry of the growth — is developed in Part II. The algebraic content used here is that the affine group is infinite with finite parabolics and is not a free product of finite groups.

Examples and Special Cases

Symmetric Groups

The identification $A_n \cong S_{n+1}$ gives the Coxeter structure of the symmetric group, and it is the model for the combinatorial theory: reduced words in the Coxeter generators correspond to the classical reduced decompositions of a permutation into adjacent transpositions, the length is the inversion number, and Matsumoto's theorem is the statement that two reduced decompositions of a permutation are connected by braid moves. The exchange condition is the exchange property of the weak order on the symmetric group.

Proposition. In type $A_n$ the length of $w \in S_{n+1}$ is its inversion number:

$$ \ell(w) = \#\{(i,j) : i < j,\ w(i) > w(j)\}, $$

and the longest element $w_0$ has length $\binom{n+1}{2}$ and order $2$, sending $i$ to $n+2-i$.

Proof sketch. Each adjacent transposition $s_i$ changes the inversion number by $\pm 1$, so the inversion number is a lower bound for the length, and the bubble-sort procedure constructs a reduced word of exactly that length, using that a permutation with an inversion has an adjacent pair out of order which can be swapped to decrease the inversion number. The longest element reverses the order, and it has the stated length and order.

Dihedral and Rank-Two Cases

Proposition. In type $I_2(m)$ the Coxeter group has $2m$ elements: $m$ elements of the form $(st)^k$ for $k = 0,\ldots,m-1$ and $m$ elements of the form $(st)^k s$, each of the latter being an involution. For $m = \infty$, the group is the infinite dihedral group and the elements are the powers of $st$ and their products with $s$.

Proof. The computation is the one for the dihedral groups in Solvable and Nilpotent Groups; the relation $(st)^m = 1$ makes the powers of $st$ cyclic of order $m$, and the coset of $s$ gives the remaining $m$ elements.

Example (hyperbolic Coxeter groups). A Coxeter group whose diagram is neither finite nor affine is hyperbolic in the rough sense that it is not virtually abelian while all its proper parabolics may be finite; the triangle groups $\langle s_1, s_2, s_3 \mid s_i^2 = 1,\ (s_is_j)^{m_{ij}} = 1\rangle$ with $1/m_{12} + 1/m_{23} + 1/m_{31} < 1$ are the basic examples. The geometric description of such groups as reflection groups of the hyperbolic plane belongs to Part II; the algebraic statement is that the group is infinite, generated by three involutions, and not virtually abelian.

Summary

A Coxeter system $(W,S)$ is given by involutions $s$ with relations $(st)^{m_{st}} = 1$, and it is encoded by a Coxeter matrix and a diagram. The length function $\ell$ and its parity give the sign homomorphism, the exchange and deletion conditions provide a rewriting procedure, and Matsumoto's theorem says that two reduced words represent the same element exactly when they are related by braid moves. Consequently the word problem is solvable for every finitely presented Coxeter group, and Coxeter groups are automatic with a regular language of reduced words as a normal form.

The finite irreducible Coxeter groups are classified by their diagrams: the families $A_n$, $B_n$, $D_n$, $I_2(m)$ and the exceptional types $E_6$, $E_7$, $E_8$, $F_4$, $G_2$, $H_3$, $H_4$, with orders $(n+1)!$, $2^n n!$, $2^{n-1}n!$, $2m$, $51840$, $2903040$, $696729600$, $1152$, $12$, $120$, $14400$, all of which are the products of the reflection degrees. Parabolic subgroups $W_T$ are Coxeter systems on the induced subdiagrams, and every element has a unique decomposition into a minimal coset representative and an element of $W_T$. The affine Coxeter groups are the connected diagrams obtained from the finite diagrams by adding one node; they are infinite with finite parabolics and are virtually abelian. The realisation of Coxeter and Weyl groups as reflection groups, the root systems, the reflection representation and the Tits cone belong to Part II and are not used here.

Summary of Notation

Further Reading

• James E. Humphreys, Reflection Groups and Coxeter Groups (Cambridge University Press, 1990), for the combinatorial theory, the classification and the reflection representation.
• Nicolas Bourbaki, Groupes et algèbres de Lie, chapters IV–VI (Hermann, 1968), for the classification of Coxeter systems and the parabolic structure.
• Anders Björner and Francesco Brenti, Combinatorics of Coxeter Groups (Springer, 2005), for the length function, the exchange condition and Matsumoto's theorem.
• Hideya Matsumoto, "Générateurs et relations des groupes de Weyl généralisés", Comptes Rendus de l'Académie des Sciences de Paris 258 (1964), 3419–3422, for the braid relation theorem.
• Harold S. M. Coxeter, "Discrete groups generated by reflections", Annals of Mathematics 35 (1934), 588–621, for the classification of the finite reflection groups.
• Brigitte Brink and Robert B. Howlett, "A finiteness property and an automatic structure for Coxeter groups", Mathematische Annalen 296 (1993), 179–190, for the automatic structure and the word problem.