Complex Reflection Groups

Arun Ram
Department of Mathematics and Statistics
University of Melbourne
Parkville, VIC 3010 Australia
aram@unimelb.edu.au

Last update: 10 January 2014

Section II

Proposition 2. Let Γ𝒞. Then W(Γ) admits an antiautomorphism, denoted ww, which fixes the generators r1,,r.

Proof.

W=F/N where F is a free group on generators y1,,y and N is generated, as a normal subgroup, by the elements uij = yiyjyi qijfactors yj-1yi-1yj-1 qijfactors qijodd uij = yiyjyiyj qijfactors yi-1yj-1yi-1yj-1 qijfactors qijodd together with the elements yipi. Now F has an antiautomorphism fixing the generators y1,y. We denote this by xx for xF. Put u=uij. If qij is odd, yjyiyj qij u = yiyjyi qij = u yjyiyj qij . If qij is even, yiyjyiyj qij u = yjyiyjyi qij = u-1 yiyjyiyj qij . If the first case u is conjugate to u and in the second u is conjugate to u-1. Thus uN. It follows that N=N and hence W(Γ) has an antiautomorphism fixing r1,,r.

Proposition 3. Let Γ𝒞 and let V be an dimensional complex vector space. Define ρ:W(Γ)GL(V) by ρ(w)=θ(w)t for wW(Γ). Then ρ is a representation of W(Γ).

Proof.

Obvious.

Keeping in mind that ρ(ri)=Sit, the connection between the representations θ and ρ of W(Γ) is further clarified by

Proposition 4. Let Γ𝒞 and let A denote the matrix for the Hermitian form H(Γ) with respect to the basis {v1,,v}. By abuse of notation, for 1i, we let Si denote the matrix for the linear transformation Si=θ(ri) in the basis {v1,,v}. Then ASi=SitA.

Proof.

We view all matrices as elements of End(V) which have been written with respect to the basis {v1,,v} of column vectors for V and we write (x,y) for H(Γ)(x,y) if x,yV. Then letting 1k we compute ASi(vk) = A ( vk+(εi-1) (vk,vi) (vi,vi) vi ) = j=1 (vj,vk)vj+ (εi-1) (vk,vi) (vi,vi) j=1 (vj,vi)vi = j=1 [ (vj,vk)+ (εi-1) (vk,vi) (vi,vi) (vj,vi) ] vj and SitA(vk) = Sit ( j=1 (vj,vk) vj ) = j=1 (vj,vk) Sit(vj) = j=1ji (vj,vk)vj+ (vi,vk) j=1ji (vj,vi) (vi,vi) (εi-1)vj+ (vi,vk)εivi = j=1ji [ (vj,vk)+ (vi,vk) (vj,vi) (vi,vi) (εi-1) ] vj+(vi,vk) εivi = j=1 [ (vj,vk)+ (εi-1) (vi,vk) (vi,vi) (vj,vi) ] vj. Since (vi,vk)=(vk,vi) we have the result.

Corollary 2. Let Γ𝒞. If H(Γ) is non degenerate, the representations ρ and θ are equivalent.

Proof.

Since ρ(ri)=Sit this is immediate from Proposition 4.

Definition: Let Γ𝒞 and let a and b be two distinct vertices in Γ. We say a and b are connected if and only if there is a finite sequence of vertices a=a1,a2,,an=b in Γ such that there is an edge between ai and ai+1, 1in-1. If any two distinct vertices in Γ are connected, Γ is said to be connected.

Definition: A connected graph Γ𝒞 is said to be a linear graph if the vertices of Γ can be numbered so if |i-j|>1 there is no edge joining the ith and jth vertices. Thus a linear graph Γ𝒞 looks like p1 q12 p2 q23 p3 p-1 q-1 p . Coxeter [Cox1967] has introduced the convenient abbreviation p1[q12] p2[q23] p-1[q-1] p for such a graph and we shall make use of it later. For a linear graph Γ𝒞 Coxeter [Cox1967, p.130] gives a representation of W(Γ) by × matrices. Using the identity εk-1 sin(π/pk) =2ieπi/pk one sees that this representation is precisely the representation ρ of Proposition 3.

Consider a graph Γ𝒞 with the stipulation that pi=2 for 1i. Thus all the generators ri for W(Γ) are involutions. These Coxeter groups have been studied extensively [Bou1968]. Note that since pi=2 we have H(Γ)(vi,vi)=1 and thus the form H(Γ) is precisely the form B of [Bou1968, p.90] and the representation θ of W(Γ) is exactly the representation σ of [Bou1968, p.91].

