nLab
Coxeter group

Idea

A Coxeter group is a group determined by a Coxeter matrix, and is a combinatorial abstraction of the idea of a reflection group?.

Definition

A Coxeter matrix over an index set $I$ is a symmetric matrix

$$M:I\times I\to \{1,2,3,\dots ,\mathrm{\infty }\}$$M \colon I \times I \to \{1, 2, 3, \ldots, \infty\}

such that $M(i,i)=1$ for all $i\in I$, else $M(i,j)>1$. Writing $m_{i,j}=M(i,j)$, the associated Coxeter group $W_M$ is the group presented as having generators $s_i$, $i\in I$, and relations

$$(s_i{s}_j{)}^{m_{i,j}}=1$$(s_i s_j)^{m_{i, j}} = 1

for all $i,j\in I$, whenever $m_{i,j}\ne \mathrm{\infty }$. In other words, $m_{i,j}$ is the order of $s_i{s}_j$ (as is easily shown), and these orders determine the group.

A Coxeter group is usually more properly regarded as a group presentation rather than as an abstract group, but there is less than perfect consistency on this point in the literature. The $s_i$ are involutions that play the role of reflections generating the group.

Often Coxeter groups are specified by means of Coxeter diagrams. A Coxeter diagram associated with a Coxeter matrix is a multigraph whose vertices are indexed by $I$, and with $m_{i,j}-2$ edges between distinct vertices $i,j$. Coxeter diagrams are convenient visual aids; for example, involutions $s_i$, $s_j$ commute precisely when there are no edges between $i$ and $j$, and so the product of two Coxeter groups is specified by the disjoint union of their Coxeter diagrams.

Examples

Finite reflection groups

Let $V$ be a finite dimensional real Euclidean space, and suppose $G$ is a finite group generated by linear reflections of $V$ (each pointwise fixing a linear hyperplane and preserving the Euclidean metric). Then $G$ is a Coxeter group. Such finite Coxeter groups are also called spherical Coxeter groups (being subgroups of isometry groups of Euclidean spheres).

In this case, each generating reflection $s_i$ is the mirror reflection specified by the fixed hyperplane $H_i$, with $s_i(v_i)=-v_i$ for any $v_i$ orthogonal to $H_i$. It is easy to check that $m_{i,j}$ is the order of $s_i{s}_j$, where $\pi /m_{i,j}$ is the dihedral angle between $H_i$ and $H_j$. Moreover, the relations $(s_i{s}_j{)}^{m_{i,j}}=1$ suffice to specify the structure of the group, roughly because the dihedral angles uniquely determine a hyperplane arrangement up to an element of the orthogonal group, and the hyperplane arrangement determines the group in kaleidoscopic fashion, using the hyperplanes as mirrors.

Finite reflection groups have been completely classified. Notice that if $G$ and $H$ are finite reflection groups on $V$ and $W$ respectively, then $G\times H$ is a finite reflection group on $V\times W$. Such reflection groups are called reducible, and for the purposes of classification it suffices to consider just irreducible reflection groups. Also, if $G$ is a reflection group on $V$, we can regard it as a reflection group on $V\times ℝ$ in a trivial way, but we ignore such inessential extensions in our descriptions below. Thus it will suffice to consider only irreducible, essential finite reflection groups. The dimension of the Euclidean space on which the group acts will be indicated by a subscript (with mild and fixable exceptions for $E_7$ and $E_6$).

Irreducible essential finite reflection groups fall into four infinite families $A_n$, $B_n=C_n$, $D_n$, $I_2(m)$, together with a small number of exceptional groups:

1. $E_6$, $E_7$, $E_8$,
2. $F_4$,
3. $G_2$,
4. $H_3$, $H_4$.

