Last update: 10 January 2014

**Proposition 2.** Let $\Gamma \in {\mathcal{C}}_{\ell}\text{.}$
Then $W\left(\Gamma \right)$ admits an antiautomorphism, denoted
$w\to w\prime ,$ which fixes the generators
${r}_{1},\dots ,{r}_{\ell}\text{.}$

Proof. | |

$W=F/N$ where $F$ is a free group on generators ${y}_{1},\dots ,{y}_{\ell}$ and $N$ is generated, as a normal subgroup, by the elements $$\begin{array}{cccc}{u}_{ij}& =& \underset{\underset{{q}_{ij}\hspace{0.17em}\text{factors}}{\u23df}}{{y}_{i}{y}_{j}\cdots {y}_{i}}\underset{\underset{{q}_{ij}\hspace{0.17em}\text{factors}}{\u23df}}{{y}_{j}^{-1}{y}_{i}^{-1}\cdots {y}_{j}^{-1}}& \phantom{\rule{2em}{0ex}}{q}_{ij}\hspace{0.17em}\text{odd}\\ {u}_{ij}& =& \underset{\underset{{q}_{ij}\hspace{0.17em}\text{factors}}{\u23df}}{{y}_{i}{y}_{j}\cdots {y}_{i}{y}_{j}}\underset{\underset{{q}_{ij}\hspace{0.17em}\text{factors}}{\u23df}}{{y}_{i}^{-1}{y}_{j}^{-1}\cdots {y}_{i}^{-1}{y}_{j}^{-1}}& \phantom{\rule{2em}{0ex}}{q}_{ij}\hspace{0.17em}\text{odd}\end{array}$$ together with the $\ell $ elements ${y}_{i}^{{p}_{i}}\text{.}$ Now $F$ has an antiautomorphism fixing the generators ${y}_{1},\dots {y}_{\ell}\text{.}$ We denote this by $x\to x\prime $ for $x\in F\text{.}$ Put $u={u}_{ij}\text{.}$ If ${q}_{ij}$ is odd, $\underset{\underset{{q}_{ij}}{\u23df}}{{y}_{j}{y}_{i}\cdots {y}_{j}}u\prime =\underset{\underset{{q}_{ij}}{\u23df}}{{y}_{i}{y}_{j}\cdots {y}_{i}}=u\underset{\underset{{q}_{ij}}{\u23df}}{{y}_{j}{y}_{i}\cdots {y}_{j}}\text{.}$ If ${q}_{ij}$ is even, $\underset{\underset{{q}_{ij}}{\u23df}}{{y}_{i}{y}_{j}\cdots {y}_{i}{y}_{j}}u\prime =\underset{\underset{{q}_{ij}}{\u23df}}{{y}_{j}{y}_{i}\cdots {y}_{j}{y}_{i}}={u}^{-1}\underset{\underset{{q}_{ij}}{\u23df}}{{y}_{i}{y}_{j}\cdots {y}_{i}{y}_{j}}\text{.}$ If the first case $u\prime $ is conjugate to $u$ and in the second $u\prime $ is conjugate to ${u}^{-1}\text{.}$ Thus $u\prime \in N\text{.}$ It follows that $N=N\prime $ and hence $W\left(\Gamma \right)$ has an antiautomorphism fixing ${r}_{1},\dots ,{r}_{\ell}\text{.}$ $\square $ |

**Proposition 3.** Let $\Gamma \in {\mathcal{C}}_{\ell}$ and let
$V$ be an $\ell $ dimensional complex vector space. Define $\rho :W\left(\Gamma \right)\to GL\left(V\right)$
by $\rho \left(w\right)={\theta \left(w\prime \right)}^{t}$
for $w\in W\left(\Gamma \right)\text{.}$ Then
$\rho $ is a representation of $W\left(\Gamma \right)\text{.}$

Proof. | |

Obvious. $\square $ |

Keeping in mind that $\rho \left({r}_{i}\right)={S}_{i}^{t},$ the connection between the representations $\theta $ and $\rho $ of $W\left(\Gamma \right)$ is further clarified by

**Proposition 4.** Let $\Gamma \in {\mathcal{C}}_{\ell}$ and let
$A$ denote the matrix for the Hermitian form $H\left(\Gamma \right)$
with respect to the basis $\{{v}_{1},\dots ,{v}_{\ell}\}\text{.}$
By abuse of notation, for $1\le i\le \ell ,$ we let ${S}_{i}$
denote the matrix for the linear transformation ${S}_{i}=\theta \left({r}_{i}\right)$
in the basis $\{{v}_{1},\dots ,{v}_{\ell}\}\text{.}$
Then $A{S}_{i}={S}_{i}^{t}A\text{.}$

Proof. | |

We view all matrices as elements of $\text{End}\left(V\right)$ which have been written with respect to the basis $\{{v}_{1},\dots ,{v}_{\ell}\}$ of column vectors for $V$ and we write $(x,y)$ for $H\left(\Gamma \right)(x,y)$ if $x,y\in V\text{.}$ Then letting $1\le k\le \ell $ we compute $$\begin{array}{ccc}A{S}_{i}\left({v}_{k}\right)& =& A({v}_{k}+({\epsilon}_{i}-1)\frac{({v}_{k},{v}_{i})}{({v}_{i},{v}_{i})}{v}_{i})\\ & =& \sum _{j=1}^{\ell}({v}_{j},{v}_{k}){v}_{j}+({\epsilon}_{i}-1)\frac{({v}_{k},{v}_{i})}{({v}_{i},{v}_{i})}\sum _{j=1}^{\ell}({v}_{j},{v}_{i}){v}_{i}\\ & =& \sum _{j=1}^{\ell}[({v}_{j},{v}_{k})+({\epsilon}_{i}-1)\frac{({v}_{k},{v}_{i})}{({v}_{i},{v}_{i})}({v}_{j},{v}_{i})]{v}_{j}\end{array}$$ and $$\begin{array}{ccc}{S}_{i}^{t}A\left({v}_{k}\right)& =& {S}_{i}^{t}\left(\sum _{j=1}^{\ell}({v}_{j},{v}_{k}){v}_{j}\right)\\ & =& \sum _{j=1}^{\ell}({v}_{j},{v}_{k}){S}_{i}^{t}\left({v}_{j}\right)\\ & =& \sum _{\underset{j\ne i}{j=1}}^{\ell}({v}_{j},{v}_{k}){v}_{j}+({v}_{i},{v}_{k})\sum _{\underset{j\ne i}{j=1}}^{\ell}\frac{({v}_{j},{v}_{i})}{({v}_{i},{v}_{i})}({\epsilon}_{i}-1){v}_{j}+({v}_{i},{v}_{k}){\epsilon}_{i}{v}_{i}\\ & =& \sum _{\underset{j\ne i}{j=1}}^{\ell}[({v}_{j},{v}_{k})+({v}_{i},{v}_{k})\frac{({v}_{j},{v}_{i})}{({v}_{i},{v}_{i})}({\epsilon}_{i}-1)]{v}_{j}+({v}_{i},{v}_{k}){\epsilon}_{i}{v}_{i}\\ & =& \sum _{j=1}^{\ell}[({v}_{j},{v}_{k})+({\epsilon}_{i}-1)\frac{({v}_{i},{v}_{k})}{({v}_{i},{v}_{i})}({v}_{j},{v}_{i})]{v}_{j}\text{.}\end{array}$$ Since $({v}_{i},{v}_{k})=({v}_{k},{v}_{i})$ we have the result. $\square $ |

**Corollary 2.** Let $\Gamma \in \mathcal{C}\text{.}$ If
$H\left(\Gamma \right)$ is non degenerate, the representations
$\rho $ and $\theta $ are equivalent.

Proof. | |

Since $\rho \left({r}_{i}\right)={S}_{i}^{t}$ this is immediate from Proposition 4. $\square $ |

Definition: Let $\Gamma \in \mathcal{C}$ and let $a$ and $b$ be two distinct vertices in $\Gamma \text{.}$ We say $a$ and $b$ are connected if and only if there is a finite sequence of vertices $a={a}_{1},{a}_{2},\dots ,{a}_{n}=b$ in $\Gamma $ such that there is an edge between ${a}_{i}$ and ${a}_{i+1},$ $1\le i\le n-1\text{.}$ If any two distinct vertices in $\Gamma $ are connected, $\Gamma $ is said to be connected.

Definition: A connected graph $\Gamma \in \mathcal{C}$ is said to be a linear graph if the vertices of $\Gamma $ can be numbered so if $|i-j|>1$ there is no edge joining the ${i}^{\text{th}}$ and ${j}^{\text{th}}$ vertices. Thus a linear graph $\Gamma \in \mathcal{C}$ looks like $$\begin{array}{c}\n\n\n\n\n\n\n\n\n\n\n\n\n\np1\nq12\np2\nq23\np3\n\n\cdots \n\np\u2113-1\nq\u2113-1\u2113\np\u2113\n\n\end{array}\text{.}$$ Coxeter [Cox1967] has introduced the convenient abbreviation $${p}_{1}\left[{q}_{12}\right]{p}_{2}\left[{q}_{23}\right]\cdots {p}_{\ell -1}\left[{q}_{\ell -1\ell}\right]{p}_{\ell}$$ for such a graph and we shall make use of it later. For a linear graph $\Gamma \in {\mathcal{C}}_{\ell}$ Coxeter [Cox1967, p.130] gives a representation of $W\left(\Gamma \right)$ by $\ell \times \ell $ matrices. Using the identity $$\frac{{\epsilon}_{k}-1}{\text{sin}(\pi /{p}_{k})}=2i{e}^{\pi i/{p}_{k}}$$ one sees that this representation is precisely the representation $\rho $ of Proposition 3.

Consider a graph $\Gamma \in {\mathcal{C}}_{\ell}$ with the stipulation that ${p}_{i}=2$ for $1\le i\le \ell \text{.}$ Thus all the generators ${r}_{i}$ for $W\left(\Gamma \right)$ are involutions. These Coxeter groups have been studied extensively [Bou1968]. Note that since ${p}_{i}=2$ we have $H\left(\Gamma \right)({v}_{i},{v}_{i})=1$ and thus the form $H\left(\Gamma \right)$ is precisely the form $B$ of [Bou1968, p.90] and the representation $\theta $ of $W\left(\Gamma \right)$ is exactly the representation $\sigma $ of [Bou1968, p.91].

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