We will be interested in determining when the linear group G=θ(W(Γ)) acts irreducibly on V. It is clear that if the graph Γ is not connected then G will decompose as the direct product of the subgroups θ(W(Γ)) corresponding to the connected components Γ of Γ, since each of these subgroups θ(W(Γ)) operates non trivially only in the subspace V of V generated by those basis vectors corresponding to the vertices of the connected component Γ of Γ.

Proposition 5. Suppose Γ𝒞 is connected. Let V= { xV|H(x,y) =0for allyV } . Then

(1) G acts trivially on V and
(2) If UV is stable under G, then UV.

Proof.

We will write (x,y) to denote the value of H(Γ)(x,y) for x,yV. For (1) take 1i. Now Si(x)=x+ (εi-1) (x,vi) (vi,vi) vi . Thus if xV we have (x,vi)=0 and hence Si(x)=x. Since all generators of G operate trivially on V we are done. We now consider (2). Assume there is some basis vector viU. Let vj be any other basis vector. We shall show vjU also. Since Γ is connected there is a sequence of vertices ai=ai1,,ain=aj such that there is an edge in Γ between aim and aim+1 (1mn-1). By relabeling we can assume this sequence is a1,a2,,an. We now show by induction that vmU for 1mn. If m=1, this is our hypothesis. So assume vkU with 1kn-1. Now qk,k+13 and hence (vk,vk+1)2 = cos2π/qk,k+1- sin2(π2pk-π2pk+1) = 12 [ cos(2πqk,k+1) +cos(πpk-πpk+1) ] 0. Since Sk+1(vk)= vk+ (εk+1-1) (vk,vk+1) (vk+1,vk+1) vk+1, the fact that vk, Sk+1(vk)U implies vk+1U. Thus every basis vector is in U and we have U=V a contradiction. Hence no basis vector is in U. Now let 1i and let xU. Then Si(x)=x+(εi-1)(x,vi)(vi,vi)vi and this vector must be in U also. Hence (x,vi)=0 and xV.

We can now give two conditions sufficient to insure that the linear group G=θ(W(Γ)) associated with a connected graph Γ𝒞 acts irreducibly on V. The first of these is

Corollary 3. Suppose Γ𝒞 is connected. If H(Γ) is non degenerate on V then G acts irreducibly on V.

Proof.

This is immediate from Proposition 5.

The second condition can be stated as

Corollary 4. Let Γ𝒞 be connected. Assume G=θ(W(Γ)) is finite. Then G acts irreducibly on V.

Proof.

Suppose false. Then V=UU a direct sum of two proper non zero subspaces stable under G. Applying Proposition 5 we obtain UV and UV. Hence V=V, a contradiction.

One very interesting and obvious question to ask about the groups W(Γ) under consideration is which of these groups are finite. A necessary condition is given by

Proposition 6. Let Γ𝒞 be connected. If W=W(Γ) is finite, then the Hermitian form H=H(Γ) is positive definite.

Proof.

Certainly the finiteness of W implies that of G=θ(W). Since G is a finite linear group there is a positive definite Hermitian form H stable under the action of G [Bur1955](section 195). But we are assuming that Γ is connected; so we can apply Corollary 4 to yield that G acts irreducibly on V. Now by [Bur1955](section 206), the space of Hermitian forms invariant under a finite irreducible linear group is one dimensional and H is also invariant under G. Thus there is some non zero scalar α such that H=αH. Applying both sides to v1 we obtain 0<H(v1,v1) =αH(v1,v1)= α·sin(π/p1). Hence α is a positive real number. Thus H, being a positive real scalar multiple of the positive definite form H, is also positive definite.

Definition: Let Γ𝒞. Γ is said to be positive definite if and only if the corresponding Hermitian form H (=H(Γ)) is positive definite and we denote by 𝒞+ the collection of all the positive definite graphs Γ𝒞. We also put 𝒞k+=𝒞k𝒞+ and we remark that Γ𝒞+ if and only if all the connected components of Γ are in 𝒞+.

Because of Proposition 6 it is of interest to determine all the graphs Γ𝒞+. To this end we begin with a definition.

Definition: Let Γ𝒞. A graph Γ𝒞 is said to be a subgraph of Γ and we write ΓΓ if Γ can be obtained from Γ by performing any of the following operations in any order subject to the restriction that after each operation is performed the graph thus obtained is still in 𝒞.

1) Removing some of the vertices together with all adjoining edges.
2) Decreasing the marks on some of the edges.
3) Decreasing the marks on the vertices subject to the restriction: if there is an edge in Γ joining the vertices ai and aj then |1pi-1pj| |1pi-1pj| where pi, pj are the marks on ai, aj in Γ and pi, pj are the marks on ai, aj in Γ.

Proposition 7. Suppose Γ𝒞 is positive definite. If Γ𝒞 is a subgraph of Γ, then Γ is also positive definite.

Proof.

