Classification of finite Coxeter systems, including the H and dihedral families

(The special cosine values and the determinant recurrences.) First the cosine values used below. For $c:=\cos (\pi \mathrm{/}3)$ the double-angle and shift identities of [F7] give $2c^2-1=\cos (2\pi \mathrm{/}3)=-\cos (\pi \mathrm{/}3)=-c$, so $(2c-1)(c+1)=0$, and $c>-1$ because $0<\pi \mathrm{/}3<\pi$, cosine is strictly decreasing on $[0,\pi ]$ and $\cos \pi =-1$ [F7], hence $c=1\mathrm{/}2$; also $\cos (\pi \mathrm{/}4)=\sqrt{2}\mathrm{/}2$ by [F7]. For $c_5:=\cos (\pi \mathrm{/}5)$, iterating the recurrence of [F7] gives $T_5(t)=16t^5-20t^3+5t$, so $T_5(c_5)=\cos \pi =-1$, i.e. $16c_5^5-20c_5^3+5c_5+1=(c_5+1)(4c_5^2-2c_5-1{)}^2=0$ by expansion; since $0<\pi \mathrm{/}5<\pi \mathrm{/}2$ gives $0<c_5<1$ [F7], one has $c_5\mathrm{\ne }-1$, hence $4c_5^2-2c_5-1=0$ and $(c_5-\frac{1}{4}{)}^2=\frac{5}{16}$; by uniqueness of nonnegative square roots $c_5=\frac{1}{4}\pm \frac{\sqrt{5}}{4}$, and $c_5>0$ excludes $\frac{1-\sqrt{5}}{4}<0$ (as $2<\sqrt{5}$ [F7]), so $c_5=(1+\sqrt{5})\mathrm{/}4$. Now for a path on $k$ vertices with labels $m_1,\dots ,m_{k-1}$ put $D_k:=\det (2C_k)$, where $C_k$ is the leading $k\times k$ principal submatrix of $C$; since multiplying a $k\times k$ matrix by $2$ multiplies its determinant by $2^k$ [F6] and $d_k=d_{k-1}-{\cos }^2(\pi \mathrm{/}{m}_{k-1})d_{k-2}$ with $2^k{d}_k=D_k$ [F2], expanding along the last row gives $D_0=1$, $D_1=2$, $D_2=4{\sin }^2(\pi \mathrm{/}{m}_1)$ and $D_k=2D_{k-1}-4{\cos }^2(\pi \mathrm{/}{m}_{k-1})D_{k-2}(k\ge 2)\mathrm{.}$ In particular $D_2(A_2)=4-4{\cos }^2(\pi \mathrm{/}3)=4-1=3$, $D_2(I_2(m))=4{\sin }^2(\pi \mathrm{/}m)$, and for a disjoint union the matrix is block diagonal, so $D_2(A_1\bigsqcup A_1)=2\cdot 2=4$ and $D_3(A_3)=2D_2(A_2)-D_1(A_1)=6-2=4$ [F6, F7].

(Induction hypothesis, recorded for use in the proof of (3).) Assume $n\ge 3$ and assume that for every disjoint union $\mathrm{\Delta }$ of listed diagrams with total rank $<n$ both statements hold: every principal minor of $C(\mathrm{\Delta })$ is positive, and $B_{\mathrm{\Delta }}$ is positive definite.

(The irreducible case: both directions of (1).) Let $\mathrm{\Gamma }$ be connected. If $W$ is finite then $B$ is positive definite by [F1], so clause (7) of the exclusion lemma in [F2] gives that $\mathrm{\Gamma }$ is isomorphic as a labelled graph to one of $A_n$ ($n\ge 1$), $B_n$ ($n\ge 2$), $D_n$ ($n\ge 4$), $E_6,E_7,E_8$, $F_4$, $H_3$, $H_4$, $I_2(m)$ ($m\ge 3$) with the labels displayed in (1). Conversely, if $\mathrm{\Gamma }$ is one of those labelled graphs then $B$ is positive definite by the positivity clause (3), proved below, and then $W$ is finite by [F1]. Hence $W$ is finite if and only if $\mathrm{\Gamma }$ is one of those labelled graphs, which is (1).