The Coxeter matrices which specify these groups are often and traditionally encoded in the form of Coxeter diagrams, consisting of $n$ dots, and $k-2$ line segments between dots $i$ and $j$ if $m_{i,j}=k$. The case where $k=2$ (no line segments) means $s_i$ and $s_j$ commute. Coxeter diagrams are highly convenient; for example, there are a number of “coincidences” where various Coxeter groups in different families A-I are isomorphic, and these coincidences are visually apparent by seeing that their Coxeter diagrams are isomorphic. Similarly, the Coxeter diagram of a reducible group $G\times H$ is the disjoint union of the Coxeter diagrams for $G$ and $H$ separately, and so in the irreducible case we are only interested in connected Coxeter diagrams.

The family $A_n$

$A_n$ is the isometry group of a regular $n$-simplex, and is identified with the symmetric group $S_{n+1}$, where $s_i$ is identified with the permutation $(ii+1)$. We have $m_{i,i+1}=m_{i+1,i}=3$, and $m_{i,j}=2$ if $\mid i-j\mid \ge 2$. The condition $(s_i{s}_{i+1}{)}^3=1$ may be rewritten as a braid relation

$$s_i{s}_{i+1}{s}_i=s_{i+1}{s}_i{s}_{i+1}$$s_i s_{i+1} s_i = s_{i+1} s_i s_{i+1}

since the $s_i$ are involutions.

The family $B_n$

$B_n=C_n$ is the isometry group of a regular $n$-cube $\{-1,1{\}}^n$, and is identified with a wreath product $S_n⋉({\mathbb{Z}}_2{)}^n$. The generators may be given by $s_1,\dots ,s_{n-1},t_{n-1}$ where $s_i$ is the reflection through the hyperplane $x_i=x_{i+1}$ (i.e., swap the $i^{\mathrm{th}}$ and $(i+1{)}^{\mathrm{st}}$ coordinates), and $t_{n-1}$ is the reflection through the hyperplane $x_n=0$. The Coxeter diagram looks like this:

so that $s_{n-1}{t}_{n-1}$ is of order 4, but $s_i{t}_{n-1}$ is otherwise of order 2 (i.e., $s_i$ and $t_{n-1}$ commute).

Remark: The distinction between $B_n$ and $C_n$ is not apparent at the level of Coxeter groups, but rather at the level of root systems, used to classify simple complex Lie algebras. In other words, in this case there are two distinct root systems which generate the same reflection group.

The family $D_n$

$D_n$ is the linear isometry group on the set of integral vectors in ${ℝ}^n$ of length $\sqrt{2}$, of which there are $2n(n-1)$ many. It is not an isometry group of a regular solid, but it is a subgroup of $B_n$ of index 2. In this case there are involutions $s_1,\dots s_{n-1},t_{n-1}$ where $s_i$ is as described for the case $B_n$, and $t_{n-1}$ swaps and negates the last two coordinates. The Coxeter diagram looks like this:

We see by examining the Coxeter diagrams that $A_3\cong D_3$. The case $D_4$ on the other hand admits a symmetry of order 3, called triality?.

The family $I_2(m)$

The dihedral group of order $2n$ is the isometry group of a regular $n$-gon in the plane, or of the set $\{e^{2\pi ij/n}:1\le j\le n\}$ in ${ℂ}^1\cong {ℝ}^2$. This is generated by two reflections: complex conjugation, and reflection through the hyperplane orthogonal to $1+e^{2\pi i/n}$. The Coxeter diagram has $m-2$ edges between two vertices. There are coincidences $A_2\cong I_2(3)$, and $B_2\cong I_2(4)$.

There is also a coincidence $I_2(6)\cong G_2$ (which allows us to elide over the description of the Coxeter group $G_2$!). The distinction between them is again only at the level of root systems, where the root system of $G_2$ consists of the 12 vectors

$$\{e^{2\pi ij/6}\}\cup \{e^{2\pi ij/6}+e^{2\pi (j+1)/6}\}$$\{e^{2\pi i j/6}\} \cup \{e^{2\pi i j/6} + e^{2\pi (j+1)/6}\}

The groups $E_8$, $E_7$, $E_6$

There is a rich and fascinating literature on these structures; we confine ourselves only to a very succinct (and cryptic) description.