We order the vertices a1,,a of Γ in such a way that a1,,ak are the vertices of Γ. We will denote the marks on the vertices and edges of Γ by the usual pi and qij, 1i, j, and those of Γ by pi and qij, 1i, jk. We let (αij) be the matrix for H(Γ) with respect to the basis {v1,,v} and we let (αij) be the matrix for H(Γ) with respect to the basis {v1,,vk}. We claim αijαij.

Since ΓΓ, for all 1i, jk, pipi, qijqij, and if there is an edge joining ai and aj in Γ then |pi-1pj| |1pi-1pj|. Now pipi implies sin(π/pi)sin(π/pi) and thus αiiαii. So assume ij. Now in general, αij0. Hence if there is no edge in Γ joining ai and aj, αij=0 and thus αijαij. So assume there is an edge in Γ joining ai and aj. Then we have |1pi-1pj| |1pi-1pj|, so sin2(π2pi-π2pj) sin2(π2pi-π2pj). Also, qijqij implies cos2(π/qij) cos2(π/qij). Hence - { cos2(π/qij)- sin2(π2pi-π2pj) } 12 - { cos2(π/qij)- sin2(π2pi-π2pj) } 12 , i.e., αijαij.

Now assume the proposition is false. So there is a vector v=x1v1++xkvk, v0, such that H(Γ)(v,v)0. For each 1jk write xj=cj+idj and define yj=|cj|+i|dj|. Put w=y1v1++ ykvk+0·vk+1 ++0·v. Then v0 implies w0. We have 0H(Γ) (v,v) = 1m,nk αmnXm Xn = mαmm XmXm+ 1m<nk αmn (XmXn+XnXm) = mαmm XmXm+ 1m<nk 2αmn (cmcn+dmdn) αmmym ym+ 1m<nk 2αmn ( |cm| |cn| + |dm| |dn| ) αmmym ym+ 1m<nk αmn ( ymyn+ ynym ) = 1m,nk αmnymyn = H(Γ)(w,w) > 0, which is a contradiction.

Definition: Let A=(aij) be an n×n matrix over . Let A(k) for 1kn, denote the matrix formed by the upper left hand k×k corner of A, i.e., A(k)=(aij) 1i,jk. The principal minors of A are the n scalars Det(A(k)) 1kn.

If At=A we say A is positive definite if and only if i,jaijxixj0 for all x1,,xn, and i,jaijxixj=0 if and only if all xi=0.

We will be using the following fact from linear algebra.

Proposition 8. A is positive definite if and only if all the principal minors of A are positive.

Proof.

See [Hal1958].

If Γ𝒞 we write Det(Γ) for Det(H(Γ)) and we denote by 𝒞 the collection of all graphs Γ in 𝒞 such that Det(Γ)=0, but if ΓΓ then Γ𝒞+. We also put 𝒞k=𝒞𝒞k.

Theorem 2. The connected graphs in 𝒞+ are precisely those in List 1. (The subscript on the letter denoting the graph indicates the number of vertices.) List 1 p (p2) q (q3), 3 3 , 3 6 , 3 4 3 , 4 4 , 3 8 , 4 6 , 4 4 3 , 3 5 3 , 5 5 , 3 10 , 5 6 , 5 4 3 . 3 3 3 , 3 3 4 ,H3 5 , F4 4 ,H4 5 , 3 3 3 3 E6 E7 E8 A(2) , , , Bp(,p2) p 4 , p 4 , p 4 , D(4) , , ,

Theorem 3. The connected graphs in 𝒞 are precisely those in List 2. (The subscript on the letter denoting the graph is one less than the number of vertices.) List 2 6 6 , 3 4 6 , 4 4 4 , 6 6 , 3 6 3 , 8 4 , 12 3 4 p 4 (p3), 6 , 4 4 4 , 4 4 4 , 3 3 4 3 3 3 3 3 , 3 3 4 , 3 3 3 4 F4 4 , 3 3 3 3 3 E6 E7 E8 D(4) , , , Bp(3) p 4 , p 4 , p 4 , Bp,p (2) p 4 4 p , p 4 4 p , p 4 4 p , A(2) , , ,

We will prove Theorems 2 and 3 simultaneously.

Lemma 2.

(a) Det(A)= (+1)/2.
(b) Det(Bp)= sinπ/p2-1.
(c) Det(Bp,p) =0.
(d) Det(D)= 12-2.
(e) Det(Bp)= 0.
(f) Det(A) =0.
(g) Det(D) =0.
(h) Det(E) =0=6,7,8.
(g) Det(F4) =0.

Proof.

(a) See [BGr1971, p.58].

(b) If =2 this is a trivial computation. So assume 3. Expanding Det(Bp) along the first row we find Det(Bp) = sinπ/pDet (A-1)- 12sinπ/p Det(A-2) = sinπ/p· 2-1- sinπ/p· -12-1 = sin(π/p) 2-1 .