**Proposition 5.** Suppose $\Gamma \in {\mathcal{C}}_{\ell}$ is connected. Let
$${V}^{\perp}=\{x\in V\hspace{0.17em}|\hspace{0.17em}H(x,y)=0\hspace{0.17em}\text{for all}\hspace{0.17em}y\in V\}\text{.}$$
Then

(1) | $G$ acts trivially on ${V}^{\perp}$ and |

(2) | If $U\u2acbV$ is stable under $G,$ then $U\subset {V}^{\perp}\text{.}$ |

Proof. | |

We will write $(x,y)$ to denote the value of $H\left(\Gamma \right)(x,y)$ for $x,y\in V\text{.}$ For (1) take $1\le i\le \ell \text{.}$ Now ${S}_{i}\left(x\right)=x+({\epsilon}_{i}-1)\frac{(x,{v}_{i})}{({v}_{i},{v}_{i})}{v}_{i}\text{.}$ Thus if $x\in {V}^{\perp}$ we have $(x,{v}_{i})=0$ and hence ${S}_{i}\left(x\right)=x\text{.}$ Since all generators of $G$ operate trivially on ${V}^{\perp}$ we are done. We now consider (2). Assume there is some basis vector ${v}_{i}\in U\text{.}$ Let ${v}_{j}$ be any other basis vector. We shall show ${v}_{j}\in U$ also. Since $\Gamma $ is connected there is a sequence of vertices ${a}_{i}={a}_{{i}_{1}},\dots ,{a}_{{i}_{n}}={a}_{j}$ such that there is an edge in $\Gamma $ between ${a}_{{i}_{m}}$ and ${a}_{{i}_{m+1}}$ $(1\le m\le n-1)\text{.}$ By relabeling we can assume this sequence is ${a}_{1},{a}_{2},\dots ,{a}_{n}\text{.}$ We now show by induction that ${v}_{m}\in U$ for $1\le m\le n\text{.}$ If $m=1,$ this is our hypothesis. So assume ${v}_{k}\in U$ with $1\le k\le n-1\text{.}$ Now ${q}_{k,k+1}\ge 3$ and hence $$\begin{array}{ccc}{({v}_{k},{v}_{k+1})}^{2}& =& {\text{cos}}^{2}\pi /{q}_{k,k+1}-{\text{sin}}^{2}(\frac{\pi}{2{p}_{k}}-\frac{\pi}{2{p}_{k+1}})\\ & =& \frac{1}{2}[\text{cos}\left(\frac{2\pi}{{q}_{k,k+1}}\right)+\text{cos}(\frac{\pi}{{p}_{k}}-\frac{\pi}{{p}_{k+1}})]\\ & \ne & 0\text{.}\end{array}$$ Since ${S}_{k+1}\left({v}_{k}\right)={v}_{k}+({\epsilon}_{k+1}-1)\frac{({v}_{k},{v}_{k+1})}{({v}_{k+1},{v}_{k+1})}{v}_{k+1},$ the fact that ${v}_{k},$ ${S}_{k+1}\left({v}_{k}\right)\in U$ implies ${v}_{k+1}\in U\text{.}$ Thus every basis vector is in $U$ and we have $U=V$ a contradiction. Hence no basis vector is in $U\text{.}$ Now let $1\le i\le \ell $ and let $x\in U\text{.}$ Then ${S}_{i}\left(x\right)=x+({\epsilon}_{i}-1)\frac{(x,{v}_{i})}{({v}_{i},{v}_{i})}{v}_{i}$ and this vector must be in $U$ also. Hence $(x,{v}_{i})=0$ and $x\in {V}^{\perp}\text{.}$ $\square $ |

We can now give two conditions sufficient to insure that the linear group $G=\theta \left(W\left(\Gamma \right)\right)$ associated with a connected graph $\Gamma \in \mathcal{C}$ acts irreducibly on $V\text{.}$ The first of these is

**Corollary 3.** Suppose $\Gamma \in \mathcal{C}$ is connected. If
$H\left(\Gamma \right)$ is non degenerate on $V$ then
$G$ acts irreducibly on $V\text{.}$

Proof. | |

This is immediate from Proposition 5. $\square $ |

The second condition can be stated as

**Corollary 4.** Let $\Gamma \in \mathcal{C}$ be connected. Assume
$G=\theta \left(W\left(\Gamma \right)\right)$
is finite. Then $G$ acts irreducibly on $V\text{.}$

Proof. | |

Suppose false. Then $V=U\oplus U\prime $ a direct sum of two proper non zero subspaces stable under $G\text{.}$ Applying Proposition 5 we obtain $U\subset {V}^{\perp}$ and $U\prime \subset {V}^{\perp}\text{.}$ Hence $V={V}^{\perp},$ a contradiction. $\square $ |

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

**Proposition 6.** Let $\Gamma \in \mathcal{C}$ be connected. If
$W=W\left(\Gamma \right)$ is finite, then the Hermitian
form $H=H\left(\Gamma \right)$ is positive definite.

Proof. | |

Certainly the finiteness of $W$ implies that of $G=\theta \left(W\right)\text{.}$ Since $G$ is a finite linear group there is a positive definite Hermitian form ${H}_{\circ}$ stable under the action of $G$ [Bur1955](section 195). But we are assuming that $\Gamma $ is connected; so we can apply Corollary 4 to yield that $G$ acts irreducibly on $V\text{.}$ 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\text{.}$ Thus there is some non zero scalar $\alpha \in \u2102$ such that ${H}_{\circ}=\alpha H\text{.}$ Applying both sides to ${v}_{1}$ we obtain $$0<{H}_{\circ}({v}_{1},{v}_{1})=\alpha H({v}_{1},{v}_{1})=\alpha \xb7\text{sin}(\pi /{p}_{1})\text{.}$$ Hence $\alpha $ is a positive real number. Thus $H,$ being a positive real scalar multiple of the positive definite form ${H}_{\circ},$ is also positive definite. $\square $ |

Definition: Let $\Gamma \in \mathcal{C}\text{.}$ $\Gamma $ is said to be positive definite if and only if the corresponding Hermitian form $H$ $(=H\left(\Gamma \right))$ is positive definite and we denote by ${\mathcal{C}}^{+}$ the collection of all the positive definite graphs $\Gamma \in \mathcal{C}\text{.}$ We also put ${\mathcal{C}}_{k}^{+}={\mathcal{C}}_{k}\cap {\mathcal{C}}^{+}$ and we remark that $\Gamma \in {\mathcal{C}}^{+}$ if and only if all the connected components of $\Gamma $ are in ${\mathcal{C}}^{+}\text{.}$

Because of Proposition 6 it is of interest to determine all the graphs $\Gamma \in {\mathcal{C}}^{+}\text{.}$ To this end we begin with a definition.

Definition: Let $\Gamma \in \mathcal{C}\text{.}$ A graph $\Gamma \prime \in \mathcal{C}$ is said to be a subgraph of $\Gamma $ and we write $\Gamma \prime \subset \Gamma $ if $\Gamma \prime $ can be obtained from $\Gamma $ 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 $\mathcal{C}\text{.}$

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 $\Gamma \prime $ joining the vertices ${a}_{i}$ and ${a}_{j}$ then $|\frac{1}{{p}_{i}}-\frac{1}{{p}_{j}}|\le |\frac{1}{{p}_{i}^{\prime}}-\frac{1}{{p}_{j}^{\prime}}|$ where ${p}_{i},$ ${p}_{j}$ are the marks on ${a}_{i},$ ${a}_{j}$ in $\Gamma $ and ${p}_{i}^{\prime},$ ${p}_{j}^{\prime}$ are the marks on ${a}_{i},$ ${a}_{j}$ in $\Gamma \prime \text{.}$ |

**Proposition 7.** Suppose $\Gamma \in \mathcal{C}$ is positive definite. If
$\Gamma \prime \in \mathcal{C}$ is a subgraph of $\Gamma ,$
then $\Gamma \prime $ is also positive definite.

Proof. | |

