[ Main page | Part II. Word processing | Part III. Multiplication | Part IV. Closures ]
crm1.html

# Coxeter groups Part I. Geometry and combinatorics

by Bill Casselman
Introduction
 If \$S@ is any set, a Coxeter matrix indexed by \$S@ is a function \$m_{s,t}@ on \$S x S@ with values in either the positive integers or infinity, such that \$m_{s,s} = 1@ \$m_{t,s} = m_{s,t} > 1@ for distinct \$s@ and \$t@. There are naturally occurring cases where \$S@ is infinite, but in these notes \$S@ will be assumed to be finite. We shall see eventually that this is not a serious restriction. Associated to a Coxeter matrix is a Coxeter diagram. Its nodes are indexed by \$S@, and there is an edge between two nodes \$s@ and \$t@ if \$m_{s,t}@ is \$3@ or more. This edge is labeled by \$m_{s,t} ,@ usually only implicitly if \$m_{s,t} = 3 .@ The Coxeter matrix is said to be irreducible if its Coxeter diagram is connected. For example, if the Coxeter matrix is then its Coxeter diagram is . The Coxeter group \$W = W_{S}@ associated to a Coxeter matrix \$m@ is the group with generators \$S@ and relations \$s^{2} = 1@ \$st ... = ts ... @ (with \$m_{s,t}@ factors on both sides) whenever \$s@ and \$t@ are distinct and \$m_{s,t}@ is finite The rank of the group is the cardinality of \$S@. Relations of the second type are called braid relations. The group \$W@ does not on its own distinguish the subset \$S@, but often \$S@ is implicit in referring to a Coxeter group. More properly, the pair \$(W, S)@ is called a Coxeter system. This simple definition conveys, without elaboration, no idea of how interesting such groups are. They are among the most intriguing of all mathematical structures.
Elementary combinatorial consequences
 More precisely, the definition sets \$W@ to be the set of words in \$S@ (i.e. finite sequences \$s_{1} ... s_{n}@ of elements of \$S@) modulo an equivalence relation. Words \$x@ and \$y@ are equivalent if \$x@ is obtained from \$y@ by a chain of these elementary transformations: deleting a pair \$ss@; inserting a pair \$ss@; replacing one side of a braid relation by the other. Multiplication is defined by concatenation of words. The word \$1@ of length \$0@ is allowed, and corresponds to the identity element. Suppose for example that \$S@ has two elements \$s@ and \$t@, and that \$m_{s,t} = 3@. The braid relation is \$sts = tst@. Thus \$(st)^{3} = ststst@ can be transformed successively to \$ststst=stssts@, \$stssts=stts@, \$stts=ss@, \$ss=1@. Verify that if \$w = s_{1} ... s_{n}@ then \$w^{-1} = s_{n} ... s_{1}@. Verify that \$W@ is always a group. Verify in general that for all \$s@ and \$t@ the product \$st@ satisfies \$(st)^{m_{s,t}} = 1@. Verify that we could have stipulated \$W@ to be defined by relations \$(st)^{m_{s,t}} = 1@. If a Coxeter diagram decomposes into two components \$S_{1}@ and \$S_{2}@, then the corresponding group is a direct product of the groups parametrized by \$S_{1}@ and \$S_{2}@. Verify this last claim. All words in an equivalence class have the same parity - either even or odd. The sign of \$w@ is defined to be \$1@ if its parity is even, \$-1@ if odd. The sign is a homomorphism from \$W@ to the multiplicative group of \$1@, \$-1@. A word is said to be reduced if it is of minimal length in its equivalence class. The length \$l(w)@ is the common length of all the reduced words of \$w@. The following is an immediate consequence of this definition: The length has these properties: \$l(xy) l(x) + l(y)@; \$l(w^{-1}) = l(w)@; \$l(w) = 0@ if and only if \$w@ is the identity; \$l(w) = 1@ if and only if \$w@ lies in \$S@ (more properly, has a representative in \$S@); \$sign(w) = (-1)^{ l(w)}@; \$l(ws) = l(w) + 1@ or \$l(w) - 1@; \$l(sw) = l(w) + 1@ or \$l(w) - 1@; The last two assertions are proven by a simple parity argument. The right weak Bruhat order on \$W@ is defined by the condition that \$ws > w@ if \$l(ws) = l(w) + 1@, therefore also \$ws < w@ if \$l(ws) = l(w) - 1@. Similarly for the left order. Verify this claim. Suppose that \$S@ has two elements \$s@ and \$t@. Let \$m = m_{s,t} .@ (a) If \$m@ is finite, verify directly from the definition that \$W@ has \$2m@ elements, and that exactly one of them has two expressions as reduced words. (Hint. It is straightforward to see there are no more than \$2m@ elements. To see that there are exactly that number, represent the group by permutations of \$2m@ elements, effectively that corresponding to left multiplication on the group itself. ) (b) If \$m@ is infinite, verify that every element of \$W@ has exactly one reduced expression, and that elements of \$W@ - other than the identity - correspond bijectively to sequences \$st ...@ and \$ts ...@ with no repetitions. If \$T@ is a subset of \$S@, then the inclusion of \$T@ in \$S@ induces a canonical map from \$W_{T}@ to \$W_{S}@. It is not clear a priori that this is an embedding, although it will turn out that this is so, or that a shortest expression of an element in the image by elements of \$T@ will also be one by elements of \$S@. For the moment, all we can see easily is that if \$w@ is an element of \$W_{T}@ with image \$w_{*}@ in \$W_{S}@, then \$l(w_{*}) l(w)@.
Reflections
It is possible to develop the subject of Coxeter groups entirely in combinatorial terms (this is done - well, at least thoroughly attempted - in the book by Bourbaki), but certain geometric representations of Coxeter groups, in which the group acts discretely on a certain domain, and in which the generators are represented by reflections, allow one to visualize nicely what is going on.

Recall that a linear reflection is a linear transformation fixing a hyperplane passing through the origin and acting as multiplication by \$-1@ on a line through the origin transverse to this hyperplane.

There are other kinds of reflections, too, but they reduce to linear ones. They are discussed at the end of this section. Single reflections If \$s@ is a reflection in a space \$V@, there exists a linear functional \$a@ and a vector \$a^{v}@ so that the reflection takes \$v@ to

\$ v - < a, v > a^{v}@.

The hyperplane fixed by the reflection is where \$a = 0@, and \$a^{v}@ is mapped to its negative as long as \$< a , a^{v} > = 2@.