(c) If =2, this is an easy calculation. So we assume 3. Expanding Det(Bp,p) along the last column we have Det(Bp,p) = sinπ/p Det(Bp)- 12sinπ/p Det(B-1p) = sinπ/p· sinπ/p 2-1 -sinπ/p· sinπ/p 2-1 = 0.

(d) See [BGr1971, p.59].

(e) Again expanding by minors we obtain Det(Bp) = sinπ/p Det(D)-12 sinπ/p Det(D-1) = sinπ/p 2-2 - sinπ/p 2-2 = 0.

For proofs of (f) through (i) see [BGr1971, pp.60-61].

Notice that the kth principal minor of A (respectively Bp, D) is just Det(Ak) (respectively Det(Bkp), Det(Dk)) and thus the combination of Proposition 8 and parts (a), (b), and (d) of Lemma 2 justify the presence of these graphs in List 1. Note further that because of Proposition 7, no graph which has any of Bp,p, Bp, A, D, E (=6,7,8), or F4 as a subgraph can be positive definite and hence is to be excluded from List 1.

We can now begin in earnest to prove Theorems 2 and 3. It is obvious that 𝒞1𝒞+.

Step I. We will determine the connected graphs in 𝒞2+ and the connected graphs in 𝒞2. Suppose Γ𝒞2 is connected. Thus Γ is p1[q]p2 with q3. Now the matrix for H(Γ) in the basis {v1,v2} is ( α11 α12 α21 α22 ) the first principal minor of which is α11=sinπ/p1>0. So by Proposition 8, Γ will be positive definite if and only if Det(Γ)>0. Now Det(Γ) = sinπ/p1 sinπ/p2- cos2(π/q)+ sin2(π2p1-π2p2) = -12 ( cos(2πq)+ cos(πp1+πp2) ) . Thus, Det(Γ)>0 if and only if cos(π-2πq)> cos(πp1+πp2), and Det(Γ)=0 if and only if cos(π-2πq)= cos(πp1+πp2). Since both arguments lie in the interval [0,π] over which cosine is strictly decreasing we have Det(Γ)>0 if and only if (2) 1p1+ 1p2> 1-2/q [Cox1962, p.94] and Det(Γ)=0 if and only if (3) 1p1+ 1p2= 1-2/q [Cox1974, p.110]. The solutions to (2) subject to the restrictions q3, p1,p22, and p1=p2 if q is odd are given in [Cox1962, p.96] and reproduced here: p[4]2, 2[q]2, 3[3]3, 3[6]2, 3[4]3, 4[3]4, 3[8]2, 4[6]2, 4[4]3, 3[5]3, 5[3]5, 3[10]2, 5[6]2, 5[4]3 (p1p2). These are precisely the graphs in List 1 with two vertices. The solutions to (3) subject to the restrictions above occur in [Cox1974, p.111] and we give them here also: 6[3]6, 3[4]6, 4[4]4, 2[6]6, 3[6]3, 2[8]4, 2[12]3 (p1p2). Now by the definition of a subgraph it is easy to verify that if Γ𝒞2 and if ΓΓ, then Det(Γ)>Det(Γ). Thus if Γ occurs amongst those graphs just listed, we have Det(Γ)>0. So every proper subgraph of Γ is positive definite and these graphs comprise the set of connected graphs in 𝒞2 as indicated in List 2.

Step II. We determine all linear graphs in 𝒞3+ and all linear graphs in 𝒞3. Let Γ𝒞3 be linear. Thus Γ is p[q]p[q]p. Putting s=sinπ/p, s=sinπ/p, s=sinπ/p, c=cosπ/p, c=cosπ/p, and c=cosπ/p we find (after using some trigonometric identities) that Det(Γ) = 12 (s+s) - s ( cos2π/q+ 12cc ) - s ( cos2π/q+ 12cc ) . We will determine the linear graphs in 𝒞3+ first. The condition that Det(Γ)>0 is (4) 12(s+s)> s ( cos2π/q+ 12cc ) +s ( cos2π/q+ 12cc ) . Since cos2π/4=12, if (4) is to hold, we cannot have both q4 and q4. So one of them must be 3. Without loss of generality, q=3. Hence, p=p, so Γ is p[3]p[q]p.

Now if q6, cos2(π/q)34. Thus if q6, (4) forces 12(s+s)> s(34+12cc)+ s(14+12c2) or (5) 14s>14s+ 12scc+12 sc2. Comparing the left side with the first term on the right we see p>p, so in particular p>2. But comparing the left side with the last term on the right we see that c2<12 and thus 4>p. So we must have p=3 and p=2. But substituting these values in (5) yields 14>3+18 a contradiction. Hence, q5.