We order the vertices ${a}_{1},\dots ,{a}_{\ell}$ of $\Gamma $ in such a way that ${a}_{1},\dots ,{a}_{k}$ are the vertices of $\Gamma \prime \text{.}$ We will denote the marks on the vertices and edges of $\Gamma $ by the usual ${p}_{i}$ and ${q}_{ij},$ $1\le i,$ $j\le \ell ,$ and those of $\Gamma \prime $ by ${p}_{i}^{\prime}$ and ${q}_{ij}^{\prime},$ $1\le i,$ $j\le k\text{.}$ We let $\left({\alpha}_{ij}\right)$ be the matrix for $H\left(\Gamma \right)$ with respect to the basis $\{{v}_{1},\dots ,{v}_{\ell}\}$ and we let $\left({\alpha}_{ij}^{\prime}\right)$ be the matrix for $H\left(\Gamma \prime \right)$ with respect to the basis $\{{v}_{1},\dots ,{v}_{k}\}\text{.}$ We claim ${\alpha}_{ij}\le {\alpha}_{ij}^{\prime}\text{.}$ Since $\Gamma \prime \subset \Gamma ,$ for all $1\le i,$ $j\le k,$ ${p}_{i}^{\prime}\le {p}_{i},$ ${q}_{ij}^{\prime}\le {q}_{ij},$ and if there is an edge joining ${a}_{i}$ and ${a}_{j}$ in $\Gamma \prime $ then $|\frac{\prime}{{p}_{i}^{\prime}}-\frac{1}{{p}_{j}^{\prime}}|\ge |\frac{1}{{p}_{i}}-\frac{1}{{p}_{j}}|\text{.}$ Now ${p}_{i}^{\prime}\le {p}_{i}$ implies $\text{sin}(\pi /{p}_{i}^{\prime})\ge \text{sin}(\pi /{p}_{i})$ and thus ${\alpha}_{ii}^{\prime}\ge {\alpha}_{ii}\text{.}$ So assume $i\ne j\text{.}$ Now in general, ${\alpha}_{ij}\le 0\text{.}$ Hence if there is no edge in $\Gamma \prime $ joining ${a}_{i}$ and ${a}_{j},$ ${\alpha}_{ij}^{\prime}=0$ and thus ${\alpha}_{ij}\le {\alpha}_{ij}^{\prime}\text{.}$ So assume there is an edge in $\Gamma \prime $ joining ${a}_{i}$ and ${a}_{j}\text{.}$ Then we have $|\frac{1}{{p}_{i}^{\prime}}-\frac{1}{{p}_{j}^{\prime}}|\ge |\frac{1}{{p}_{i}}-\frac{1}{{p}_{j}}|,$ so ${\text{sin}}^{2}(\frac{\pi}{2{p}_{i}}-\frac{\pi}{2{p}_{j}})\ge {\text{sin}}^{2}(\frac{\pi}{2{p}_{i}}-\frac{\pi}{2{p}_{j}})\text{.}$ Also, ${q}_{ij}^{\prime}\le {q}_{ij}$ implies ${\text{cos}}^{2}(\pi /{q}_{ij})\ge {\text{cos}}^{2}(\pi /{q}_{ij}^{\prime})\text{.}$ Hence $-{\{{\text{cos}}^{2}(\pi /{q}_{ij})-{\text{sin}}^{2}(\frac{\pi}{2{p}_{i}}-\frac{\pi}{2{p}_{j}})\}}^{\frac{1}{2}}\le -{\{{\text{cos}}^{2}(\pi /{q}_{ij}^{\prime})-{\text{sin}}^{2}(\frac{\pi}{2{p}_{i}^{\prime}}-\frac{\pi}{2{p}_{j}^{\prime}})\}}^{\frac{1}{2}},$ i.e., ${\alpha}_{ij}\le {\alpha}_{ij}^{\prime}\text{.}$ Now assume the proposition is false. So there is a vector $v={x}_{1}{v}_{1}+\dots +{x}_{k}{v}_{k},$ $v\ne 0,$ such that $H\left(\Gamma \prime \right)(v,v)\le 0\text{.}$ For each $1\le j\le k$ write ${x}_{j}={c}_{j}+{\text{id}}_{j}$ and define ${y}_{j}=\left|{c}_{j}\right|+i\left|{d}_{j}\right|\text{.}$ Put $w={y}_{1}{v}_{1}+\dots +{y}_{k}{v}_{k}+0\xb7{v}_{k+1}+\dots +0\xb7{v}_{\ell}\text{.}$ Then $v\ne 0$ implies $w\ne 0\text{.}$ We have $$\begin{array}{ccc}0\ge H\left(\Gamma \prime \right)(v,v)& =& \sum _{1\le m,n\le k}{\alpha}_{mn}^{\prime}{X}_{m}{\stackrel{\u203e}{X}}_{n}\\ & =& \sum _{m}{\alpha}_{mm}^{\prime}{X}_{m}{\stackrel{\u203e}{X}}_{m}+\sum _{1\le m<n\le k}{\alpha}_{mn}^{\prime}({X}_{m}{\stackrel{\u203e}{X}}_{n}+{X}_{n}{\stackrel{\u203e}{X}}_{m})\\ & =& \sum _{m}{\alpha}_{mm}^{\prime}{X}_{m}{\stackrel{\u203e}{X}}_{m}+\sum _{1\le m<n\le k}2{\alpha}_{mn}^{\prime}({c}_{m}{c}_{n}+{d}_{m}{d}_{n})\\ & \ge & \sum {\alpha}_{mm}{y}_{m}{\stackrel{\u203e}{y}}_{m}+\sum _{1\le m<n\le k}2{\alpha}_{mn}^{\prime}(\left|{c}_{m}\right|\left|{c}_{n}\right|+\left|{d}_{m}\right|\left|{d}_{n}\right|)\\ & \ge & \sum {\alpha}_{mm}{y}_{m}{\stackrel{\u203e}{y}}_{m}+\sum _{1\le m<n\le k}{\alpha}_{mn}({y}_{m}{\stackrel{\u203e}{y}}_{n}+{y}_{n}{\stackrel{\u203e}{y}}_{m})\\ & =& \sum _{1\le m,n\le k}{\alpha}_{mn}{y}_{m}{\stackrel{\u203e}{y}}_{n}\\ & =& H\left(\Gamma \right)(w,w)\\ & >& 0,\end{array}$$ which is a contradiction. $\square $ |

Definition: Let $A=\left({a}_{ij}\right)$ be an
$n\times n$ matrix over $\u2102\text{.}$ Let
${A}^{\left(k\right)}$ for $1\le k\le n,$
denote the matrix formed by the upper left hand $k\times k$ corner of $A,$
i.e., ${A}^{\left(k\right)}=\left({a}_{ij}\right)$
$1\le i,j\le k\text{.}$ The
*principal minors of $A$* are the $n$ scalars
$\text{Det}\left({A}^{\left(k\right)}\right)$
$1\le k\le n\text{.}$

If ${A}^{t}=\stackrel{\u203e}{A}$ we say
*$A$ is positive definite* if and only if
$\sum _{i,j}{a}_{ij}{x}_{i}{\stackrel{\u203e}{x}}_{j}\ge 0$
for all ${x}_{1},\dots ,{x}_{n}\in \u2102,$
and $\sum _{i,j}{a}_{ij}{x}_{i}{\stackrel{\u203e}{x}}_{j}=0$
if and only if all ${x}_{i}=0\text{.}$

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]. $\square $ |

If $\Gamma \in \mathcal{C}$ we write $\text{Det}\left(\Gamma \right)$ for $\text{Det}\left(H\left(\Gamma \right)\right)$ and we denote by ${\mathcal{C}}^{\circ}$ the collection of all graphs $\Gamma $ in $\mathcal{C}$ such that $\text{Det}\left(\Gamma \right)=0,$ but if $\Gamma \prime \u2acb\Gamma $ then $\Gamma \prime \in {\mathcal{C}}^{+}\text{.}$ We also put ${\mathcal{C}}_{k}^{\circ}={\mathcal{C}}^{\circ}\cap {\mathcal{C}}_{k}\text{.}$

**Theorem 2.** The connected graphs in ${\mathcal{C}}^{+}$ are precisely those in List 1. (The subscript
on the letter denoting the graph indicates the number of vertices.)
$$\begin{array}{c}\text{List 1}\\ \begin{array}{c}\n\n\n\n\n\np\n\n\end{array}\hspace{0.17em}(p\ge 2)\\ \begin{array}{c}\n\n\n\n\n\n\n\n\n\nq\n\n\end{array}\hspace{0.17em}(q\ge 3),\begin{array}{c}\n\n\n\n\n\n\n\n\n\n3\n3\n\n\end{array},\begin{array}{c}\n\n\n\n\n\n\n\n\n\n3\n6\n\n\end{array},\begin{array}{c}\n\n\n\n\n\n\n\n\n\n3\n4\n3\n\n\end{array},\\ \begin{array}{c}\n\n\n\n\n\n\n\n\n\n4\n\n4\n\n\end{array},\begin{array}{c}\n\n\n\n\n\n\n\n\n\n3\n8\n\n\n\end{array},\begin{array}{c}\n\n\n\n\n\n\n\n\n\n4\n6\n\n\n\end{array},\begin{array}{c}\n\n\n\n\n\n\n\n\n\n4\n4\n3\n\n\end{array},\begin{array}{c}\n\n\n\n\n\n\n\n\n\n3\n5\n3\n\n\end{array},\\ \begin{array}{c}\n\n\n\n\n\n\n\n\n\n5\n\n5\n\n\end{array},\begin{array}{c}\n\n\n\n\n\n\n\n\n\n3\n10\n\n\n\end{array},\begin{array}{c}\n\n\n\n\n\n\n\n\n\n5\n6\n\n\n\end{array},\begin{array}{c}\n\n\n\n\n\n\n\n\n\n5\n4\n3\n\n\end{array}\text{.}\\ \begin{array}{c}\n\n\n\n\n\n\n\n\n\n\n3\n\n3\n\n3\n\n\end{array},\begin{array}{c}\n\n\n\n\n\n\n\n\n\n\n3\n\n3\n4\n\n\n\end{array},{H}_{3}\begin{array}{c}\n\n\n\n\n\n\n\n\n\n\n\n\n\n5\n\n\n\end{array},\\ {F}_{4}\begin{array}{c}\n\n\n\n\n\n\n\n\n\n\n\n\n\n\n4\n\n\n\n\n\end{array},{H}_{4}\begin{array}{c}\n\n\n\n\n\n\n\n\n\n\n\n\n\n\n\n\n5\n\n\n\end{array},\begin{array}{c}\n\n\n\n\n\n\n\n\n\n\n\n3\n\n3\n\n3\n\n3\n\n\end{array}\\ {E}_{6}\begin{array}{c}\n\n\n\n\n\n\n\n\n\n\n\n\n\n\end{array}\\ {E}_{7}\begin{array}{c}\n\n\n\n\n\n\n\n\n\n\n\n\n\n\n\end{array}\\ {E}_{8}\begin{array}{c}\n\n\n\n\n\n\n\n\n\n\n\n\n\n\n\n\end{array}\\ {A}_{\ell}\hspace{0.17em}(\ell \ge 2)\begin{array}{c}\n\n\n\n\n\n\n\n\n\end{array},\begin{array}{c}\n\n\n\n\n\n\n\n\n\n\end{array},\begin{array}{c}\n\n\n\n\n\n\n\n\n\n\n\end{array},\cdots \\ {B}_{\ell}^{p}\hspace{0.17em}(\ell ,p\ge 2)\begin{array}{c}\n\n\n\n\n\n\n\n\n\np\n4\n\n\end{array},\begin{array}{c}\n\n\n\n\n\n\n\n\n\n\np\n4\n\n\end{array},\begin{array}{c}\n\n\n\n\n\n\n\n\n\n\n\np\n4\n\n\end{array},\cdots \\ {D}_{\ell}\hspace{0.17em}(\ell \ge 4)\begin{array}{c}\n\n\n\n\n\n\n\n\n\n\n\n\end{array},\begin{array}{c}\n\n\n\n\n\n\n\n\n\n\n\n\n\end{array},\begin{array}{c}\n\n\n\n\n\n\n\n\n\n\n\n\n\n\end{array},\cdots \end{array}$$

