Positive Definite Coxeter Graph

Theorem

The following graphs are all the connected graph with positive definite and positive semidefinite.

Positive Definite Coxeter Graph

• $A_n(n\ge 1)$ : $\circ -\circ -\cdots -\circ -\circ -\circ$
• $B_n(n\ge 2)$ : $\circ -\circ -\cdots -\circ \stackrel{4}{-}\circ$
• $D_n(n\ge 4)$ : $\circ -\circ -\cdots -\circ <\begin{array}{c}\circ \\ \circ \end{array}$
• $E_6$ : $\circ -\circ -\stackrel{\stackrel{\circ }{|}}{\circ }-\circ -\circ$
• $E_7$ : $\circ -\circ -\stackrel{\stackrel{\circ }{|}}{\circ }-\circ -\circ -\circ$
• $E_8$ : $\circ -\circ -\stackrel{\stackrel{\circ }{|}}{\circ }-\circ -\circ -\circ -\circ$
• $F_4$ : $\circ -\circ \stackrel{4}{-}\circ -\circ$
• $H_3$ : $\circ \stackrel{5}{-}\circ -\circ$
• $H_4$ : $\circ \stackrel{5}{-}\circ -\circ -\circ$
• $I_2(m)$ : $\circ \stackrel{m}{-}\circ$

The cases $n\le 2$ can be checked directly. For example, the matrix $A$ corresponding to the graph ${\mathrm{I}}_2(m)$ is

$$\left(\begin{array}{cc}1& -\cos (\pi /m)\\ -\cos (\pi /m)& 1\end{array}\right)$$

det(2A) = $4(1-{\cos }^2(\pi /m))=4{\sin }^2(\pi /m)$.

If $n\ge 3$, the graph above shows that it is possible to number vertices in such a way that the last vertex (numbered $n$) is joined by an edge to only one other vertex (numbered $n-1$), this edge being labelled $m=3$ or $4$. Let $d_i$ be the determinant of the upper left $i\times i$ submatrix of $2A$. Then an expansion of $\det 2A$ along the last row shows that

$\det 2A=2d_{n-1}-c{d}_{n-2},$

where $c=1$ (resp. $2$) if $m=3$ (resp. $4$). Keeping in mind that we multiply each matrix by $2$, we compute inductively the values in the following table.

$$\begin{array}{cccccccccc}{A}_n& B_n& D_n& E_6& E_7& E_8& F_4& H_3& H_4& {\mathrm{I}}_2(m)\\ n+1& 2& 4& 3& 2& 1& 1& 3-\sqrt{5}& (7-3\sqrt{5})/2& 4{\sin }^2(\pi /m)\end{array}$$ Table 1: Determinant of $2A$

The reader should carry out the required verification as an exercise, recalling the values:

$\cos \frac{\pi }{3}=\frac{1}{2},\cos \frac{\pi }{4}=\frac{\sqrt{2}}{2},\cos \frac{\pi }{5}=\frac{1+\sqrt{5}}{4},\cos \frac{\pi }{6}=\frac{\sqrt{3}}{2}.$

(If the value of $\cos \pi /5$ is not so familiar, look at the derivation in Bourbaki [1], p. 192 (footnote).)

As an example, we work through the cases of $H_3$ and $H_4$. For $H_3$ the smaller minors come from graphs of types ${\mathrm{I}}_2(5)$ and $A_1$, so formula (1) reads:

$\det 2A=8{\sin }^2(\pi /5)-2=3-\sqrt{5}.$

For $H_4$ the smaller minors are of types $H_3$ and ${\mathrm{I}}_2(5)$, yielding:

$\det 2A=2(3-\sqrt{5})-4{\sin }^2(\pi /5)=(7-3\sqrt{5})/2.$

Positive Semidefinite Coxeter Graphs

• ${\tilde{A}}_1$ : $\circ \stackrel{\infty }{=}\circ$
• ${\tilde{A}}_n(n\ge 2)$ : $\begin{array}{ccc}& \circ & \\ ╱& & ╲\\ \circ -\circ & \cdots & \circ -\circ \end{array}$
• ${\tilde{B}}_2={\tilde{C}}_2$ : $\circ \stackrel{4}{-}\circ \stackrel{4}{-}\circ$
• ${\tilde{B}}_n(n\ge 3)$ : $\begin{array}{ccc}\circ & & \\ & \searrow & \\ & & \circ -\circ -\cdots -\circ \stackrel{4}{-}\circ \\ & \nearrow & \\ \circ & & \end{array}$
• ${\tilde{C}}_n(n\ge 3)$ : $\circ \stackrel{4}{-}\circ -\circ -\cdots -\circ \stackrel{4}{-}\circ$
• ${\tilde{D}}_n(n\ge 4)$ : $\begin{array}{cccccc}\circ & & & & & \circ \\ & \searrow & & & \nearrow & \\ & & \circ -\cdots -\circ & & & \\ & \nearrow & & & \searrow & \\ \circ & & & & & \circ \end{array}$
• ${\tilde{E}}_6$ : $\circ -\circ -\stackrel{\stackrel{\circ }{|}}{\stackrel{\circ }{|}}\circ -\circ -\circ$
• ${\tilde{E}}_7$ : $\circ -\circ -\circ -\stackrel{\stackrel{\circ }{|}}{\circ }-\circ -\circ -\circ$
• ${\tilde{E}}_8$ : $\circ -\circ -\stackrel{\stackrel{\circ }{|}}{\circ }-\circ -\circ -\circ -\circ -\circ$
• ${\tilde{F}}_4$ : $\circ -\circ -\circ \stackrel{4}{-}\circ -\circ$
• ${\tilde{G}}_2$ : $\circ \stackrel{6}{-}\circ -\circ$