The function \$a@ and vector \$a^{v}@ are unique up to non-zero scalar multiples. If \$a@ is replaced by \$ca@ then \$a^{v}@ is replaced by \$c^{-1}a^{v}@.

Often a reflection will be orthogonal with respect to some inner product , when the reflection takes \$v@ to

\$ v - 2 (a^{v} v) / (a^{v} a^{v}) @.

In this situation, the dot product induces a linear map from \$V@ to the linear dual space \$V^{*}@, and \$a@ is the image of \$2 a^{v} / (a^{v} a^{v})@.

The group \$GL(V)@ acts by its definition on \$V@, and on \$V^{*}@ according to the prescription \$< ga, gv > = < a, v >@. (If vectors are column vectors, then linear functions are row vectors and the canonical pairing is the matrix product \$a v@. If \$g@ is represented by the matrix \$M@ then \$g@ takes \$v@ to \$Mv@ and \$a@ to \$a M^{-1}@.) At any rate, the group \$GL(V)@ acts transitively on pairs \$(a, a^{v})@, hence all reflections are conjugate to each other. Pairs of reflections Suppose \$s@ and \$t@ to be a pair of reflections. Such pairs turn out to make up essentially a one-parameter family of conjugacy classes.

Let \$s@ and \$t@ be a pair of reflections, say corresponding to \$a, a^{v}@ and \$b, b^{v}@. Define associated real constants

 \$c_{s, t} = < a, b^{v} >@ \$c_{t, s} = < b, a^{v} > . @

Let \$(s_{1}, t_{1})@ and \$(s_{2}, t_{2})@ be pairs of reflections, conjugate under the linear transformation \$g@. Then

 \$ga_{1} = c_{a} a_{2}@ \$ga_{1}^{v} = c_{a}^{-1} a_{2}^{v}@ \$gb_{1} = c_{b} b_{2}@ \$gb_{1}^{v} = c_{b}^{-1} b_{2}^{v}@

for some non-zero constants \$c_{a}@ and \$c_{b}@, and consequently \$c_{s2, t2} = (c_{b}/c_{a}) c_{s1, t1}@, \$c_{t2, s2} = (c_{a}/c_{b}) c_{t1, s1}@. The constants \$c_{s, t}@ and \$c_{t, s}@ are therefore not conjugation-invariant, but the product \$n_{s,t} = c_{s, t}c_{t, s}@ is. For generic pairs it will turn out to possess a simple interpretation.

One way to understand conjugation-invariant phenomena is to consider geometrical configurations - for example, how the various hyperplanes and lines relate qualititatively to each other. One possibility is that in which the reflection hyperplanes of \$s@ and \$t@ are the same. In this case we may take \$a = b@. Then
 \$c_{s, t} = < a, b^{v} > = < b, b^{v} > = 2@ \$c_{t, s} = < b, a^{v} > = < a, a^{v} > = 2@
so that \$n_{s, t} = 4@. Similarly \$n_{s, t} = 4@ when \$a^{v}@ and \$b^{v}@ are linearly dependent.

When \$n_{s, t}@ is not equal to \$4@, then \$a@ and \$b@ are linearly independent, as are \$a^{v}@ and \$b^{v}@. The plane spanned by \$a^{v}@ and \$b^{v}@ is transverse to the linear subspace of codimension \$2@ where \$a@ and \$b@ are both equal to \$0@.

Only the last claim remains to be proven. Verify the last claim.

We are especially interested in the case where \$n_{s, t} = 4@ but \$a@ and \$b@ are linearly independent. If \$L@ is the intersection of the kernels of \$a@ and \$b@, then \$s@ and \$t@ induce reflections on the two-dimensional quotient \$V / L@. In this plane \$a^{v}@ and \$b^{v}@ are linearly dependent. We have \$c_{s, t}c_{t, s} = < a, b^{v} > < b, a^{v} > = 4@, and we can scale \$a@ so that in fact \$c_{s, t} = c_{t, s}@, both being equal to \$2@ or \$-2@. In either case, \$a^{v}@ and \$b^{v}@ lie on a single line through the origin, and both \$s@ and \$t@ transform a vector \$v@ in a direction parallel to that line. In particular the products \$st@ and \$ts@ are shears along that line.

 \$s@ \$t@

The region on one side of that line and in between the two lines \$a=0@ and \$b=0@ will be a fundamental domain for the group acting on the corresponding open half-plane. If we choose the signs of \$a@ and \$b@ correctly we may assume that this region is that where \$a > 0@ and \$b > 0@. In that case, with our normalization, \$c_{s , t} = c_{t, s} = -2@. In the situation described above, explain how \$s@ and \$t@ act on the space \$V^{*}@ dual to \$V@. This is of importance in the theory of Kac-Moody Lie algebras, since \$V^{*}@ contains the roots of the algebra. Show that in dimension \$2@ there are three conjugacy classes of pairs \$(s, t)@ with \$n_{s, t} = 4@ and in dimensions greater than \$2@ there are four.

From now on, suppose that \$n_{s, t}@ is not equal to \$4@. Then the vectors \$a^{v}@ and \$b^{v}@ span a plane transversal to the intersection of the kernels of \$a@ and \$b@, and in effect we may restrict ourselves to dimension \$2@. In these circumstances, reflections fix lines.

There is one other exceptional collection of cases to deal with - when \$n_{s, t} = 0@. This happens only when either \$c_{s, t} = < a, b^{v} > = 0@ or \$c_{t, s} = < b, a^{v} > = 0@. If both are equal to \$0@, then \$s@ and \$t@ are a commuting pair of reflections whose product amounts to multiplication by \$-1@. The group generated by \$s@ and \$t@ has four elements, and any one of the four quadrants is a fundamental domain.

Otherwise, suppose that \$< a, b^{v} > = 0@, but \$< b, a^{v} >@ is not equal to \$0@. We may arrange that \$< b, a^{v} >@ is in fact positive.

Then the line \$a = 0@ is fixed by both \$s@ and \$t@. The reflection \$s@ interchanges the two sides of this line, but \$t@ preserves it. The pair of reflections \$t@ and \$sts@ now both stabilize each side of the line \$a = 0@, and the \$n@-invariant of this pair is \$4@, since they share the eigenvector \$b^{v}@. Therefore from what have already learned in this case, we know that with a suitable choice of sign for \$b@ the region \$C@ where \$b > 0@ and \$sb > 0@ on the side of the line where \$a > 0@ is a fundamental domain for the group generated by \$t@ and \$sts@. Furthermore, the reflection \$s@ takes \$C@ to \$-C@. Note also that the vector \$a^{v}@ lies in its interior, as shown in the figure. Later on we shall need a simple consequence of this clear picture of how the pair \$s@ and \$t@ act: in this case the region where \$a > 0@, \$b > 0@ is not a fundamental domain for the group generated by \$s@ and \$t@. Or, in other words, if \$n_{s, t} = 0@ and this region is a fundamental domain then \$s@ and \$t@ are a commuting pair of reflections, and \$c_{s, t}@ and \$c_{t, s}@ both vanish.