**Theorem 3.** The connected graphs in ${\mathcal{C}}^{\circ}$ are precisely those in List 2.
(The subscript on the letter denoting the graph is one less than the number of vertices.)
$$\begin{array}{c}\text{List 2}\\ \begin{array}{c}\n\n\n\n\n\n\n\n\n\n6\n\n6\n\n\end{array},\begin{array}{c}\n\n\n\n\n\n\n\n\n\n3\n4\n6\n\n\end{array},\begin{array}{c}\n\n\n\n\n\n\n\n\n\n4\n4\n4\n\n\end{array},\begin{array}{c}\n\n\n\n\n\n\n\n\n\n\n6\n6\n\n\end{array},\begin{array}{c}\n\n\n\n\n\n\n\n\n\n3\n6\n3\n\n\end{array},\begin{array}{c}\n\n\n\n\n\n\n\n\n\n\n8\n4\n\n\end{array},\begin{array}{c}\n\n\n\n\n\n\n\n\n\n\n12\n3\n\n\end{array}\\ \begin{array}{c}\n\n\n\n\n\n\n\n\n\n\n\n4\np\n4\n\n\n\end{array}(p\ge 3),\begin{array}{c}\n\n\n\n\n\n\n\n\n\n\n\n\n\n6\n\n\n\end{array},\begin{array}{c}\n\n\n\n\n\n\n\n\n\n\n4\n\n4\n\n4\n\n\end{array},\begin{array}{c}\n\n\n\n\n\n\n\n\n\n\n4\n\n4\n4\n\n\n\end{array},\\ \begin{array}{c}\n\n\n\n\n\n\n\n\n\n\n3\n\n3\n4\n3\n\n\end{array}\\ \begin{array}{c}\n\n\n\n\n\n\n\n\n\n\n\n\n3\n3\n3\n3\n\n\end{array},\begin{array}{c}\n\n\n\n\n\n\n\n\n\n\n\n3\n\n3\n4\n\n\n\n\n\end{array},\begin{array}{c}\n\n\n\n\n\n\n\n\n\n\n\n3\n\n3\n\n3\n4\n\n\n\end{array}\\ {\stackrel{\sim}{F}}_{4}\begin{array}{c}\n\n\n\n\n\n\n\n\n\n\n\n\n\n\n\n4\n\n\n\n\n\n\n\end{array},\begin{array}{c}\n\n\n\n\n\n\n\n\n\n\n\n\n3\n\n3\n\n3\n\n3\n\n3\n\n\end{array}\\ {\stackrel{\sim}{E}}_{6}\begin{array}{c}\n\n\n\n\n\n\n\n\n\n\n\n\n\n\n\end{array}\\ {\stackrel{\sim}{E}}_{7}\begin{array}{c}\n\n\n\n\n\n\n\n\n\n\n\n\n\n\n\n\end{array}\\ {\stackrel{\sim}{E}}_{8}\begin{array}{c}\n\n\n\n\n\n\n\n\n\n\n\n\n\n\n\n\n\end{array}\\ {\stackrel{\sim}{D}}_{\ell}\hspace{0.17em}(\ell \ge 4)\begin{array}{c}\n\n\n\n\n\n\n\n\n\n\n\n\n\end{array},\begin{array}{c}\n\n\n\n\n\n\n\n\n\n\n\n\n\n\n\end{array},\begin{array}{c}\n\n\n\n\n\n\n\n\n\n\n\n\n\n\n\n\end{array},\cdots \\ {\stackrel{\sim}{B}}_{\ell}^{p}\hspace{0.17em}(\ell \ge 3)\begin{array}{c}\n\n\n\n\n\n\n\n\n\n\n\n\np\n4\n\n\end{array},\begin{array}{c}\n\n\n\n\n\n\n\n\n\n\n\n\n\np\n4\n\n\end{array},\begin{array}{c}\n\n\n\n\n\n\n\n\n\n\n\n\n\n\np\n4\n\n\end{array},\cdots \\ {\stackrel{\sim}{B}}_{\ell}^{p,p\prime}\hspace{0.17em}(\ell \ge 2)\begin{array}{c}\n\n\n\n\n\n\n\n\n\n\np\n4\n\n4\np\n\n\end{array},\begin{array}{c}\n\n\n\n\n\n\n\n\n\n\n\np\n4\n\n\n\n4\np\n\n\end{array},\begin{array}{c}\n\n\n\n\n\n\n\n\n\n\n\n\np\n4\n\n\n\n\n\n4\np\n\n\end{array},\cdots \\ {\stackrel{\sim}{A}}_{\ell}\hspace{0.17em}(\ell \ge 2)\begin{array}{c}\n\n\n\n\n\n\n\n\n\n\end{array},\begin{array}{c}\n\n\n\n\n\n\n\n\n\n\n\end{array},\begin{array}{c}\n\n\n\n\n\n\n\n\n\n\n\n\end{array},\cdots \end{array}$$

We will prove Theorems 2 and 3 simultaneously.

**Lemma 2.**

(a) | $\text{Det}\left({A}_{\ell}\right)=(\ell +1)/2\ell \text{.}$ |

(b) | $\text{Det}\left({B}_{\ell}^{p}\right)=\frac{\text{sin}\hspace{0.17em}\pi /p}{{2}^{\ell -1}}\text{.}$ |

(c) | $\text{Det}\left({\stackrel{\sim}{B}}_{\ell}^{p,p\prime}\right)=0\text{.}$ |

(d) | $\text{Det}\left({D}_{\ell}\right)=\frac{1}{{2}^{\ell -2}}\text{.}$ |

(e) | $\text{Det}\left({\stackrel{\sim}{B}}_{\ell}^{p}\right)=0\text{.}$ |

(f) | $\text{Det}\left({\stackrel{\sim}{A}}_{\ell}\right)=0\text{.}$ |

(g) | $\text{Det}\left({\stackrel{\sim}{D}}_{\ell}\right)=0\text{.}$ |

(h) | $\text{Det}\left({\stackrel{\sim}{E}}_{\ell}\right)=0\phantom{\rule{2em}{0ex}}\ell =6,7,8\text{.}$ |

(g) | $\text{Det}\left({\stackrel{\sim}{F}}_{4}\right)=0\text{.}$ |

Proof. | |

(a) See [BGr1971, p.58]. (b) If $\ell =2$ this is a trivial computation. So assume $\ell \ge 3\text{.}$ Expanding $\text{Det}\left({B}_{\ell}^{p}\right)$ along the first row we find $$\begin{array}{ccc}\text{Det}\left({B}_{\ell}^{p}\right)& =& \text{sin}\hspace{0.17em}\pi /p\hspace{0.17em}\text{Det}\left({A}_{\ell -1}\right)-\frac{1}{2}\text{sin}\hspace{0.17em}\pi /p\hspace{0.17em}\text{Det}\left({A}_{\ell -2}\right)\\ & =& \text{sin}\hspace{0.17em}\pi /p\xb7\frac{\ell}{{2}^{\ell -1}}-\text{sin}\hspace{0.17em}\pi /p\xb7\frac{\ell -1}{{2}^{\ell -1}}\\ & =& \frac{\text{sin}(\pi /p)}{{2}^{\ell -1}}\text{.}\end{array}$$ (c) If $\ell =2,$ this is an easy calculation. So we assume $\ell \ge 3\text{.}$ Expanding $\text{Det}\left({\stackrel{\sim}{B}}_{\ell}^{p,p\prime}\right)$ along the last column we have $$\begin{array}{ccc}\text{Det}\left({\stackrel{\sim}{B}}_{\ell}^{p,p\prime}\right)& =& \text{sin}\hspace{0.17em}\pi /p\prime \hspace{0.17em}\text{Det}\left({B}_{\ell}^{p}\right)-\frac{1}{2}\text{sin}\hspace{0.17em}\pi /p\prime \hspace{0.17em}\text{Det}\left({B}_{\ell -1}^{p}\right)\\ & =& \text{sin}\hspace{0.17em}\pi /p\prime \xb7\frac{\text{sin}\hspace{0.17em}\pi /p}{{2}^{\ell -1}}-\text{sin}\hspace{0.17em}\pi /p\prime \xb7\frac{\text{sin}\hspace{0.17em}\pi /p}{{2}^{\ell -1}}\\ & =& 0\text{.}\end{array}$$ (d) See [BGr1971, p.59]. (e) Again expanding by minors we obtain $$\begin{array}{ccc}\text{Det}\left({\stackrel{\sim}{B}}_{\ell}^{p}\right)& =& \text{sin}\hspace{0.17em}\pi /p\hspace{0.17em}\text{Det}\left({D}_{\ell}\right)-\frac{1}{2}\text{sin}\hspace{0.17em}\pi /p\hspace{0.17em}\text{Det}\left({D}_{\ell -1}\right)\\ & =& \frac{\text{sin}\hspace{0.17em}\pi /p}{{2}^{\ell -2}}-\frac{\text{sin}\hspace{0.17em}\pi /p}{{2}^{\ell -2}}\\ & =& 0\text{.}\end{array}$$ For proofs of (f) through (i) see [BGr1971, pp.60-61]. Notice that the ${k}^{\text{th}}$ principal minor of ${A}_{\ell}$ (respectively ${B}_{\ell}^{p},$ ${D}_{\ell}\text{)}$ is just $\text{Det}\left({A}_{k}\right)$ (respectively $\text{Det}\left({B}_{k}^{p}\right),$ $\text{Det}\left({D}_{k}\right)\text{)}$ 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 ${\stackrel{\sim}{B}}_{\ell}^{p,p\prime},$ ${\stackrel{\sim}{B}}_{\ell}^{p},$ ${\stackrel{\sim}{A}}_{\ell},$ ${\stackrel{\sim}{D}}_{\ell},$ ${\stackrel{\sim}{E}}_{\ell}$ $(\ell =6,7,8),$ or ${\stackrel{\sim}{F}}_{4}$ as a subgraph can be positive definite and hence is to be excluded from List 1. $\square $ |

We can now begin in earnest to prove Theorems 2 and 3. It is obvious that ${\mathcal{C}}_{1}\subset {\mathcal{C}}^{+}\text{.}$