$E_8$ is the group of linear isometries of a root system consisting of vectors $x=(x_1,\dots ,x_8)$ in ${\mathbb{Z}}^8\cup (\mathbb{Z}+\frac{1}{2}{)}^8$ such that

$$\sum _i{x}_i\in 2\mathbb{Z},\mid x\mid =\sqrt{2}.$$\sum_i x_i \in 2\mathbb{Z}, \qquad {|x|} = \sqrt{2}.

Its Coxeter diagram is:

$E_7$ is the group of linear isometries of the subset of roots used for $E_8$ whose first two coordinates are equal. Its Coxeter diagram is:

$E_6$ is the group of linear isometries of the subset of roots used for $E_8$ whose first three coordinates are equal. Its Coxeter diagram is:

The group $F_4$

The group $F_4$ is the isometry group of the 24-cell?, which is a regular polyhedron in ${ℝ}^4$ consisting of the 8 unit quaternions $\pm 1$, $\pm i$, $\pm j$, $\pm k$ and the 16 unit quaternions given by $\frac{1}{2}({\epsilon }_{0}1+{\epsilon }_{1}i+{\epsilon }_{2}j+{\epsilon }_{3}k)$ where $({\epsilon }_0,\dots ,{\epsilon }_3)\in \{-1,1{\}}^4$. (These 24 quaternions form a group under multiplication, and this group is isomorphic to $D_4$.) The Coxeter diagram is:

The group $G_2$

See the discussion on $I_2(m)$ above.

The groups $H_3$, $H_4$

The group $H_3$ is the isometry group of the regular dodecahedron or of the regular icosahedron in ${ℝ}^3$, and is abstractly isomorphic to the group ${\mathbb{Z}}_2\times {\mathrm{Alt}}_5$, having 120 elements. Its Coxeter diagram is:

The group $H_4$ is the isometry group of a regular polyhedron in ${ℝ}^4$ known as the 120-cell, or of the dual polyhedron known as the 600-cell. Its Coxeter diagram is:

Affine reflection groups

Hyperbolic reflection groups

Properties of Coxeter groups

Theorem

Equality in Coxeter groups is decidable. In other words, there is an algorithm which, given two words $u$, $v$ in the generators $s_i$, determines in finitely many steps whether $u{v}^{-1}$ belongs to the relator subgroup.

Sketch of proof

Consider the equivalence relation on words generated by the relation $u\sim v$ if $v$ is obtained by replacing an alternating substring of the form $s_i{s}_j{s}_i\dots$ of length $m_{i,j}$ by the alternating substring $s_j{s}_i{s}_j\dots$ of the same length. Clearly each equivalence class has only finitely many members since all the word-lengths are the same. Then say that $u$ is reduced if no member of its equivalence class contains a substring of the form $s_i{s}_i$. If $u$ is unreduced, then $u$ is $\sim$-related to, hence in the same coset of the relator subgroup as, a $v$ which has such a substring $s_i{s}_i$, which in turn is in the coset of the word obtained by deleting $s_i{s}_i$, called a reduction of $u$. The algorithm proceeds by enumerating all words in the $\sim$-equivalence class of $u$, passing to the first reduction that arises, and iterating this process until one finally obtains a reduced word $w$; this will be in the same relator coset as $u$. Then, two reduced words are in the same relator coset if and only if they are $\sim$-equivalent, and more generally two words $u$, $v$ are in the same relator coset if and only if the algorithm applied to each produces two reduced words which are $\sim$-equivalent.

Reduced-word expressions for a group element $u$ may be visualized as paths of minimal length from the identity to $u$ in the Cayley graph? given by the group presentation (here, a simple graph whose vertices are group elements, with an edge between $u$ and $v$ if $s_{i}u=v$ for some generator $s_i$). Such reduced-word expressions are important in the study of buildings based on the Coxeter group, and also in the related study of BN-pairs?.

References

• N. Bourbaki, Groupes et Algèbras de Lie, Chapitres 4-6, Masson, Paris (1981).

• Kenneth Brown, Buildings, Springer Monographs in Mathematics, Springer 1989.