From now on, we assume \$n_{s, t}@ to be neither \$0@ nor \$4@.

If \$n@ be neither \$0@ nor \$4@, there is a unique conjugacy class of pairs \$(s, t)@ of reflections with \$n_{s, t} = n@.

Let \$s@ be any reflection, say corresponding to \$a@, \$a^{v}@. All choices of \$s@ are certainly conjugate. We may as well take \$a@ to be the function \$x@ and the vector \$a^{v}@ to be \$(1, 0)@. The matrices commuting with \$s@ are then the diagonal matrices. We now look for \$b@ and \$b^{v}@ with \$< b, b^{v} > = 2@, \$< a, b^{v} > < b, a^{v} > = n@. Let \$b@ be any linear function independent of \$a@ and not vanishing on \$a^{v}@. All choices are conjugate by a linear transformation preserving \$a@ and \$a^{v}@. Suppose \$c = < b, a^{v} >@. It remains to choose \$b^{v}@ independent of \$a^{v}@ with \$< a, b^{v} > = n/c@. This requires that \$n@ differ from \$4@, and then all choices are conjugate by a linear transformation fixing both the line \$a = 0@ and that through \$a^{v}@.

Take \$a^{v}@ and \$b^{v}@ as a basis of \$V@. The matrices of \$s@, \$t@, and \$st@ are then

 , ,

As one consequence, \$-2 + n_{s,t}@ is the trace of \$st@, hence clearly conjugation-invariant.

Suppose \$n_{s, t}@ to be neither \$0@ nor \$4@. Then there exists a non-degenerate quadratic form invariant under both \$s@ and \$t@, unique up to scalar multiple. It will be definite if and only if \$0 < n_{s, t} < 4@.

Suppose that \$u v@ is an inner product invariant under \$s@ and \$t@. This happens if and only if \$a^{v}@ is perpendicular to the line \$a = 0@, and similarly for \$b^{v}@ and \$b@. The space of vectors fixed by \$s@ is spanned by \$c_{s, t} a^{v} - 2b^{v}@, and that fixed by \$t@ is spanned by \$2a^{v} - c_{t, s} b^{v}@. For invariance, therefore, we must have

 (c_{s, t} a^{v} - 2b^{v}) a^{v} = 0 (2a^{v} - c_{t, s} b^{v}) b^{v} = 0 c_{s, t} (a^{v} a^{v}) - 2 (b^{v} a^{v}) = 0 c_{s, t} (a^{v} a^{v}) = 2 (b^{v} a^{v}) 2 (a^{v} b^{v}) - c_{t, s} (b^{v} b^{v}) = 0 c_{t, s} (b^{v} b^{v}) = 2 (a^{v} b^{v})

Since \$n_{s, t}@ is not \$0@, neither \$c_{s, t}@ nor \$c_{t, s}@ vanish. Therefore the single number \$a^{v} b^{v}@ determines the inner product on all of \$V@.

The matrix of the quadratic form is

In order for the form to be definite, it is necessary and sufficient that \$c_{s, t}@ and \$c_{t, s}@ have the same sign, and that the determinant be positive. Therefore we must have \$0 < n_{s, t} < 4@.

In order for the group generated by \$s@ and \$t@ to be finite, it is necessary that one of these hold:

• \$s = t@ (when \$n = 4@);
• \$s@ and \$t@ commute (when \$n = 0@);
• \$n = 4 cos^{2} p / m@ for some positive integers \$m@ and \$p < m@.
In the last case, the region \$a > 0@ and \$b > 0@ will be a fundamental domain for the group precisely when \$p = 1@, and \$c_{s, t}@ and \$c_{t, s}@ are both negative.

The picture accompanying the last assertion is this:

Prove this in detail.

Suppose now that \$n@ is not \$4@, and that \$s@ and \$t@ generate an infinite group. We want again to see when the region \$a > 0@, \$b > 0@ is a fundamental domain. From one of the Propositions just proven, we must have \$n > 4@ or \$n < 0@.

The elements \$s@ and \$t@ generate an infinite group with fundamental domain \$a > 0@, \$b > 0@ if and only if \$n@ is greater than or equal to \$4@, and both \$c_{s, t}@ and \$c_{t, s}@ are negative.

The case \$n = 4@ has been dealt with. It remains to show that \$n@ cannot be negative. This case can be eliminated by using the invariance of the pair of lines where the indefinite metric vanishes. The following images portray what things look like (the red lines are where the invariant indefinite quadratic form vanishes):

 \$n > 4@ \$n < 0@