(Coincidences and the duplicate-free list (4).) Reading the labelled graphs of (1) [F3]: $I_2(3)$ is one edge labelled $3$, which is $A_2$; $I_2(4)$ is one edge labelled $4$, which is $B_2$, also called $C_2$ in the root-system naming, and for $n\ge 3$ the paths with labels $3,\dots ,3,4$ are the $B_n$; $I_2(6)$ is one edge labelled $6$, conventionally called $G_2$; $A_1$ is the one-vertex diagram, written $B_1$ in the root-system naming; $A_3$ and $D_3$ are both the path on three vertices, since the third arm of $D_3$ has length $n-3=0$; $H_2$ is $I_2(5)$ by the rank-two naming convention; and $I_2(2)$ denotes the two-vertex diagram with no edge, which by Disconnected diagrams, direct products, and comparison of invariant forms (1) is the direct product $A_1\times A_1$ of two one-vertex systems [F8]. For the non-isomorphism claim, the type is recovered from invariants of the labelled graph: the number of vertices, the degree sequence, the multiset of edge labels, the position of the unique label $\ge 4$ or of the unique vertex of degree $3$, and, for a diagram with a vertex of degree $3$, the multiset of the lengths of the three arms (the numbers of vertices in the components obtained by deleting that vertex); these separate every pair of the list with exactly the exceptions displayed above, and distinct $m$ give non-isomorphic $I_2(m)$ because the label is read off the single edge. Removing the duplicates gives the displayed duplicate-free list, with $I_2(3),I_2(4),I_2(6)$ named alternatively as $A_2,B_2,G_2$.

(The determinant table for the listed diagrams.) Using the recurrence of 1.1 [step 1.1] with the last edge label and deleting the last one or two vertices: $A_n$ has all labels $3$, so $D_n=2D_{n-1}-D_{n-2}$ with $D_1=2$, $D_2=3$, giving $D_n=n+1$ by induction on $n$ [F10]; $B_n$ (labels $3,\dots ,3,4$, the $4$ at the end) has $D_n=2D_{n-1}-2D_{n-2}$ with $D_{n-1}=n$ (the all-$3$ path $A_{n-1}$) and $D_{n-2}=n-1$, giving $D_n=2$; $B_3$ has $D_3=2D_2(A_2)-2D_1(A_1)=6-4=2$ and $F_4$ (labels $3,4,3$) has $D_4=2D_3(B_3)-D_2(A_2)=4-3=1$; $H_3$ (labels $3,5$) has $D_3=2D_2(A_2)-4{\cos }^2(\pi \mathrm{/}5)D_1=6-8{\cos }^2(\pi \mathrm{/}5)=3-\sqrt{5}$ and $H_4$ (labels $3,3,5$) has $D_4=2D_3(A_3)-4{\cos }^2(\pi \mathrm{/}5)D_2(A_2)=8-\frac{9+3\sqrt{5}}{2}=\frac{7-3\sqrt{5}}{2}$; $I_2(m)$ has $D_2=4{\sin }^2(\pi \mathrm{/}m)$. For any leaf $a$ with sole neighbour $b$ and off-diagonal entry $-t$ in $M=2C$, order $a$ last and $b$ next to last. Expansion along the last row gives $\det M=2\det M_{\widehat{a}}-t^2\det M_{\widehat{a},\widehat{b}}$: the off-diagonal cofactor has its last column zero except for $-t$, whose expansion gives the second term with its negative sign [F6]. For label $3$, $t=1$. For $D_4$, deletion of $a$ gives $A_3$, and deletion of $a,b$ gives $A_1\bigsqcup A_1$; for $D_n$ with $n\ge 5$, use the end of the long arm, giving $D_{n-1}$ and $D_{n-2}$ (with $D_3=A_3$). Thus $D_n(D)=2D_{n-1}-D_{n-2}$ with $D_3(A_3)=4$, $D_2(A_1\bigsqcup A_1)=4$, whence $D_n(D)=4$ for $n\ge 4$; and deleting the end vertex of the long arm of $E_6,E_7,E_8$ respectively one and two vertices of it gives $D(E_6)=2D_5(D)-D_4(A)=8-5=3$, $D(E_7)=2D(E_6)-D_5(D)=6-4=2$, $D(E_8)=2D(E_7)-D(E_6)=4-3=1$. This is the table of (3).