If q=3, then p=p and (4) becomes s>s(12+c2) which holds if and only if p=2 or p=3.

If q=4 (4) becomes (6) 12s>12scc +s(14+12c2). Comparing the left side with the second term on the right we see we must have p=2 or p=3. Substituting p=2 in (6) we obtain 12s>14s and thus p is arbitrary in this case. Substituting p=3 in (6) we obtain 18s>38c or tanπ/p>3 which forces p=2.

If q=5, p=p and (4) becomes 1>cos2π/5+14+c2 which forces p=2.

Thus Det(Γ)>0 forces Γ to be one of: A3, 3[3]3[3]3, B3p, 3[3]3[4]2, 2[3]2[5]2.

Now for such Γ the first principal minor of H(Γ) is obviously positive and the second principal minor is the determinant of the Hermitian form associated with the graph obtained from Γ by deleting its third vertex. One quickly determines by referring to Step I that the graphs so obtained have positive determinants. We have thus enumerated all the linear graphs in 𝒞3+ and we mention that these are precisely those linear graphs with three vertices in List 1.

We now proceed to determine the linear graphs 𝒞3. For a linear graph Γ𝒞3 the expression for Det(Γ) appears at the beginning of Step II and we see that the condition that Det(Γ)=0 is (4') 12(s+s)=s ( cos2(π/q)+ 12cc ) +s ( cos2(π/q)+ 12cc ) . Again, since cos2π/4=12, we see that if q4 and q4 we must have q=q=4 and cc=cc=0. Hence, either p=2 and p and p are arbitrary or p=p=2 and p is arbitrary. Thus if q4 and q4 (4') forces Γ to be either B2p,p or 2[4]p[4]2. Thus we assume without loss of generality that q=3. Hence p=p and Γ is p[3]p[q]p. We rearrange (4') to obtain (5') 14s=s ( cos2π/q -12 ) +12scc+ 12sc2. Recalling that cos2π/6=34 we see that if q7 we must have s>s and thus p>p. In particular, p>2. Further, if q7, the first term on the right is positive, the second is now negative and thus comparing the left side with the last term on the right we must have c2<12, so p<4. Hence, q7 forces p=3 and p=2. Substituting these values in (5') we obtain 18 = 32 (cos2π/q-12) > 32 (cos2π/6-12) = 38a contradiction. Thus we may assume q6. If q-6, (5') becomes 14s=14s+12scc+12sc2. Now since the first term on the right is positive and the second nonnegative, by comparing the left side with the last term on the right we see that c2<12 so p=3 or p=2. If p=2 we must have s=s and thus p=2 also. If p=3, the last term on the right is positive and thus comparing the left side with the first term on the right yields s>s, so p>p and thus p=2. Substituting these values in the equation above we obtain 14=3+18 a contradiction. So if q=6, Γ is 2[3]2[6]2.

If q=5 we have p=p and going back to (5') we once again compare the left side with the last term on the right and (since the first term on the right is positive and the second, non negative) conclude that c2=12 so p=2 or p=3. However, substituting either of these values in (5') yields a contradiction.