Finish the proof. (Hint: the reflection \$s@ preserves the `cones' through which \$a = 0@ passes. What does it do to the other two? This situation is somewhat like the one we saw where \$n = 0@.)

In summary:

Assume that \$s@ and \$t@ are a pair of reflections in space with reflection data \$a@, \$a^{v}@ and \$b@, \$b^{v}@. Assume also that the region \$a > 0@, \$b > 0@ is a fundamental domain for the group they generate. Exactly one of the following cases occurs:

• \$s@ and \$t@ commute, and \$c_{s, t} = c_{t, s} = 0@;
• \$st@ has finite order \$m > 2@, and \$n_{s, t} = 4 cos^{2} /m@;
• \$st@ has infinite order and \$n 4@.

In the last two cases, \$c_{s, t}@ and \$c_{t, s}@ are both negative. Affine reflections An affine reflection reflects points in an affine hyperplane \$f(x) = 0@ for some affine function \$f(x)@. The function \$f@ can be expressed as

\$f(x) = < a, x > + c@

for some linear function \$a@ and constant \$c@. The linear function \$a@ is the gradient of \$f@, and for any point \$x@ in \$V@ and vector \$v@ we have \$f(x + v) = f(x) + < a, v >@. The reflection then takes a point \$x@ to \$x - f(x) a^{v}@ for some vector \$a^{v}@ in \$V@ with \$< a, a^{v} > = 2@.

An affine reflection is a special case of a linear one, through the familiar trick of embedding an affine space of dimension \$n@ into a vector space of dimension \$n+1@. Thus \$v@ in \$V@ maps to \$(v, 1)@ in a larger space \$V_{#}@. Let \$@ be the function on \$V_{#}@ taking \$(v, x)@ to \$x@. The affine reflection on \$V@ corresponding to \$a@, \$a^{v}@, and \$c@ is the restriction to \$V@ of the reflection defined by the linear function \$a + c @ on \$U@. In the discussion of pairs of reflections with \$n = 4@ we have already seen an implicit example of this. Non-Euclidean reflections A non-Euclidean reflection reflects points of a non-Euclidean space in a non-Euclidean hyperplane. This also can be explained in terms of linear reflections.

The non-Euclidean space \$H_{n}@ of \$n@ dimension is the component \$Q(x) = x_{n+1}^{2} - x_{1}^{2} - ... - x_{n}^{2} = 1@, \$x_{n+1} > 0@ of the hyperbolic sphere, which can be parametrized by Euclidean space \$E_{n}@ according to the formula

It is taken into itself by the connected component of the orthogonal group of \$Q@ and there is a unique Riemannian metric on it invariant under this group and restricting to the Euclidean metric at \$(0, 0, ... , 0, 1)@. There are two models of this in Euclidean space of \$n@ dimensions, the familiar Poincaré model and the slightly less familiar Klein model. (There is also, for \$n=2@, the upper half-plane, but that is another story.) Both models identify \$H@ with the interior of the unit ball in \$E_{n}@ centred at the origin.

For the Klein model, this ball is identified with the intersection of the slice \$x_{n+1} = 1@ of the region \$Q(x) > 0@ (the interior of a homogeneous cone). A point \$x@ on \$H@ maps to \$x_{*} = x/x_{n+1}@. It happens that a non-Euclidean geodesic line between two points \$x@ and \$y@ is the intersection with \$H@ of the plane through the origin containing \$x@ and \$y@, and this intersects the slice in a line between \$x_{*}@ and \$y_{*}@. Thus in the Klein model. points of \$H@ are identified with points of the interior of a unit ball, and geodesics between such points are line segments in the ball.

The Poincaré model is a transformation of the Klein model. A point \$x@ in the interior of the unit ball in \$E_{n}@ maps to the point above it on the upper hemisphere in \$E_{n+1}@, then by South pole stereographic projection back onto the equator. In this transformation, geodesics become arcs of circles perpendicular to the boundary of the unit ball.

The point for us is that non-Euclidean reflections are those induced on the hyperbolic sphere, or either of its models, by linear reflections in \$E_{n+1}@. For both models, we start with a hyperplane \$a = 0@ which intersects the region \$Q(x) > 0@ and a vector \$a^{v}@ transverse to it. In the Klein model, we take a point \$x@ in the slice \$Q(x) > 0@, \$x_{n+1} = 1@ to \$x - < a, x > a^{v}@ and then project it back onto the slice. We have seen examples of this also in the discussion above of pairs of linear reflections with \$n > 4@. In the Poincaré model we unravel by stereographic projection, reflect, and ravel again. Design an algorithm to draw the geodesic between two points of the unit disc in the Poincaré model. There are two ways to approach this problem, depending on the tools available for drawing. (1) Suppose all you can do is produce line segments and circles, then you must first decide whether to draw a line or a circle; if it is a circle, you must find the centre, radius, and arc. This becomes delicate only for points nearly lying on a diameter of the unit disc, and suffers to some extent from stability. Discuss how serious this is, analyzing how continuously your drawing depends on the two points. (2) if you can draw Bezier curves, then you should probably use them to approximate circles. Use one or two bisections to allow a reasonable approximation; then use velocity vectors to find the control points. The best way to do all this is likely through stereographic projection, since the geodesics in the disc correspond to simple latitude circles on the sphere.

Examples
In this section we shall look at some Coxeter groups defined geometrically. Finite dihedral groups Suppose \$P@ to be a regular polygon in the plane. That is to say, it is a polygon of \$m@ sides for some \$m > 2@, centred at the origin, and invariant under rotations by \$2 / m@.

Rotations are not its only symmetries, since any line through the center of any of its sides and the origin, or any of its corners and the origin, is an axis of mirror symmetry. Since any symmetry must take a corner into some other corner, and can either preserve or reverse orientation, there are \$2m@ symmetries altogether, in which the rotations form a subgroup of order \$2@.

The symmetry group of a regular polygon of \$m@ sides is a Coxeter group with two generators, say \$s@ and \$t@. We have \$m_{s, t} = m@.

This should be clear from the picture. The generators \$s@ and \$t@ should be chosen to be reflections in neighbouring axes of symmetry, as the red lines in the figure.

They are orthogonal reflections, with the angle between their lines of reflection equal to \$/m@. Choosing the signs of \$a^{v}@ and \$b^{v}@ correctly, we have \$a^{v} b^{v} = -2 cos (/m)@. The region where \$a > 0@ and \$b > 0@ is a fundamental domain \$C@ for the symmetry group.

The \$2m@ elements of the group can be expressed as

\$1@, \$s@, \$t@, \$st@, \$ts@, ... , \$st ... = ts ...@ (\$m@ terms)

We can see how these elements match up with transforms of \$C@ in this picture:

Affine dihedral groups Now we look at the group generated by affine reflections in the points at the end of a line segment in one dimension.

It is an infinite Coxeter group with two generators, say \$s@ and \$t@, and with \$m_{s, t}@ infinite. As we have already seen, the realization by affine reflections is the restriction to a line of a linear Coxeter group in dimension \$2@. Again, if \$a@ and \$b@ are chosen correctly, the region where \$a > 0@ and \$b > 0@ is a fundamental domain for the group.

The elements of the group can be expressed as

\$1@, \$s@, \$t@, \$st@, \$ts@, \$sts@, \$tst@, ...
Hyperbolic dihedral groups Now we look at the group generated by two hyperbolic reflections in the ends of a segment on the hyperbola \$Q(x, y) = 1@, where \$Q@ is an indefinite non-degenerate quadratic form. It, too, is an infinite Coxeter group with two generators. And again, if \$a@ and \$b@ are chosen correctly, the region where \$a > 0@ and \$b > 0@ is a fundamental domain for the group.

An observation about groups of rank two The examples we have just examined exhaust the possible representations of rank two Coxeter groups with the property that the region \$C@ where \$a > 0@, \$b > 0@ is a fundamental domain. An observation we shall need later, based on observation of these cases, is that

In these circumstances, if \$s@ is a generator in \$S@ then \$sw > w@ if and only if \$C@ and \$wC@ lie on the same side of the line \$a_{s} = 0@. .

In brief, the argument for this is that if \$sw > w@ then \$w = ts .. @, and the shortest gallery (sequence of contiguous chambers) from \$C@ to \$swC@ through chambers is the reflection of the one from \$C@ to \$wC@, except that it starts with an extra transition from \$C@ to \$sC@. To be more explicit, the shortest gallery from \$C@ to \$wC@ is the sequence \$C@, \$tC@, \$stC@, ... and is reflected into the longer gallery \$C@, \$sC@, \$stC@, \$stsC@, ... Groups of rank 3 Suppose now that \$s_{0}@, \$s_{1}@, and \$s_{2}@ generate a Coxeter group \$W@ of rank \$3@ with Coxeter matrix \$(m_{i, j})@ for \$i@, \$j = 1@, \$2@, \$3@. I assume that all the \$m_{i, j}@ are finite, so that all the dihedral groups \$W_{i, j}@ are finite. How can we tell whether \$W@ is finite?

We know that the standard representation preserves a metric in which \$|a_{i}|^{2} = 1@ for all \$i@ and \$a_{i} a_{j} = -cos (/m_{i, j})@ for \$i@ distinct from \$j@. If we assume that the indexing is chosen so that \$m_{1, 2}@ differs from \$2@, then by choosing coordinates suitably (so that the finite Coxeter group generated by the first two reflections stabilizes the \$(x, y)@-plane) we can arrange this metric to be \$x^{2} + y^{2} + c z^{2}@ with \$c = 1@, \$0@, or \$-1@, and \$a_{1} = (1, 0, 0)@, \$a_{2} = (-cos /m_{1,2}, sin /m_{1,2}, 0)@. In order to find \$a_{3}@ we have to take into account the conditions

• |a_{3}|^{2} = 1@
• a_{3} a_{1} = - cos /m_{1, 3}
• a_{3} a_{2} = - cos /m_{2, 3}
We may assume that \$a_{3} = (x, y, z)@ with \$z > 0@. So these equations become
• x^{2} + y^{2} + c x_{3}^{2} = 1@
• (x, y, z) (1, 0, 0) = - cos /m_{1,3}
• (x, y, z) (-cos /m_{1, 2}, sin /m_{1, 2}, 0) = - cos /m_{2, 3}
or
• \$x = - cos /m_{1,3}@
• \$cos /m_{1, 3} cos /m_{1, 2} + y sin /m_{1,2} = - cos /m_{2, 3}@
• @cz^{2} = 1 - x^{2} - y^{2}@

Let \$r = 1 - 1/m_{1, 2} + 1/m_{1, 3} + 1/m_{2, 3}@. Then

• if \$r < 0@ then \$c > 0@ and \$W@ is finite;
• if \$r = 0@ then \$c = 0@ and \$W@ stabilizes a half-plane, and it acts by affine reflections on a plane parallel to its boundary;
• if \$r > 0@ then \$c < 0@ and the group acts by non-Euclidean reflections.
It all depends on how \$ - /m_{2, 3}@ compares to \$/m_{1, 2} + /m_{1, 3}@. For example, if they are equal, then the cosine sum formula allows us to set \$y = sin /m_{1, 3}@. This gives us \$x^{2} + y^{2} = 1@, \$c = 0@, \$z@ arbitrary. The group preserves the whole \$(x, y)@ plane. Etc.

Here is a table of cases of possible values of the \$m_{i, j}@ in weakly increasing order:

 Finite: \$2@, \$3@, \$3@; \$2@, \$3@, \$4@; \$2@, \$3@, \$5@; Affine: \$3@, \$3@, \$3@; \$2@, \$4@, \$4@; \$2@, \$3@, \$6@;
The regular solids The classification of the finite Coxeter groups in three dimensions is intimately related to the classification of the regular solids. Verify that the Coxeter subgroup with values of \$m@ equal to \$2@, \$3@, \$3@ is the symmetry group of the regular tetrahedron. Verify that the Coxeter subgroup with values of \$m@ equal to \$2@, \$3@, \$4@ is the symmetry group of the cube and the regular octahedron. \$2@, \$3@, \$4@ Verify that the Coxeter subgroup with values of \$m@ equal to \$2@, \$3@, \$5@ is the symmetry group of the icosahedron and the dodecahedron. Prove directly that the symmetry group of any regular polyhedron is a Coxeter group. Verify that the symmetry group of the regular simplex in \$n@ dimensions is a Coxeter group. Verify that the symmetry group of the cube in \$n@ dimensions is a Coxeter group. Affine Coxeter groups of rank 3

 Affine A2 Affine B2 Affine G2
A hyperbolic Coxeter group of rank 3

 Poincaré model Klein model
Cartan matrices

A polyhedral realization of a Coxeter group is a linear representation in which

• The group possesses a fundamental domain \$C@ which is a polyhedral cone;
• the generators in \$S@ are represented by reflections in the walls of this cone.
I do not exclude the case where the cone is invariant under translation. This for a group with a single generator a single hyperplane is admissible in any dimension. In these notes, we shall use only simplicial realizations where the polyhedral cone is simplicial, its walls parametrized by \$S@. The dimension of a simplicial realization must be at least the rank of the group.

Every Coxeter group possesses at least one realization, as we shall see in a moment. Geometric properties of realizations translate naturally to combinatorial properties of the group. From the geometry of the simplices neighbouring a fundamental domain, for example, you can read off the Coxeter matrix. This is because if \$L@ the intersection of two walls, then the configuration in the neighbourhood of \$L@ is essentially that in a realization of the group generated by the two reflections in those walls. This is a special case of a very general result proven in most generality by MacBeath around 1964.

Given a realization, make a choice for each \$s@ in \$S@ of a pair \$a_{s}@, \$a_{s}^{v}@ defining reflection in the wall of the fundamental domain parametrized by \$s@. The sign of each function \$a_{s}@ can (and always will) be made so that \$a_{s} > 0@ in the interior of the given fundamental domain. Such a linear function \$a_{s}@ is determined up to a positive scalar multiple, and its equivalence class under such multiplications will be called a basic root of the realization (and implicitly also of the choice of fundamental domain). The half-space \$A_{s}@ where \$a_{s} > 0@ is determined by this class, and will be called a basic geometric root of the realization. The hyperplane \$a_{s} = 0@ will be called a basic root hyperplane. This terminology is not common, but for general Coxeter groups this notion of root is entirely natural, since the particular choice of \$a_{s}@ has no intrinsic significance. This is not the case if the Coxeter group is the Weyl group of a Kac-Moody Lie algebra, since in that case the roots themselves are part of the structure of the Lie algebra.

The Cartan matrix associated to a choice of functions \$a_{s}@ is the matrix \$c_{s, t} = < a_{s}, a_{t}^{v} >@. If the \$a_{s}@ are chamnged to \$d_{s}a_{s}@ then \$c_{s, t}@ is cahmnged to \$d_{s} c_{s, t} d_{t}^{-1}@. This gives rise to a new matrix \$DCD^{-1}@ where \$D@ is a diagonal matrix with positive entries. But the numbers \$n_{s,t} = c_{s, t}c_{t, s}@ depend only on the realization itself. The next result is a consequence of observations made earlier about conjugacy classes of pairs of reflections:

In any realization, the Cartan matrix satisfies these conditions:

1. \$c_{s, s} = 2@;
2. \$c_{s, t} = 0@ if and only if \$c_{t,s} = 0@;
3. \$c_{s, t}@ is either \$0@ or a negative number;
4. if \$n_{s, t}@ lies between \$0@ and \$4@ then it is equal to \$4 cos^{2} (/m_{s, t})@.
This theorem is apparently due originally to Vinberg. A real matrix \$C@ satisfying these conditions for a given Coxeter matrix is called an abstract Cartan matrix. It determines a Coxeter matrix in a natural way. The numbers \$n_{s, t}@ will always be non-negative; the finite values of \$m_{s, t}@ are determined by conditions (2) and (4) for the values of \$n_{s, t}@ lying in \$[0, 4)@; and \$m_{s, t}@ is infinite for \$n@ which are \$4@ or larger.

Any Cartan matrix clearly gives rise to a representation of the associated Coxeter group. In fact:

The representation of a Coxeter group determined by any abstract Cartan matrix is a realization of the associated Coxeter group.

This will be proven in the next section. One consequence is that every Coxeter group has at least one realization, since there exists always the standard Cartan matrix

\$c_{s,t} = -2 cos(/m_{s,t}) . @

Cartan matrices with integral matrices determine Kac-Moody Lie algebras. In this case the representation of its Weyl group on the lattice of roots is the one associated to this Cartan matrix. Coxeter groups which occur as the Weyl groups of Kac-Moody algebras are called crystallographic, and are distinguished by the property that for them the numbers \$m_{s, t}@ are either \$2@, \$3@, \$4@, \$6@ or infinite.

Two Cartan matrices \$C_{1}@ and \$C_{2}@ will give rise to isomorphic representations of a Coxeter group if and only if there exists a positive diagonal matrix \$D@ with \$C_{2} = D C_{1} D^{-1}@. In particular, those Cartan matrices giving rise to realizations equivalent to the standard one are symmetrizable.

If each \$m_{s, t}@ is finite, then the isomorphism classes of Cartan realizations are parametrized by \$H^{1}( , R)@ (where \$@ is the Coxeter diagram).

If all \$m_{s, t}@ are finite, then all Cartan matrices are of the form \$c_{s, t} d_{s, t}@ where \$c_{s, t} = -2 cos^{2}/m_{s, t}@ and \$d_{s, t}@ is an arbitrary matrix of positive real numbers with \$d_{t, s} = 1/d_{s, t}@. Two of these will give isomorphic represntations of \$W@ when the entries differ by factors \$d_{s}/d_{t}@, with all \$d_{s} > 0@. But the assignment of \$d_{s, t}@ to \$(s, t)@ defines a cocycle on the Coxeter graph with values in the multiplicative group of positive real numbers, and assignments \$d_{s}/d_{t}@ are coboundaries. Conclude by applying the logarithm.

If \$W@ is finite, then the Coxeter diagram has no circuits.

Because if the diagram were not a tree, the group would possess a continuous family of non-isomorphic representations of dimension \$r@.

Distinct classes can give rise to realizations with very different geometric properties. We have seen this already in the case of the infinite dihedral group, and here are the pictures for two different realizations of the Coxeter group whose Coxeter diagram is :

 The Klein model of the standard realization The Kac-Vinberg realization

The first of these is associated to the standard Cartan matrix, and the second to the integral matrix

which is that of a certain hyperbolic Kac-Moody Lie algebra. It is the second, therefore, which is likely to have intrinsic significance. Does the Coxeter group of rank \$3@ with all \$m_{s, t} = 3@ have non-equivalent Cartan matrices? (This is a research problem! ) Prove that the boundary of the second is non-smooth everywhere (i.e. even though it does have tangent lines everywhere, it will not likely be \$C^{2}@). (This conjecture is consistent with, but not directly related to, a curious result of Kac & Vinberg, which asserts that if the boundary of the slice we are looking at is smooth, it is an ellipse. This problem will appear more reasonable after we have looked at the role of finite automata in the geometry of Coxeter groups.)

Geometry and combinatorics
 For the moment, fix a Cartan matrix. It gives rise to a representation of its associated Coxeter group, in which the elements of \$s@ act by reflections. This will be called for the moment a Cartan representation. The principal result connecting combinatorics and the geometry of a Coxeter group is this: Suppose \$w@ in \$W@, \$s@ in \$S@. Suppose that \$a_{s}@ is a basic root in a Cartan representation of \$W@. Then \$sw > w@ if and only if \$wC@ lies entirely in the region \$a_{s} > 0@. This generalizes what we have already seen for groups of rank two. The proof is somewhat intricate. . It begins with If \$T@ is a subset of \$S@ and \$w@ is any element of \$W@, then there exists \$u@ in \$W_{T}@ and \$x@ in \$W@ such that (a) \$tx > x@ for all \$t@ in \$T@; (b) \$l(w) = l(u) + l(x)@. This result will be made more precise later on, where we discuss the cosets \$W_{T}\W@ in more detail. of the Lemma. The following algorithm computes \$u@ and \$x@: ``` x := w u := 1 while tx < x for some t in T x := tx u := ut ``` Since the length of \$x@ decreases in every iteration of the loop, the algorithm certainly stops. When it does so, \$tx > x@ for all \$t@ in \$T@. In order to prove the Lemma, it suffices to verify that conditions (b) and (c) hold, and also that \$w = ux@, whenever entry into the loop is tested. They certainly hold at the first test, so it remains to see that they are not destroyed in the loop. Equality \$w = ux@ is certainly preserved. Since \$l(w) = l(u) + l(x)@ to start and \$l(w) = l(ut tx)@, we also have \$l(u) + l(x)@ is at most \$l(ut) + l(tx)@. But since \$tx < x@, \$ut > u@, and we must have \$l(ut) + l(tx) = l(u) + l(x)@. Thus at the end of the loop we still have \$l(w) = l(u) + l(x)@. We now prove Theorem 3 by induction on \$l(w)@. If \$w = 1@ there is no problem. Suppose \$l(w) > 1@. If \$x = sw < w@ it must be shown that \$a_{s}@ is negative on \$wC@. But then \$wC = sxC@; by induction \$a_{s}@ is positive on \$xC@, hence \$sxC@ lies in the region where \$a_{s} < 0@. Now suppose \$sw > 0@. It must be shown that \$a_{s} > 0@ on \$wC@. Choose \$t@ such that \$tw < w@. Find \$u@ in \$W_{s,t}@ and \$x@ in \$W@ satisfying the conditions of the Lemma. Since \$tw < w@, \$l(x) < l(w)@. Since \$sx > x@ and \$tx > x@, induction lets us see that \$xC@ is contained in the region \$C_{s,t}@ where \$a_{s} > 0@ and \$a_{t} > 0@. Since \$l(w) = l(u) + l(x)@, \$l(su) = l(u) + 1@, and this is still valid if \$l@ is the length in \$W_{s,t}@. From the discussion on groups of rank two, we see that \$a_{s} > 0@ on the region \$uC_{s,t}@, hence on \$wC = uxC@ as well.
Roots
 A root of a realization is the transform of one of the basic roots by an element of \$W@. If \$b = w(a_{s})@ is a root then \$g s g^{-1}@ is reflection in the hyperplane \$b = 0@. Thus if \$b@ is a root so is \$-b@. The fundamental chamber \$C@ of the representation is the intersection of all the root half-spaces \$a_{s} > 0@. A root is called positive if it contains the chamber \$C@, negative if its opposite contains \$C@. Every root is either positive or negative. The point is that the chamber \$C@ is not intersected by a root hyperplane. This result follows immediately from Theorem 3. A reformulation: If \$wC@ intersects \$C@ then \$w = 1@. If \$w@ is not equal to \$1@, then there exists \$s@ with \$sw < w@. But then \$C@ and \$wC@ lie on opposite sides of the hyperplane \$a_{s} = 0@. In other words, every Cartan representation is a realization of the group as a subgroup of \$GL(V)@. If we restrict the realization to the subgroup generated by \$T@, we see that \$W_{T}@ embeds into \$W@, too. For a subset \$T@ of \$S@, let \$C_{T}@ be the region in the boundary of \$C@ where the basic roots \$a_{t} = 0@ for \$t@ in \$T@, \$a_{s} > 0@ for \$s@ not in \$T@. Every point of \$C_{T}@ is fixed by \$t@ in \$T@, hence all elements of the subgroup \$W_{T}@. Conversely: 3. Let \$@ be the closure of \$C@. If \$w@ intersects \$@ then the intersection equals the closure of \$C_{T}@ for some \$T@, and \$w@ lies in \$W_{T}@. By induction on \$l(w)@. If \$w = 0@ or \$1@, no problem. Otherwise, say \$sw < w@ and \$w = sx@ for \$l(x) < l(w)@. Then \$a_{s} 0@ on \$x@ while \$a_{a} 0@ on \$w@. Therefore the intersection of \$C@ and \$wC@ lies in \$a_{s} = 0@. But then the intersection of \$x@ and \$@ is non-empty, so we can apply the induction hypothesis. We deduce that the intersection of \$x@ and \$@ is equal to the the closure of some \$C_{T}@, and \$x@ lies in \$W_{T}@. But then \$sC@ intersects \$C_{T}@ as well, and \$s@ lies in \$T@ also. Hence \$w@ lies in \$W_{T}@. Any face of a chamber of a realization is the \$W@-transform of a unique face of \$C@. If \$xC_{U} = yC_{T}@, then \$y^{-1}xC_{U} = C_{T}@. But then \$y^{-1}x@ must lie in \$W_{T}@. In other words, each face of a chamber is labeled by a unique subset \$T@. A gallery is a sequence of chambers \$C_{i}@ with each successive pair sharing a face of codimension one. If \$w = s_{1} ... s_{n}@ then the sequence \$C@, \$s_{1}C@, \$s_{1}s_{2}C@, ... , \$s_{1}s_{2} ... s_{n}C@ is a gallery. The chambers \$C@ and \$sC@ share a face labeled by \$s@, and hence \$wC@ and \$wsC@ do, too. Minimal galleries correspond to reduced words. For \$w@ in \$W@, let \$L_{w}@ be the set of positive roots \$r@ such that \$w^{-1}r@ is negative - i.e. \$r > 0@ on \$C@ but \$r < 0@ on \$wC@. This means that the root hyperplane \$r = 0@ separates \$C@ from \$wC@. In any gallery linking \$C@ to \$wC@ it must be one of the walls between two successive chambers in the gallery. Therefore: The root hyperplanes for \$r@ in \$L_{w}@ are those separating \$C@ from \$w^{-1}C@. A minimal gallery from \$C@ through \$xC@ to \$xyC@ can be split into two disjoint pieces, one from \$C@ to \$xC@, the other from \$xC@ to \$xyC@. The second is the \$x@-transform by \$x@ of a gallery from \$C@ to \$yC@. Therefore: If \$l(xy) = l(x) + l(y)@ then \$L_{xy}@ is the disjoint union of \$L_{x}@ and \$xL_{y}@. The length \$l(w)@ is the cardinality of \$L_{w}@. The length of \$w@ is the number of root hyperplans separating \$C@ from \$wC@. An element \$w@ lies in \$W_{T}@ if and only if \$L_{w}@ is contained in \$T@. Let \$R^{+}@ be the set of positive roots, \$R_{T}@ those generated by \$W_{T}@ from the \$a_{t}@ with \$t@ in \$T@. An element of \$W_{T}@ permutes the roots in \$R^{+} - R_{T}^{+}@. A reduced word for \$w@ in \$W_{T}@ is one also in \$W@. In every coset \$W_{T} \ W@ there exists a unique element \$x@ such that \$tx > x@ for all \$t@ in \$T@. For any \$w@ in this coset, \$l(w) = l(wx^{-1}) + l(x)@. Let \$W^{T}@ be the set of these distinguished coset representatives. Any element \$w@ can be expressed as \$w = xy@ with \$x@ in \$W_{T}@ and \$y@ in \$W^{T}@. These last will be left as exercises.
The chambers are parametrized by elements of \$W@, and the geometrical structure of the complex they make up mirrors the structure of \$W@. These chambers are simplicial cones embedded in the vector space \$V@, and the left action of \$W@ on \$V@ is compatible with the left action of \$W@ on itself. But there is also a right action of \$W@ on itself, and this corresponds to a right action of \$W@ on the set of chambers. If \$C_{*} = xC@ is a chamber then \$C_{*}w = xwC@ defines the right transform of \$C_{*}@ by \$w@. Thus \$xC = Cx@. The right action of generators is particularly simple: \$C_{*}@ and \$C_{*}s@ share a wall of codimension one labeled by \$s@.

The following pictures illustrate how this works on the affine Weyl group of \$A_{2}@. The chambers are really three dimensional simplicial cones, and we are looking at a slice through them, in which the generators are represented by affine reflections.

 s_{2}C s_{1}s_{2}C s_{3}s_{1}s_{2}C s_{2}s_{3}s_{1}s_{2}C

If \$w = s_{1}s_{2} ... s_{n}@, then this word representation of \$w@ corresponds in a simple fashion to a gallery from the fundamental chamber \$C@ to \$wC@ - namely, the chain of chambers \$C@, \$s_{1}C@, \$s_{1}s_{2}C@, ... , \$s_{1}s_{2} ... s_{n}C@, in that order. We read the path from left to right.

The Tits cone
 Define \$@ to be the union of the closed chambers of a realization. A vector \$v@ lies in \$@ if and only if the set of positive roots \$b@ with \$< b, v > < 0@ is finite. It is to be shown that if the set of roots \$b@ with \$< b, v > < 0@ is finite, then \$v = wu@ for some \$u@ in the closure of \$C@. If the set of such roots is empty then already \$v@ lies in \$C@. Otherwise, \$< a_{s}, v > < 0@ for some \$s@. Now \$s@ permutes the set \$R^{+} - { a_{s} } @, hence \$L_{sv} = s(L_{v} - { a_{s} })@, which has size one less than \$L_{v}@. Apply induction. The region \$@ is convex. It is called the Tits cone. The following are equivalent: The group \$W@ is finite; The set of roots is finite; The Tits cone is all of \$V@. Prove that in every double coset \$W_{X}\ W / W_{Y}@ there is a unique element of least length. The face \$C_{T}@ lies in the interior of \$@ if and only if \$W_{T}@ is finite. Every finite subgroup of \$W@ lies in the conjugate of some finite \$W_{T}@.
Classification
These are the Coxeter diagrams for those irreducible Coxeter groups which are finite:

 \$A_{n} ( n 1)@: \$B_{n} = C_{n} (n 2)@ : \$D_{n} (n 4)@ : \$E_{6}@ : \$E_{7}@ : \$E_{8}@ : \$F_{4}@ : \$G_{2}@ : \$H_{3}@ : \$H_{4}@ : \$I_{p} (p = 5, 7)@ :

This is justified in VI.4 of the book by Bourbaki. The basic idea is to check when the standard realization preserves a positive definite quadratic form. These are the cases when the Tits `cone' is the whole vector space. The starting point is that the Coxeter diagram cannot contain any circuits. Another easy remark is that the number of branches from any point can be at most \$3@. But from there the argument is complicated. The argument of Bourbaki uses the criterion that \$W@ is finite if and only if the quadratic form left invariant by \$W@ in the standard realization is definite. An argument along different lines can presumably be put together using ideas of Kac and Vinberg. How large are these groups?

These are the Coxeter diagrams for those irreducible Coxeter groups which can be interpreted as affine reflections:

 \$A_{1}^{~}@: \$A_{n}^{~} ( n 2)@: \$B_{2}^{~}@ : \$B_{n}^{~} (n 2)@ : \$C_{n}^{~} (n 2)@ : \$D_{n}^{~} (n 4)@ : \$E_{6}^{~}@ : \$E_{7}^{~}@ : \$E_{8}^{~}@ : \$F_{4}^{~}@ : \$G_{2}^{~}@ :

This also is in the book by Bourbaki. These are the cases when the Tits `cone' is a half-space. The aim of this exercise and the next two is to explain how the regular polyhedra in all dimensions of Euclidean space are classified in terms of Coxeter diagrams. Recall that a regular polyhedron is a polyhedron in Euclidean space whose symmetry group acts transitively on the faces of any given dimension. Prove that the symmetry group of any regular polyhedron in \$n@ dimensions is a Coxeter group, and that the fundamental domain of the action is a slice through a fundamental domain in a realization of the group. (Hint: Start with dimensions \$2@ and \$3@. ) Suppose that \$v@ is a vector in a realization of a finite Coxeter group. We may assume that \$v@ lies in the closure of a fundamental domain for the group. Let \$T@ be the complement of the set of generators fixing \$v@. Let \$P@ be the convex hull of the \$W@ orbit of \$V@. Show that the faces of \$P@ meeting the fundamental domain are parametrized by the connected components of the Coxeter diagram containing \$T@ (Hint: if \$X@ is such aset, the face will be the orbit of \$v@ under \$W_{X}@.) (c) Show that \$P@ will be a regular polyhedron if and only if \$T@ is a single generator and the Coxeter diagram has no branches. Prove that the regular Euclidean polyhedra are classified by isomorphism classes of (a) a Coxeter diagram associated to a finite Coxeter group together with (b) a single node of the diagram on its boundary. List explicitly all the ones occurring in dimension \$4@.

References
 N. Bourbaki, Chapitres IV, V, VI of Groupes et algebres de Lie, Hermann, Paris, 1968. James Humphreys, Reflection groups and Coxeter groups, Cambridge Press, 1990. V. Kac, Infinite dimensional Lie algebras, Cambridge University Press. E. B. Vinberg, Discrete linear groups generated by reflections, Math. U. S. S. R. Izvestia 5 (1971). V. Kac and E. B. Vinberg, Quasi-homogeneous cones (in Russian), Math. Zametki 3 (1967), pp. 347-354. R. Howlett, lecture notes available on the Internet (http://www.maths.usyd.edu.au/): Miscellaneous facts about Coxeter groups (June, 1993) and Introduction to Coxeter groups (February, 1996). A. M. MacBeath, Annals of Mathematics 79 (1964).