(The reducible case (2).) Let the connected components of $\mathrm{\Gamma }$ be on $S_1,\dots ,S_k$. By Disconnected diagrams, direct products, and comparison of invariant forms (1) the multiplication map $W_{S_1}\times \cdots \times W_{S_k}\to W$ is an isomorphism, and by its (2) the form is the orthogonal direct sum $B=B_{S_1}\oplus \cdots \oplus B_{S_k}$ [F9]. A direct product of groups is finite exactly when each factor is finite [F8], and a direct sum of forms is positive definite exactly when each summand is [F9]; by 1.3 [step 1.3] applied to each component this happens exactly when every ${\mathrm{\Gamma }}_{S_i}$ is one of the diagrams of (1). This is (2).

(Base of the induction: rank $\le 2$.) The empty diagram has rank $0$ and no principal minors, and its form is positive definite vacuously; $A_1$ has $D_1=2>0$, and $I_2(m)$ ($m\ge 3$) has $D_2=4{\sin }^2(\pi \mathrm{/}m)>0$ together with the $1\times 1$ minors $2>0$, by 1.1 [step 1.1] and $\sin (\pi \mathrm{/}m)>0$ for $0<\pi \mathrm{/}m<\pi$ [F7]; by Sylvester's criterion [F5] the forms of $A_1$, $A_2=I_2(3)$, $B_2=I_2(4)$ and all $I_2(m)$ are positive definite. The remaining disjoint union of rank $2$ is $A_1\bigsqcup A_1$, with $2C=\mathrm{diag}(2,2)$, positive principal minors $2,2,4$ and positive definite form. This completes the base of the induction. [base],

(Inductive step: every listed diagram is positive definite; clause (3).) Let $\mathrm{\Delta }$ be a disjoint union of listed diagrams of total rank $n\ge 3$, and assume the induction hypothesis of 1.2 [step 1.2]. If $\mathrm{\Delta }$ is disconnected, its matrix is block diagonal with blocks the matrices of its components, and every principal submatrix of a block diagonal matrix is block diagonal with blocks the corresponding principal submatrices of the components, so multiplicativity of determinants [F6] and the induction hypothesis give positivity of every principal minor and positive definiteness of $B_{\mathrm{\Delta }}$ [F9]. If $\mathrm{\Delta }$ is connected, it is one of the listed diagrams: deleting vertices from an all-$3$ path leaves $A$ paths; a subpath retaining the label-$4$ endpoint edge of $B_n$ is a smaller $B$ path; proper subpaths of $F_4$ are $A$ paths, $B_2$ or $B_3$; and proper subpaths of $H_3,H_4$ are $A$ paths, $I_2(5)$ or $H_3$. Deleting a vertex of $I_2(m)$ leaves $A_1$. Deleting vertices from a star with arm lengths $(a,b,c)$ leaves stars with arm lengths $a^{\mathrm{\prime }}\le a$, $b^{\mathrm{\prime }}\le b$, $c^{\mathrm{\prime }}\le c$ (or paths, when an arm disappears); the triples $(1,1,n-3)$ of $D_n$ and $(1,2,2),(1,2,3),(1,2,4)$ of $E_6,E_7,E_8$ dominate componentwise every smaller triple, and the result is again a $D$ or $E$ diagram of smaller rank, or a path $A$ [F3]. Hence every proper principal submatrix of a listed diagram is block diagonal with blocks listed diagrams of smaller rank, and every principal minor is positive by the induction hypothesis; the full determinant is the positive table value of 2.1 [step 2.1]; since the leading principal minors are principal minors, Sylvester's criterion [F5] gives positive definiteness of the form of every listed diagram, which is (3).

(Discharge of the induction; assembly.) The base case is 2.3 [step 2.3] and the inductive step is 3.1 [step 3.1], so by the induction principle on the rank, every disjoint union of listed diagrams, and in particular every diagram of the list (1), has positive definite form [discharge-induction: step 3.1]. Clause (1) is 1.3 [step 1.3], clause (2) is 2.2 [step 2.2], clause (3) is 2.1 and 3.1 [step 2.1, step 3.1], and clause (4) is 1.4 [step 1.4]; hence the connected finite diagrams are exactly the standard list, the finite Coxeter systems are exactly the direct products of the irreducible types, every listed diagram is positive definite and therefore finite, and the list is duplicate-free after the stated identifications.