Step I. We will determine the connected graphs in ${\mathcal{C}}_{2}^{+}$ and the connected graphs in ${\mathcal{C}}_{2}^{\circ}\text{.}$ Suppose $\Gamma \in {\mathcal{C}}_{2}$ is connected. Thus $\Gamma $ is ${p}_{1}\left[q\right]{p}_{2}$ with $q\ge 3\text{.}$ Now the matrix for $H\left(\Gamma \right)$ in the basis $\{{v}_{1},{v}_{2}\}$ is $$\left(\begin{array}{cc}{\alpha}_{11}& {\alpha}_{12}\\ {\alpha}_{21}& {\alpha}_{22}\end{array}\right)$$ the first principal minor of which is ${\alpha}_{11}=\text{sin}\hspace{0.17em}\pi /{p}_{1}>0\text{.}$ So by Proposition 8, $\Gamma $ will be positive definite if and only if $\text{Det}\left(\Gamma \right)>0\text{.}$ Now $$\begin{array}{ccc}\text{Det}\left(\Gamma \right)& =& \text{sin}\hspace{0.17em}\pi /{p}_{1}\hspace{0.17em}\text{sin}\pi /{p}_{2}-{\text{cos}}^{2}(\pi /q)+{\text{sin}}^{2}(\frac{\pi}{2{p}_{1}}-\frac{\pi}{2{p}_{2}})\\ & =& -\frac{1}{2}(\text{cos}\left(\frac{2\pi}{q}\right)+\text{cos}(\frac{\pi}{{p}_{1}}+\frac{\pi}{{p}_{2}}))\text{.}\end{array}$$ Thus, $\text{Det}\left(\Gamma \right)>0$ if and only if $$\text{cos}(\pi -\frac{2\pi}{q})>\text{cos}(\frac{\pi}{{p}_{1}}+\frac{\pi}{{p}_{2}}),$$ and $\text{Det}\left(\Gamma \right)=0$ if and only if $$\text{cos}(\pi -\frac{2\pi}{q})=\text{cos}(\frac{\pi}{{p}_{1}}+\frac{\pi}{{p}_{2}})\text{.}$$ Since both arguments lie in the interval $[0,\pi ]$ over which cosine is strictly decreasing we have $\text{Det}\left(\Gamma \right)>0$ if and only if $$\begin{array}{cc}\text{(2)}& \frac{1}{{p}_{1}}+\frac{1}{{p}_{2}}>1-2/q\phantom{\rule{2em}{0ex}}\text{[Cox1962, p.94]}\end{array}$$ and $\text{Det}\left(\Gamma \right)=0$ if and only if $$\begin{array}{cc}\text{(3)}& \frac{1}{{p}_{1}}+\frac{1}{{p}_{2}}=1-2/q\phantom{\rule{2em}{0ex}}\text{[Cox1974, p.110].}\end{array}$$ The solutions to (2) subject to the restrictions $q\ge 3,$ ${p}_{1},{p}_{2}\ge 2,$ and ${p}_{1}={p}_{2}$ if $q$ is odd are given in [Cox1962, p.96] and reproduced here: $p\left[4\right]2,$ $2\left[q\right]2,$ $3\left[3\right]3,$ $3\left[6\right]2,$ $3\left[4\right]3,$ $4\left[3\right]4,$ $3\left[8\right]2,$ $4\left[6\right]2,$ $4\left[4\right]3,$ $3\left[5\right]3,$ $5\left[3\right]5,$ $3\left[10\right]2,$ $5\left[6\right]2,$ $5\left[4\right]3$ $({p}_{1}\ge {p}_{2})\text{.}$ 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\left[3\right]6,$ $3\left[4\right]6,$ $4\left[4\right]4,$ $2\left[6\right]6,$ $3\left[6\right]3,$ $2\left[8\right]4,$ $2\left[12\right]3$ $({p}_{1}\ge {p}_{2})\text{.}$ Now by the definition of a subgraph it is easy to verify that if $\Gamma \in {\mathcal{C}}_{2}$ and if $\Gamma \prime \u2acb\Gamma ,$ then $\text{Det}\left(\Gamma \prime \right)>\text{Det}\left(\Gamma \right)\text{.}$ Thus if $\Gamma $ occurs amongst those graphs just listed, we have $\text{Det}\left(\Gamma \prime \right)>0\text{.}$ So every proper subgraph of $\Gamma $ is positive definite and these graphs comprise the set of connected graphs in ${\mathcal{C}}_{2}^{\circ}$ as indicated in List 2.

Step II. We determine all linear graphs in ${\mathcal{C}}_{3}^{+}$ and all linear graphs in ${\mathcal{C}}_{3}^{\circ}\text{.}$ Let $\Gamma \in {\mathcal{C}}_{3}$ be linear. Thus $\Gamma $ is $p\prime \left[q\prime \right]p\left[q\u2033\right]p\u2033\text{.}$ Putting $s=\text{sin}\hspace{0.17em}\pi /p,$ $s\prime =\text{sin}\hspace{0.17em}\pi /p\prime ,$ $s\u2033=\text{sin}\hspace{0.17em}\pi /p\u2033,$ $c=\text{cos}\hspace{0.17em}\pi /p,$ $c\prime =\text{cos}\hspace{0.17em}\pi /p\prime ,$ and $c\u2033=\text{cos}\hspace{0.17em}\pi /p\u2033$ we find (after using some trigonometric identities) that $$\begin{array}{ccccc}\text{Det}\left(\Gamma \right)& =& \frac{1}{2}(s\prime +s\u2033)& -& s\prime ({\text{cos}}^{2}\pi /q\u2033+\frac{1}{2}cc\u2033)\\ & & & -& s\u2033({\text{cos}}^{2}\pi /q\prime +\frac{1}{2}cc\prime )\text{.}\end{array}$$ We will determine the linear graphs in ${\mathcal{C}}_{3}^{+}$ first. The condition that $\text{Det}\left(\Gamma \right)>0$ is $$\begin{array}{cc}\text{(4)}& \frac{1}{2}(s\prime +s\u2033)>s\prime ({\text{cos}}^{2}\pi /q\u2033+\frac{1}{2}cc\u2033)+s\u2033({\text{cos}}^{2}\pi /q\prime +\frac{1}{2}cc\prime )\text{.}\end{array}$$ Since ${\text{cos}}^{2}\pi /4=\frac{1}{2},$ if (4) is to hold, we cannot have both $q\u2033\ge 4$ and $q\prime \ge 4\text{.}$ So one of them must be $3\text{.}$ Without loss of generality, $q\prime =3\text{.}$ Hence, $p=p\prime ,$ so $\Gamma $ is $p\left[3\right]p\left[q\u2033\right]p\u2033\text{.}$

Now if $q\u2033\ge 6,$ ${\text{cos}}^{2}(\pi /q\u2033)\ge \frac{3}{4}\text{.}$ Thus if $q\u2033\ge 6,$ (4) forces $\frac{1}{2}(s+s\u2033)>s(\frac{3}{4}+\frac{1}{2}cc\u2033)+s\u2033(\frac{1}{4}+\frac{1}{2}{c}^{2})$ or $$\begin{array}{cc}\text{(5)}& \frac{1}{4}s\u2033>\frac{1}{4}s+\frac{1}{2}scc\u2033+\frac{1}{2}s\u2033{c}^{2}\text{.}\end{array}$$ Comparing the left side with the first term on the right we see $p>p\u2033,$ so in particular $p>2\text{.}$ But comparing the left side with the last term on the right we see that ${c}^{2}<\frac{1}{2}$ and thus $4>p\text{.}$ So we must have $p=3$ and $p\u2033=2\text{.}$ But substituting these values in (5) yields $\frac{1}{4}>\frac{\sqrt{3}+1}{8}$ a contradiction. Hence, $q\u2033\le 5\text{.}$

If $q\u2033=3,$ then $p\u2033=p$ and (4) becomes $s>s(\frac{1}{2}+{c}^{2})$ which holds if and only if $p=2$ or $p=3\text{.}$

If $q\u2033=4$ (4) becomes $$\begin{array}{cc}\text{(6)}& \frac{1}{2}s\u2033>\frac{1}{2}scc\u2033+s\u2033(\frac{1}{4}+\frac{1}{2}{c}^{2})\text{.}\end{array}$$ Comparing the left side with the second term on the right we see we must have $p=2$ or $p=3\text{.}$ Substituting $p=2$ in (6) we obtain $\frac{1}{2}s\u2033>\frac{1}{4}s\u2033$ and thus $p\u2033$ is arbitrary in this case. Substituting $p=3$ in (6) we obtain $\frac{1}{8}s\u2033>\frac{\sqrt{3}}{8}c\u2033$ or $\text{tan}\hspace{0.17em}\pi /p\u2033>\sqrt{3}$ which forces $p\u2033=2\text{.}$

If $q\u2033=5,$ $p=p\u2033$ and (4) becomes $1>{\text{cos}}^{2}\pi /5+\frac{1}{4}+{c}^{2}$ which forces $p=2\text{.}$

Thus $\text{Det}\left(\Gamma \right)>0$ forces $\Gamma $ to be one of: ${A}_{3},$ $3\left[3\right]3\left[3\right]3,$ ${B}_{3}^{p},$ $3\left[3\right]3\left[4\right]2,$ $2\left[3\right]2\left[5\right]2\text{.}$