If q=4 (5') becomes 14s=12scc+12sc2. In particular, p2. Now comparing the left with the last term on the right we see c212 and c2=12 forces c-0. Thus p=3 or p=4 and p=2. If p=3 we have 18s=38c, or tanπ/p=3 and thus p=3. So if q=4, Γ is either 4[3]4[4]2 or 3[3]3[4]3.

If q=3, p=p and (5') becomes c2=12. Thus, p=4 and Γ is 4[3]4[3]4.

We have now shown that if Γ𝒞3 is linear and satisfies Det(Γ)=0, then Γ is one of B2p,p, 2[4]p[4]2, 2[3]2[6]2, 4[3]4[4]2, 3[3]3[4]3, 4[3]4[3]4. Notice that these graphs are precisely those linear graphs with three vertices occurring in List 2. To complete Step II, we need to show that if Γ is one of the graphs just listed and if ΓΓ, then Γ𝒞+. In light of the first parts of Steps I and II, this task amounts to no more than seeing if the subgraph Γ has its connected components occurring in List 1. We omit the details of this verification.

Step III. We will determine all the linear graphs in 𝒞4+ or in 𝒞4. Suppose Γ𝒞4+𝒞4 is linear. Say Γ is p1[q12]p2[q23]p3[q34]p4. Then either by Proposition 7 (if Γ𝒞4+) or by definition (if Γ𝒞4) the pair of subgraphs p1[q12]p2[q23]p3 and p2[q23]p3[q34]p4 must lie in 𝒞3+. Since we have previously determined the linear graphs in 𝒞3+ we search that list for suitable pSirs and we obtain the following graphs as candidates for membership in 𝒞4+𝒞4.

(i) A4
(ii) B4p
(iii) H4
(iv) F4
(v) 3[3]3[3]3[3]3
(vi) B3p,p
(vii) 3[3]3[4]2[3]2
(viii) 3[3]3[3]3[4]2
(ix) 2[5]2[3]2[4]p
(x) 2[4]3[3]3[4]2
(xi) 2[3]2[5]2[3]2
(xii) 2[5]2[3]2[5]2
Now A4 and B4p are positive definite as remarked after Lemma 2. H4 and F4 are shown to be positive definite in [BGr1971, p.59]. Glancing back at the linear graphs with two or three vertices in List 1 whose presence there has been previously justified we see that the first three principal minors of (v) are positive and we easily compute its determinant to be 116. B3p,p has determinant zero by Lemma 2.

The determinants of both (vii) and (viii) are computed to be zero. In (ix), by reducing the 5 to 4 we obtain B32,p which has determinant zero as a subgraph. We compute that the determinants for both (x) and (xi) are negative. Finally, in (xii) we can reduce both 5's to 4's to obtain B32,2 as a subgraph. Hence the linear graphs in 𝒞4+ are precisely the graphs (i) through (v) and the linear graphs of determinant zero amongst our candidates are the graphs (vi), (vii) & (viii), which we easily see by inspection have the property that all their proper subgraphs are positive definite. We finally remark that graphs (i) through (v) are precisely the linear graphs with four vertices in List 1 and the graphs (vi), (vii) & (viii) are precisely the linear graphs with four vertices in List 2.

Step IV. We will determine all linear graphs in 𝒞5+𝒞5. By the same type of reasoning as that used at the beginning of Step III we see that 𝒞5+𝒞5 must consist of some of the graphs from the following possibilities:

(i) A5
(ii) B5p
(iii) B4p,p
(iv) F4
(v) 3[3]3[3]3[3]3[3]3
(vi) 2[5]2[3]2[3]2[3]2
(vii) 2[5]2[3]2[3]2[4]p
(viii) 2[5]2[3]2[3]2[5]2
As remarked before A5 and B5p are positive definite. B4p,p and F4 have determinant zero by Lemma 2. For (v) we compute its determinant to be zero, and for (vi) we compute its determinant to be negative. In (vii) we can change the 5 to 4 and in (viii) we can change both 5's to 4's to obtain B42,2 as a subgraph. Thus the linear graphs in 𝒞5+ are A5 and B5p. We again remark that it is an easy task to see that all proper subgraphs of B4p,p or of the graph (v) are positive definite and hence the linear graphs in 𝒞5 are just the graphs B4p,p and the graph (v).

Step V. (a) For 5 the linear graphs in 𝒞+ are A and Bp. (b) For 6 the linear graphs in 𝒞 are B-1p,p.

Arguing as we have in the previous steps and using Det(Bnp,p)=0 the proof of (a) is an easy induction. Then using, (a) the proof of (b) is an easy induction.

At this point we have determined all linear graphs in 𝒞+𝒞. We next show that a connected graph in 𝒞+ must be a tree and that the graphs A, (2) are the only connected graphs in 𝒞 which are not trees. This is done in Step VI through Step IX. We remark here that it is obvious that all the proper subgraphs of A are positive definite and since Det(A)=0 by Lemma 2 we have A-1𝒞.

Step VI. Let Γ denote the 3 cycle p p p q q q . If Γ𝒞3+𝒞3 then Γ=A2.

Proof.

Put a={12cos(πp-πp)}12, b={12cos(πp-πp)}12, c={12cos(πp-πp)}12, s=sinπ/p, s=sinπ/p, s=sinπ/p, c=cosπ/p, c=cosπ/p, and c=cosπ/p.

Case (1) None of q, q, q is three. Then Γ0, p p p 4 4 4 , is a subgraph (perhaps not proper) and hence Det(Γ0)0. Now the matrix for the form H(Γ0) is ( s -a -b -a s -c -b -c s ) . Thus, Det(Γ0) = sss-2abc- b2s-c2s- a2s = -12sss- 2abc-12s cc-12sc c-12scc -12scc < 0, giving a contradiction.

Case (2) Exactly one of q, q, q is 3. Without loss of generality q=3. Thus p=p, and Γ0, p p p 4 4 , is a subgraph. So again we must have Det(Γ0)0. But the matrix for H(Γ0) is ( s -12 -b -12 s -b -b -b s ) , and thus Det(Γ0) = s2s-b2-2s b2-14s = -b2-scc-14 s < 0, yielding a contradiction.

Case (3) Two of q, q, q are 3. Without loss of generality say q and q are 3. Thus, p=p=p and if necessary we reduce all of them simultaneously to 2. Further we then reduce q to 3 if necessary to obtain A2 as a subgraph. But this cannot be a proper subgraph as Det(A2)=0. Hence Γ=A2.

Step VII. Let Γ denote the 4 cycle p1 p2 p3 p4 q12 q23 q34 q14 . If Γ𝒞4+𝒞4, then Γ is A3.

Proof.

Note that if all the pi, 1i4, are the same we can reduce them simultaneously to 2 and then reduce the marks on the four edges to 3's to obtain A3 as a subgraph. But since Det(A3)=0 this cannot be a proper subgraph and hence Γ=A3.

Thus we can assume that at least two of the edges of Γ are not labelled with the number 3. Further any two such edges cannot have a vertex in common because a glance at List 1 reveals that no linear graph in 𝒞3+ has both its edges marked with numbers larger than 3. Thus at most two of the edges of Γ can be so marked and hence Γ0, p p p p 4 4 , is a subgraph of Γ. Further, p[4]p[3]p is a subgraph and must occur in List 1. Thus one of p, p is 2. Glancing back at Γ0 we see it does not matter which is 2, so without loss of generality, p=2. Thus writing s=sinπ/p and a=-(s/2)12 the matrix for H(Γ0) is ( s -12 0 a -12 s a 0 0 a 1 -12 a 0 -12 1 ) , and Det(Γ0)=-s4-316<0, giving a contradiction.

Step VIII. Let Γ denote the 5 cycle p1 p2 p3 p4 p5 q12 q23 q34 q23 q15 . If Γ𝒞5+𝒞5 then Γ is A4.

Proof.

Arguing as in Step VII we see that if all the pi, 1i5, are the same we will have Γ=A4. So we assume that not all the edges of Γ are labeled with the number 3. Without loss of generality, say q343. Now the subgraph Γ: p2[q23] p3[q34] p4[q45] p5 must occur in List 1 and thus q343 implies that Γ is F4, forcing pi=2, 2i5. Further we can now conclude that the subgraph Γ: p1[q12] p2[q23] p3[q34] p4 is p1[q12]2[3]2[4]2 and must also occur in List 1. Glancing at that list we see that Γ must be 2[3]2[3]2[4]2. So pi=2, 1i5 and thus Γ=A4 as remarked at the beginning of this step. This is a contradiction as we're assuming q343.

Step IX. Let Γ denote an cycle. If Γ𝒞+𝒞, then Γ is A-1.

Proof.

We may assume 6. Consider any two adjacent vertices ai and ai+1 (1i, if i=, read i+1=1) of Γ. We will show pi=pi+1=2 and qi,i+1=3. By relabelling we may assume i=2. Now the subgraph Γ p1[q12]p2[q23]p3[q34]p4[q45]p5 must occur in List 1 and hence Γ is either A5 or B5p. In either case p2=p3=2 and q23=3. Thus Γ=A-1.

Now Proposition 7 together with Step IX imply that every connected graph in 𝒞+ is a tree and that the graphs A (2) are the only connected graphs in 𝒞 which are not trees. Also we have previously determined all the linear graphs in 𝒞+𝒞. So we must consider non linear trees which leads us to the

Definition: Let Γ𝒞 and suppose a is a vertex of Γ. The degree of a, written Deg(a), is the number of vertices b of Γ such that there is an edge in Γ between a and b. We say that a is a branch point of Γ if Deg(a)3.

Our determination of the connected graphs in 𝒞+𝒞 will be complete if we determine those which contain a branch point.

Step X. Let Γ denote the graph p4 p3 p2 p1 q12 q23 q24 . If Γ𝒞4+, Γ=D4. If Γ𝒞4, Γ=B3p or Γ is 3 3 3 3 .

Proof.

Suppose Γ𝒞4+𝒞4.

Case (1) q12=q23=q34=3.

Thus p4[3]p2[3]p1 and p3[3]p2[3]p1 are subgraphs. Consulting List 1 we see we must have pi=2, 1i4 or pi=3, 1i4. The first alternative is D4 which is positive definite as remarked after Lemma 1. The second alternative has the value zero as the determinant of its Hermitian form, and all its proper subgraphs are positive definite.

Now glancing at List 1 we see that no linear graph in 𝒞3+ has both its edges marked with numbers larger than 3. We are thus led to the remaining

Case (2) Exactly one of the marks on the edges of Γ is not 3. Without loss of generality, q123. Thus Γ is p p p p q . Here again p[3]p[3]p is a subgraph and hence p=2 or p=3.

Subcase (i). Suppose p=2. Then 2[3]2[q]p is a subgraph and thus q=4 with p arbitrary or q=5 and p=2. In the first instance Γ=B3p and all its proper subgraphs are positive definite, while in the second instance we can reduce the 5 to 4 to obtain B32 as a proper subgraph yielding a contradiction.

Subcase (ii). Suppose p=3. Then 3[3]3[q]p is a subgraph and thus q=4 and p=2. Hence Γ is 3 3 3 4 and we compute Det(Γ)<0, giving a contradiction.

Step XI. Suppose Γ𝒞+ is connected and contains a branch point a. Then Γ is one of D, E6, E7, E8.

Proof.

Step X together with the fact that D4 has determinant zero imply that Deg(a)=3 and that the subgraph of Γ formed by a and the three vertices to which a is joined is D4. Further all edges of Γ are unlabelled; otherwise some Bp would occur as a subgraph. So all vertices are unlabelled also. So by the classification of positive definite graphs for Coxeter groups [BGr1971, p. 62] Γ is D, E6, E7, or E8.

Step XII. Let 5 and suppose Γ𝒞 is connected and contains a branch point a. Then Γ is one of D-1, B-1p, E6, E7, E8.

Proof.

If Deg(a)3, Step X forces Γ to contain D4 as a subgraph and hence Γ=D4. So we assume Deg(a)=3. Then again by Step X the subgraph of Γ formed by a and the three vertices to which a is joined is D4. Now if some edge is labelled with a number larger than 3 then Γ would have some Bkp as a subgraph and hence Γ=B-1p. Thus we can assume all edges are unlabelled. Hence all vertices are unlabelled also. Now if Γ contains another branch point distinct from a, then Γ would contain some Dk as a subgraph and hence Γ=D-1. Thus we can assume that a is the unique branch point of Γ. It follows that Γ is E6, E7, or E8 for the only other graphs which have a unique branch point of degree 3 and have all vertices and edges unlabelled are either Dk, E6, E7, E8 (all of which are positive definite) or graphs which contain E6, E7, or E8 as proper subgraphs. We remark that by inspection one easily verifies that each of D-1, B-1p, E6, E7, E8 has the property that all of its proper subgraphs are positive definite and hence these graphs are elements of 𝒞.

This last step completes the proof of Theorems 2 and 3.

Let Γ𝒞 be a connected graph. Recalling Proposition 6 we see that if W(Γ) is finite then Γ must occur in List 1. But referring to [Cox1967, pp. 132,133] we see that every graph in List 1 occurs in the table given there and the groups corresponding to the graphs in this table are, according to [Cox1967], finite. So the combination of [Cox1967] and List 1 yields

Theorem 4: Let Γ𝒞 be connected. Then the following statements are equivalent.

(a) W(Γ) is finite.
(b) Γ is positive definite.
(c) Γ occurs in List 1.

As mentioned before, if Γ𝒞 with pi=2, 1i, then the representation θ given by Theorem 1 for the Coxeter group W(Γ) is the same representation as that given in [Bou1968]. Thus, by [Bou1968, p.93], for such Γ, θ is a faithful representation of W(Γ). Now our representation θ fails to be faithful in general but we can prove the following.

Corollary 5. Let Γ𝒞 be connected. If W=W(Γ) is finite, then θ is a faithful representation of W.

Proof.

By the remarks preceding the corollary we can assume that not all pi, 1i, are 2. Now since W is finite, Γ appears in List 1. But a glance at List 1 reveals the fact that since not all pi are 2, Γ must be linear. As remarked before, for such I, Coxeter [Cox1967] gives a representation of W which is the representation ρ of Proposition 3. But according to [Cox1967] this representation is a faithful representation of W. Now since W is finite the form H(Γ) is positive definite so in particular it is non degenerate and thus Corollary 2 yields that ρ and θ are equivalent representations of W and hence θ is also a faithful representation of W.

The fact that θ is not in general faithful is illustrated in the following example. Let Γ denote the graph 3[6]3 in 𝒞2. The representation θ of W(Γ) is given by θ(r1)=S1= (ω1-ω01) θ(r2)=S2= (101-ωω) where ω=e2πi/3. One easily sees that S1S2 has order 3. However, putting S1= ( ω1-ωx 010 001 ) S2= ( 100 1-ωωy 001 ) where x,y are to be chosen later we see that S13=S23=I and (S1S2)3= (S2S1)3= ( 103ω(y-x) 013ω(x-y) 001 ) . Thus if xy, S1S2 has infinite order and so does r1r2. In fact by looking carefully at the computations done at the very end of the proof of Theorem 1 one sees that for all the groups W(Γ) associated with connected graphs Γ𝒞2 we have r1r2 has infinite order but θ(r1r2)=S1S2 has finite order.

Notes and references

This is a typed version of David W. Koster's thesis Complex Reflection Groups.

This thesis was submitted in partial fulfillment of the requirements for the degree of Doctor of Philosophy (Mathematics) at the University of Wisconsin - Madison, 1975.

page history