Now for such $\Gamma $ the first principal minor of $H\left(\Gamma \right)$ is obviously positive and the second principal minor is the determinant of the Hermitian form associated with the graph obtained from $\Gamma $ 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 ${\mathcal{C}}_{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 ${\mathcal{C}}_{3}^{\circ}\text{.}$ For a linear graph $\Gamma \in {\mathcal{C}}_{3}$ the expression for $\text{Det}\left(\Gamma \right)$ appears at the beginning of Step II and we see that the condition that $\text{Det}\left(\Gamma \right)=0$ is $$\begin{array}{cc}\text{(4')}& \frac{1}{2}(s\prime +s\u2033)=s\prime ({\text{cos}}^{2}(\pi /q\u2033)+\frac{1}{2}cc\u2033)+s\u2033({\text{cos}}^{2}(\pi /q\prime )+\frac{1}{2}cc\prime )\text{.}\end{array}$$ Again, since ${\text{cos}}^{2}\pi /4=\frac{1}{2},$ we see that if $q\prime \ge 4$ and $q\u2033\ge 4$ we must have $q\prime =q\u2033=4$ and $cc\u2033=cc\prime =0\text{.}$ Hence, either $p=2$ and $p\prime $ and $p\u2033$ are arbitrary or $p\prime =p\u2033=2$ and $p$ is arbitrary. Thus if $q\prime \ge 4$ and $q\u2033\ge 4$ (4') forces $\Gamma $ to be either ${\stackrel{\sim}{B}}_{2}^{p\prime ,p\u2033}$ or $2\left[4\right]p\left[4\right]2\text{.}$ Thus we assume without loss of generality that $q\prime =3\text{.}$ Hence $p=p\prime $ and $\Gamma $ is $p\left[3\right]p\left[q\u2033\right]p\u2033\text{.}$ We rearrange (4') to obtain $$\begin{array}{cc}\text{(5')}& \frac{1}{4}s\u2033=s({\text{cos}}^{2}\pi /q\u2033-\frac{1}{2})+\frac{1}{2}scc\u2033+\frac{1}{2}s\u2033{c}^{2}\text{.}\end{array}$$ Recalling that ${\text{cos}}^{2}\pi /6=\frac{3}{4}$ we see that if $q\u2033\ge 7$ we must have $s\u2033>s$ and thus $p>p\u2033\text{.}$ In particular, $p>2\text{.}$ Further, if $q\u2033\ge 7,$ 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 ${c}^{2}<\frac{1}{2},$ so $p<4\text{.}$ Hence, $q\u2033\ge 7$ forces $p=3$ and $p\u2033=2\text{.}$ Substituting these values in (5') we obtain $$\begin{array}{ccc}\frac{1}{8}& =& \frac{\sqrt{3}}{2}({\text{cos}}^{2}\pi /q\u2033-\frac{1}{2})\\ & >& \frac{\sqrt{3}}{2}({\text{cos}}^{2}\pi /6-\frac{1}{2})\\ & =& \frac{\sqrt{3}}{8}\phantom{\rule{2em}{0ex}}\text{a contradiction.}\end{array}$$ Thus we may assume $q\u2033\le 6\text{.}$ If $q\u2033-6,$ (5') becomes $\frac{1}{4}s\u2033=\frac{1}{4}s+\frac{1}{2}scc\u2033+\frac{1}{2}s\u2033{c}^{2}\text{.}$ 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 ${c}^{2}<\frac{1}{2}$ so $p=3$ or $p=2\text{.}$ If $p=2$ we must have $s\u2033=s$ and thus $p\u2033=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\u2033>s,$ so $p>p\u2033$ and thus $p\u2033=2\text{.}$ Substituting these values in the equation above we obtain $\frac{1}{4}=\frac{\sqrt{3}+1}{8}$ a contradiction. So if $q\u2033=6,$ $\Gamma $ is $2\left[3\right]2\left[6\right]2\text{.}$

If $q\u2033=5$ we have $p=p\u2033$ 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 ${c}^{2}=\frac{1}{2}$ so $p=2$ or $p=3\text{.}$ However, substituting either of these values in (5') yields a contradiction.

If $q\u2033=4$ (5') becomes $\frac{1}{4}s\u2033=\frac{1}{2}scc\u2033+\frac{1}{2}s\u2033{c}^{2}\text{.}$ In particular, $p\ne 2\text{.}$ Now comparing the left with the last term on the right we see ${c}^{2}\le \frac{1}{2}$ and ${c}^{2}=\frac{1}{2}$ forces $c\u2033-0\text{.}$ Thus $p=3$ or $p=4$ and $p\u2033=2\text{.}$ If $p=3$ we have $\frac{1}{8}s\u2033=\frac{\sqrt{3}}{8}c\u2033,$ or $\text{tan}\hspace{0.17em}\pi /p\u2033=\sqrt{3}$ and thus $p\u2033=3\text{.}$ So if $q\u2033=4,$ $\Gamma $ is either $4\left[3\right]4\left[4\right]2$ or $3\left[3\right]3\left[4\right]3\text{.}$

If $q\u2033=3,$ $p=p\u2033$ and (5') becomes ${c}^{2}=\frac{1}{2}\text{.}$ Thus, $p=4$ and $\Gamma $ is $4\left[3\right]4\left[3\right]4\text{.}$

We have now shown that if $\Gamma \in {\mathcal{C}}_{3}$ is linear and satisfies $\text{Det}\left(\Gamma \right)=0,$ then $\Gamma $ is one of ${\stackrel{\sim}{B}}_{2}^{p\prime ,p\u2033},$ $2\left[4\right]p\left[4\right]2,$ $2\left[3\right]2\left[6\right]2,$ $4\left[3\right]4\left[4\right]2,$ $3\left[3\right]3\left[4\right]3,$ $4\left[3\right]4\left[3\right]4\text{.}$ 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 $\Gamma $ is one of the graphs just listed and if $\Gamma \prime \u2acb\Gamma ,$ then $\Gamma \prime \in {\mathcal{C}}^{+}\text{.}$ In light of the first parts of Steps I and II, this task amounts to no more than seeing if the subgraph $\Gamma \prime $ 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 ${\mathcal{C}}_{4}^{+}$ or in ${\mathcal{C}}_{4}^{\circ}\text{.}$ Suppose $\Gamma \in {\mathcal{C}}_{4}^{+}\cup {\mathcal{C}}_{4}^{\circ}$ is linear. Say $\Gamma $ is ${p}_{1}\left[{q}_{12}\right]{p}_{2}\left[{q}_{23}\right]{p}_{3}\left[{q}_{34}\right]{p}_{4}\text{.}$ Then either by Proposition 7 (if $\Gamma \in {\mathcal{C}}_{4}^{+}\text{)}$ or by definition (if $\Gamma \in {\mathcal{C}}_{4}^{\circ}\text{)}$ the pair of subgraphs ${p}_{1}\left[{q}_{12}\right]{p}_{2}\left[{q}_{23}\right]{p}_{3}$ and ${p}_{2}\left[{q}_{23}\right]{p}_{3}\left[{q}_{34}\right]{p}_{4}$ must lie in ${\mathcal{C}}_{3}^{+}\text{.}$ Since we have previously determined the linear graphs in ${\mathcal{C}}_{3}^{+}$ we search that list for suitable pSirs and we obtain the following graphs as candidates for membership in ${\mathcal{C}}_{4}^{+}\cup {\mathcal{C}}_{4}^{\circ}\text{.}$

(i) | ${A}_{4}$ |

(ii) | ${B}_{4}^{p}$ |

(iii) | ${H}_{4}$ |

(iv) | ${F}_{4}$ |

(v) | $3\left[3\right]3\left[3\right]3\left[3\right]3$ |

(vi) | ${\stackrel{\sim}{B}}_{3}^{p\prime ,p}$ |

(vii) | $3\left[3\right]3\left[4\right]2\left[3\right]2$ |

(viii) | $3\left[3\right]3\left[3\right]3\left[4\right]2$ |

(ix) | $2\left[5\right]2\left[3\right]2\left[4\right]p$ |

(x) | $2\left[4\right]3\left[3\right]3\left[4\right]2$ |

(xi) | $2\left[3\right]2\left[5\right]2\left[3\right]2$ |

(xii) | $2\left[5\right]2\left[3\right]2\left[5\right]2$ |

The determinants of both (vii) and (viii) are computed to be zero. In (ix), by reducing the 5 to 4 we obtain ${\stackrel{\sim}{B}}_{3}^{2,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 ${\stackrel{\sim}{B}}_{3}^{2,2}$ as a subgraph. Hence the linear graphs in ${\mathcal{C}}_{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 ${\mathcal{C}}_{5}^{+}\cup {\mathcal{C}}_{5}^{\circ}\text{.}$ By the same type of reasoning as that used at the beginning of Step III we see that ${\mathcal{C}}_{5}^{+}\cup {\mathcal{C}}_{5}^{\circ}$ must consist of some of the graphs from the following possibilities:

(i) | ${A}_{5}$ |

(ii) | ${B}_{5}^{p}$ |

(iii) | ${\stackrel{\sim}{B}}_{4}^{p,p\prime}$ |

(iv) | ${\stackrel{\sim}{F}}_{4}$ |

(v) | $3\left[3\right]3\left[3\right]3\left[3\right]3\left[3\right]3$ |

(vi) | $2\left[5\right]2\left[3\right]2\left[3\right]2\left[3\right]2$ |

(vii) | $2\left[5\right]2\left[3\right]2\left[3\right]2\left[4\right]p$ |

(viii) | $2\left[5\right]2\left[3\right]2\left[3\right]2\left[5\right]2$ |

Step V. (a) For $\ell \ge 5$ the linear graphs in ${\mathcal{C}}_{\ell}^{+}$ are ${A}_{\ell}$ and ${B}_{\ell}^{p}\text{.}$ (b) For $\ell \ge 6$ the linear graphs in ${\mathcal{C}}_{\ell}^{\circ}$ are ${\stackrel{\sim}{B}}_{\ell -1}^{p,p\prime}\text{.}$

Arguing as we have in the previous steps and using $\text{Det}\left({\stackrel{\sim}{B}}_{n}^{p,p\prime}\right)=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 ${\mathcal{C}}^{+}\cup {\mathcal{C}}^{\circ}\text{.}$ We next show that a connected graph in ${\mathcal{C}}^{+}$ must be a tree and that the graphs ${\stackrel{\sim}{A}}_{\ell},$ $(\ell \ge 2)$ are the only connected graphs in ${\mathcal{C}}^{\circ}$ 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 ${\stackrel{\sim}{A}}_{\ell}$ are positive definite and since $\text{Det}\left({\stackrel{\sim}{A}}_{\ell}\right)=0$ by Lemma 2 we have ${\stackrel{\sim}{A}}_{\ell -1}\in {\mathcal{C}}_{\ell}^{\circ}\text{.}$

Step VI. Let $\Gamma $ denote the $3$ cycle $$\begin{array}{c}\n\n\n\n\n\n\n\n\n\n\n\np\np\u2033\np\u2032\nq\u2033\nq\nq\u2032\n\n\end{array}\text{.}$$ If $\Gamma \in {\mathcal{C}}_{3}^{+}\cup {\mathcal{C}}_{3}^{\circ}$ then $\Gamma ={\stackrel{\sim}{A}}_{2}\text{.}$

Proof. | |

Put $a={\left\{\frac{1}{2}\text{cos}(\frac{\pi}{p}-\frac{\pi}{p\prime})\right\}}^{\frac{1}{2}},$ $b={\left\{\frac{1}{2}\text{cos}(\frac{\pi}{p}-\frac{\pi}{p\u2033})\right\}}^{\frac{1}{2}},$ $c={\left\{\frac{1}{2}\text{cos}(\frac{\pi}{p\prime}-\frac{\pi}{p\u2033})\right\}}^{\frac{1}{2}},$ $s=\text{sin}\hspace{0.17em}\pi /p,$ $s\prime =\text{sin}\hspace{0.17em}\pi /p\prime ,$ $s\u2033=\text{sin}\hspace{0.17em}\pi /p\u2033,$ $c=\text{cos}\hspace{0.17em}\pi /p,$ $c\prime =\text{cos}\hspace{0.17em}\pi /p\prime ,$ and $c\u2033=\text{cos}\hspace{0.17em}\pi /p\u2033\text{.}$ Case (1) None of $q,$ $q\prime ,$ $q\u2033$ is three. Then ${\Gamma}_{0},$ $$\begin{array}{c}\n\n\n\n\n\n\n\n\n\n\n\np\np\u2033\np\u2032\n4\n4\n4\n\n\end{array},$$ is a subgraph (perhaps not proper) and hence $\text{Det}\left({\Gamma}_{0}\right)\ge 0\text{.}$ Now the matrix for the form $H\left({\Gamma}_{0}\right)$ is $\left(\begin{array}{ccc}s& -a& -b\\ -a& s\prime & -c\\ -b& -c& s\u2033\end{array}\right)\text{.}$ Thus, $$\begin{array}{ccc}\text{Det}\left({\Gamma}_{0}\right)& =& ss\prime s\u2033-2abc-{b}^{2}s\prime -{c}^{2}s-{a}^{2}s\u2033\\ & =& -\frac{1}{2}ss\prime s\u2033-2abc-\frac{1}{2}s\prime cc\u2033-\frac{1}{2}s\prime cc\u2033-\frac{1}{2}s\prime cc\u2033-\frac{1}{2}s\u2033cc\prime \\ & <& 0\text{, giving a contradiction.}\end{array}$$ Case (2) Exactly one of $q,$ $q\prime ,$ $q\u2033$ is $3\text{.}$ Without loss of generality $q=3\text{.}$ Thus $p=p\prime ,$ and ${\Gamma}_{0},$ $$\begin{array}{c}\n\n\n\n\n\n\n\n\n\n\n\np\np\u2033\np\u2032\n4\n\n4\n\n\end{array},$$ is a subgraph. So again we must have $\text{Det}\left({\Gamma}_{0}\right)\ge 0\text{.}$ But the matrix for $H\left({\Gamma}_{0}\right)$ is $\left(\begin{array}{ccc}s& -\frac{1}{2}& -b\\ -\frac{1}{2}& s& -b\\ -b& -b& s\u2033\end{array}\right),$ and thus $$\begin{array}{ccc}\text{Det}\left({\Gamma}_{0}\right)& =& {s}^{2}s\u2033-{b}^{2}-2s{b}^{2}-\frac{1}{4}s\u2033\\ & =& -{b}^{2}-scc\u2033-\frac{1}{4}s\u2033\\ & <& 0\text{, yielding a contradiction.}\end{array}$$ Case (3) Two of $q,$ $q\prime ,$ $q\u2033$ are $3\text{.}$ Without loss of generality say $q$ and $q\prime $ are $3\text{.}$ Thus, $p=p\prime =p\u2033$ and if necessary we reduce all of them simultaneously to $2\text{.}$ Further we then reduce $q\u2033$ to $3$ if necessary to obtain ${\stackrel{\sim}{A}}_{2}$ as a subgraph. But this cannot be a proper subgraph as $\text{Det}\left({\stackrel{\sim}{A}}_{2}\right)=0\text{.}$ Hence $\Gamma ={\stackrel{\sim}{A}}_{2}\text{.}$ $\square $ |

Step VII. Let $\Gamma $ denote the $4$ cycle $$\begin{array}{c}\n\n\n\n\n\n\n\n\n\n\n\np1\np2\np3\np4\n\nq12\nq23\nq34\nq14\n\n\end{array}\text{.}$$ If $\Gamma \in {\mathcal{C}}_{4}^{+}\cup {\mathcal{C}}_{4}^{\circ},$ then $\Gamma $ is ${\stackrel{\sim}{A}}_{3}\text{.}$

Proof. | |

Note that if all the ${p}_{i},$ $1\le i\le 4,$ are the same we can reduce them simultaneously to $2$ and then reduce the marks on the four edges to 3's to obtain ${\stackrel{\sim}{A}}_{3}$ as a subgraph. But since $\text{Det}\left({\stackrel{\sim}{A}}_{3}\right)=0$ this cannot be a proper subgraph and hence $\Gamma ={\stackrel{\sim}{A}}_{3}\text{.}$ Thus we can assume that at least two of the edges of $\Gamma $ 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 ${\mathcal{C}}_{3}^{+}$ has both its edges marked with numbers larger than 3. Thus at most two of the edges of $\Gamma $ can be so marked and hence ${\Gamma}_{0},$ $$\begin{array}{c}\n\n\n\n\n\n\n\n\n\n\n\np\np\np\u2032\np\u2032\n\n\n4\n\n4\n\n\end{array},$$ is a subgraph of $\Gamma \text{.}$ Further, $p\left[4\right]p\prime \left[3\right]p\prime $ is a subgraph and must occur in List 1. Thus one of $p,$ $p\prime $ is 2. Glancing back at ${\Gamma}_{0}$ we see it does not matter which is 2, so without loss of generality, $p\prime =2\text{.}$ Thus writing $s=\text{sin}\hspace{0.17em}\pi /p$ and $a=-{(s/2)}^{\frac{1}{2}}$ the matrix for $H\left({\Gamma}_{0}\right)$ is $$\left(\begin{array}{cccc}s& -\frac{1}{2}& 0& a\\ -\frac{1}{2}& s& a& 0\\ 0& a& 1& -\frac{1}{2}\\ a& 0& -\frac{1}{2}& 1\end{array}\right),$$ and $\text{Det}\left({\Gamma}_{0}\right)=-\frac{s}{4}-\frac{3}{16}<0,$ giving a contradiction. $\square $ |

Step VIII. Let $\Gamma $ denote the 5 cycle $$\begin{array}{c}\n\n\n\n\n\n\n\n\n\n\n\n\np1\np2\np3\np4\np5\nq12\nq23\nq34\nq23\nq15\n\n\end{array}\text{.}$$ If $\Gamma \in {\mathcal{C}}_{5}^{+}\cup {\mathcal{C}}_{5}^{\circ}$ then $\Gamma $ is ${\stackrel{\sim}{A}}_{4}\text{.}$

Proof. | |

Arguing as in Step VII we see that if all the ${p}_{i},$ $1\le i\le 5,$ are the same we will have $\Gamma ={\stackrel{\sim}{A}}_{4}\text{.}$ So we assume that not all the edges of $\Gamma $ are labeled with the number 3. Without loss of generality, say ${q}_{34}\ne 3\text{.}$ Now the subgraph $$\Gamma \prime :\phantom{\rule{2em}{0ex}}{p}_{2}\left[{q}_{23}\right]{p}_{3}\left[{q}_{34}\right]{p}_{4}\left[{q}_{45}\right]{p}_{5}$$ must occur in List 1 and thus ${q}_{34}\ne 3$ implies that $\Gamma \prime $ is ${F}_{4},$ forcing ${p}_{i}=2,$ $2\le i\le 5\text{.}$ Further we can now conclude that the subgraph $$\Gamma \u2033:\phantom{\rule{2em}{0ex}}{p}_{1}\left[{q}_{12}\right]{p}_{2}\left[{q}_{23}\right]{p}_{3}\left[{q}_{34}\right]{p}_{4}$$ is ${p}_{1}\left[{q}_{12}\right]2\left[3\right]2\left[4\right]2$ and must also occur in List 1. Glancing at that list we see that $\Gamma \u2033$ must be $2\left[3\right]2\left[3\right]2\left[4\right]2\text{.}$ So ${p}_{i}=2,$ $1\le i\le 5$ and thus $\Gamma ={\stackrel{\sim}{A}}_{4}$ as remarked at the beginning of this step. This is a contradiction as we're assuming ${q}_{34}\ne 3\text{.}$ $\square $ |

Step IX. Let $\Gamma $ denote an $\ell $ cycle. If $\Gamma \in {\mathcal{C}}_{\ell}^{+}\cup {\mathcal{C}}_{\ell}^{\circ},$ then $\Gamma $ is ${\stackrel{\sim}{A}}_{\ell -1}\text{.}$

Proof. | |

We may assume $\ell \ge 6\text{.}$ Consider any two adjacent vertices ${a}_{i}$ and ${a}_{i+1}$ $\mathrm{(}1\le i\le \ell ,$ if $i=\ell ,$ read $i+1=1\text{)}$ of $\Gamma \text{.}$ We will show ${p}_{i}={p}_{i+1}=2$ and ${q}_{i,i+1}=3\text{.}$ By relabelling we may assume $i=2\text{.}$ Now the subgraph $\Gamma \prime $ ${p}_{1}\left[{q}_{12}\right]{p}_{2}\left[{q}_{23}\right]{p}_{3}\left[{q}_{34}\right]{p}_{4}\left[{q}_{45}\right]{p}_{5}$ must occur in List 1 and hence $\Gamma \prime $ is either ${A}_{5}$ or ${B}_{5}^{p}\text{.}$ In either case ${p}_{2}={p}_{3}=2$ and ${q}_{23}=3\text{.}$ Thus $\Gamma ={\stackrel{\sim}{A}}_{\ell -1}\text{.}$ $\square $ |

Now Proposition 7 together with Step IX imply that every connected graph in ${\mathcal{C}}^{+}$ is a tree and that the graphs ${\stackrel{\sim}{A}}_{\ell}$ $(\ell \ge 2)$ are the only connected graphs in ${\mathcal{C}}^{\circ}$ which are not trees. Also we have previously determined all the linear graphs in ${\mathcal{C}}^{+}\cup {\mathcal{C}}^{\circ}\text{.}$ So we must consider non linear trees which leads us to the

Definition: Let $\Gamma \in \mathcal{C}$ and suppose $a$ is a vertex of $\Gamma \text{.}$ The degree of $a,$ written $\text{Deg}\left(a\right),$ is the number of vertices $b$ of $\Gamma $ such that there is an edge in $\Gamma $ between $a$ and $b\text{.}$ We say that $a$ is a branch point of $\Gamma $ if $\text{Deg}\left(a\right)\ge 3\text{.}$

Our determination of the connected graphs in ${\mathcal{C}}^{+}\cup {\mathcal{C}}^{\circ}$ will be complete if we determine those which contain a branch point.

Step X. Let $\Gamma $ denote the graph $$\begin{array}{c}\n\n\n\n\n\n\n\n\n\n\n\n\np4\np3\np2\np1\nq12\nq23\nq24\n\n\end{array}\text{.}$$ If $\Gamma \in {\mathcal{C}}_{4}^{+},$ $\Gamma ={D}_{4}\text{.}$ If $\Gamma \in {\mathcal{C}}_{4}^{\circ},$ $\Gamma ={\stackrel{\sim}{B}}_{3}^{p}$ or $\Gamma $ is $$\begin{array}{c}\n\n\n\n\n\n\n\n\n\n\n\n\n3\n3\n3\n3\n\n\end{array}\text{.}$$

Proof. | |

Suppose $\Gamma \in {\mathcal{C}}_{4}^{+}\cup {\mathcal{C}}_{4}^{\circ}\text{.}$ Case (1) ${q}_{12}={q}_{23}={q}_{34}=3\text{.}$ Thus ${p}_{4}\left[3\right]{p}_{2}\left[3\right]{p}_{1}$ and ${p}_{3}\left[3\right]{p}_{2}\left[3\right]{p}_{1}$ are subgraphs. Consulting List 1 we see we must have ${p}_{i}=2,$ $1\le i\le 4$ or ${p}_{i}=3,$ $1\le i\le 4\text{.}$ The first alternative is ${D}_{4}$ 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 ${\mathcal{C}}_{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 $\Gamma $ is not 3. Without loss of generality, ${q}_{12}\ne 3\text{.}$ Thus $\Gamma $ is $$\begin{array}{c}\n\n\n\n\n\n\n\n\n\n\n\n\np\np\np\np\u2032\nq\n\n\n\n\end{array}\text{.}$$ Here again $p\left[3\right]p\left[3\right]p$ is a subgraph and hence $p=2$ or $p=3\text{.}$ Subcase (i). Suppose $p=2\text{.}$ Then $2\left[3\right]2\left[q\right]p\prime $ is a subgraph and thus $q=4$ with $p\prime $ arbitrary or $q=5$ and $p\prime =2\text{.}$ In the first instance $\Gamma ={\stackrel{\sim}{B}}_{3}^{p\prime}$ and all its proper subgraphs are positive definite, while in the second instance we can reduce the 5 to 4 to obtain ${\stackrel{\sim}{B}}_{3}^{2}$ as a proper subgraph yielding a contradiction. Subcase (ii). Suppose $p=3\text{.}$ Then $3\left[3\right]3\left[q\right]p\prime $ is a subgraph and thus $q=4$ and $p\prime =2\text{.}$ Hence $\Gamma $ is $$\begin{array}{c}\n\n\n\n\n\n\n\n\n\n\n\n\n3\n3\n3\n\n4\n\n\n\n\end{array}$$ and we compute $\text{Det}\left(\Gamma \right)<0,$ giving a contradiction. $\square $ |

Step XI. Suppose $\Gamma \in {\mathcal{C}}^{+}$ is connected and contains a branch point $a\text{.}$ Then $\Gamma $ is one of ${D}_{\ell},$ ${E}_{6},$ ${E}_{7},$ ${E}_{8}\text{.}$

Proof. | |

Step X together with the fact that ${\stackrel{\sim}{D}}_{4}$ has determinant zero imply that $\text{Deg}\left(a\right)=3$ and that the subgraph of $\Gamma $ formed by $a$ and the three vertices to which $a$ is joined is ${D}_{4}\text{.}$ Further all edges of $\Gamma $ are unlabelled; otherwise some ${\stackrel{\sim}{B}}_{\ell}^{p}$ 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] $\Gamma $ is ${D}_{\ell},$ ${E}_{6},$ ${E}_{7},$ or ${E}_{8}\text{.}$ $\square $ |

Step XII. Let $\ell \ge 5$ and suppose $\Gamma \in {\mathcal{C}}_{\ell}^{\circ}$ is connected and contains a branch point $a\text{.}$ Then $\Gamma $ is one of ${\stackrel{\sim}{D}}_{\ell -1},$ ${\stackrel{\sim}{B}}_{\ell -1}^{p},$ ${\stackrel{\sim}{E}}_{6},$ ${\stackrel{\sim}{E}}_{7},$ ${\stackrel{\sim}{E}}_{8}\text{.}$

Proof. | |

If $\text{Deg}\left(a\right)\ne 3,$ Step X forces $\Gamma $ to contain ${\stackrel{\sim}{D}}_{4}$ as a subgraph and hence $\Gamma ={\stackrel{\sim}{D}}_{4}\text{.}$ So we assume $\text{Deg}\left(a\right)=3\text{.}$ Then again by Step X the subgraph of $\Gamma $ formed by $a$ and the three vertices to which $a$ is joined is ${D}_{4}\text{.}$ Now if some edge is labelled with $a$ number larger than 3 then $\Gamma $ would have some ${\stackrel{\sim}{B}}_{k}^{p}$ as a subgraph and hence $\Gamma ={\stackrel{\sim}{B}}_{\ell -1}^{p}\text{.}$ Thus we can assume all edges are unlabelled. Hence all vertices are unlabelled also. Now if $\Gamma $ contains another branch point distinct from $a,$ then $\Gamma $ would contain some ${\stackrel{\sim}{D}}_{k}$ as a subgraph and hence $\Gamma ={\stackrel{\sim}{D}}_{\ell -1}\text{.}$ Thus we can assume that $a$ is the unique branch point of $\Gamma \text{.}$ It follows that $\Gamma $ is ${\stackrel{\sim}{E}}_{6},$ ${\stackrel{\sim}{E}}_{7},$ or ${\stackrel{\sim}{E}}_{8}$ for the only other graphs which have a unique branch point of degree 3 and have all vertices and edges unlabelled are either ${D}_{k},$ ${E}_{6},$ ${E}_{7},$ ${E}_{8}$ (all of which are positive definite) or graphs which contain ${\stackrel{\sim}{E}}_{6},$ ${\stackrel{\sim}{E}}_{7},$ or ${\stackrel{\sim}{E}}_{8}$ as proper subgraphs. We remark that by inspection one easily verifies that each of ${\stackrel{\sim}{D}}_{\ell -1},$ ${\stackrel{\sim}{B}}_{\ell -1}^{p},$ ${\stackrel{\sim}{E}}_{6},$ ${\stackrel{\sim}{E}}_{7},$ ${\stackrel{\sim}{E}}_{8}$ has the property that all of its proper subgraphs are positive definite and hence these graphs are elements of ${\mathcal{C}}^{\circ}\text{.}$ $\square $ |

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

Let $\Gamma \in \mathcal{C}$ be a connected graph. Recalling Proposition 6 we see that if $W\left(\Gamma \right)$ is finite then $\Gamma $ 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 $\Gamma \in \mathcal{C}$ be connected. Then the following statements
are equivalent.

(a) | $W\left(\Gamma \right)$ is finite. |

(b) | $\Gamma $ is positive definite. |

(c) | $\Gamma $ occurs in List 1. |

As mentioned before, if $\Gamma \in {\mathcal{C}}_{\ell}$ with ${p}_{i}=2,$ $1\le i\le \ell ,$ then the representation $\theta $ given by Theorem 1 for the Coxeter group $W\left(\Gamma \right)$ is the same representation as that given in [Bou1968]. Thus, by [Bou1968, p.93], for such $\Gamma ,$ $\theta $ is a faithful representation of $W\left(\Gamma \right)\text{.}$ Now our representation $\theta $ fails to be faithful in general but we can prove the following.

**Corollary 5.** Let $\Gamma \in {\mathcal{C}}_{\ell}$ be connected. If
$W=W\left(\Gamma \right)$ is finite, then
$\theta $ is a faithful representation of $W\text{.}$

Proof. | |

By the remarks preceding the corollary we can assume that not all ${p}_{i},$ $1\le i\le \ell ,$ are 2. Now since $W$ is finite, $\Gamma $ appears in List 1. But a glance at List 1 reveals the fact that since not all ${p}_{i}$ are $2,$ $\Gamma $ must be linear. As remarked before, for such $I,$ Coxeter [Cox1967] gives a representation of $W$ which is the representation $\rho $ of Proposition 3. But according to [Cox1967] this representation is a faithful representation of $W\text{.}$ Now since $W$ is finite the form $H\left(\Gamma \right)$ is positive definite so in particular it is non degenerate and thus Corollary 2 yields that $\rho $ and $\theta $ are equivalent representations of $W$ and hence $\theta $ is also a faithful representation of $W\text{.}$ $\square $ |

The fact that $\theta $ is not in general faithful is illustrated in the following example. Let $\Gamma $ denote the graph $3\left[6\right]3$ in ${\mathcal{C}}_{2}^{\circ}\text{.}$ The representation $\theta $ of $W\left(\Gamma \right)$ is given by $$\theta \left({r}_{1}\right)={S}_{1}=\left(\begin{array}{cc}\omega & 1-\omega \\ 0& 1\end{array}\right)\phantom{\rule{2em}{0ex}}\theta \left({r}_{2}\right)={S}_{2}=\left(\begin{array}{cc}1& 0\\ 1-\omega & \omega \end{array}\right)$$ where $\omega ={e}^{2\pi i/3}\text{.}$ One easily sees that ${S}_{1}{S}_{2}$ has order 3. However, putting $${\stackrel{\sim}{S}}_{1}=\left(\begin{array}{ccc}\omega & 1-\omega & x\\ 0& 1& 0\\ 0& 0& 1\end{array}\right)\phantom{\rule{2em}{0ex}}{\stackrel{\sim}{S}}_{2}=\left(\begin{array}{ccc}1& 0& 0\\ 1-\omega & \omega & y\\ 0& 0& 1\end{array}\right)$$ where $x,y\in \u2102$ are to be chosen later we see that ${\stackrel{\sim}{S}}_{1}^{3}={\stackrel{\sim}{S}}_{2}^{3}=I$ and $${\left({\stackrel{\sim}{S}}_{1}{\stackrel{\sim}{S}}_{2}\right)}^{3}={\left({\stackrel{\sim}{S}}_{2}{\stackrel{\sim}{S}}_{1}\right)}^{3}=\left(\begin{array}{ccc}1& 0& 3\omega (y-x)\\ 0& 1& 3\omega (x-y)\\ 0& 0& 1\end{array}\right)\text{.}$$ Thus if $x\ne y,$ ${\stackrel{\sim}{S}}_{1}{\stackrel{\sim}{S}}_{2}$ has infinite order and so does ${r}_{1}{r}_{2}\text{.}$ 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\left(\Gamma \right)$ associated with connected graphs $\Gamma \in {\mathcal{C}}_{2}^{\circ}$ we have ${r}_{1}{r}_{2}$ has infinite order but $\theta \left({r}_{1}{r}_{2}\right)={S}_{1}{S}_{2}$ has finite order.

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.