Enumeration of the connected positive semidefinite corank-one diagrams

Let $n=\mathrm{\mid }S\mathrm{\mid }$. If $n=0$, the diagram is not connected, and if $n=1$ its cosine matrix is $[1]$, so it is positive definite rather than corank one [F1]. For $n=2$, connectedness gives one edge labelled $m\ge 3$ or $m=\mathrm{\infty }$: if $m<\mathrm{\infty }$, then $0<\cos (\pi \mathrm{/}m)<1$ because $0<\pi \mathrm{/}m\le \pi \mathrm{/}3<\pi \mathrm{/}2$, $\cos (\pi \mathrm{/}2)=0$, $\cos 0=1$ by its power series, and cosine is strictly decreasing; hence the leading minors $1$ and $1-{\cos }^2(\pi \mathrm{/}m)$ are positive, so Sylvester's criterion makes the matrix positive definite [F9,F12,F27,F29]. If $m=\mathrm{\infty }$, the matrix is $\left(\begin{array}{cc}1& -1\\ -1& 1\end{array}\right)$, the standard ${\tilde{A}}_1$. Hence assume $n\ge 3$.

The cosine values needed below are $\cos (\pi \mathrm{/}3)=1\mathrm{/}2$, $\cos (\pi \mathrm{/}4)=\sqrt{2}\mathrm{/}2$, $\cos (\pi \mathrm{/}6)=\sqrt{3}\mathrm{/}2$, and $c_5^2:={\cos }^2(\pi \mathrm{/}5)=(3+\sqrt{5})\mathrm{/}8$. For the first, if $c=\cos (\pi \mathrm{/}3)$ then $2c^2-1=\cos (2\pi \mathrm{/}3)=-c$, so $(2c-1)(c+1)=0$; strict decrease of cosine and $\pi \mathrm{/}3<\pi$ give $c>-1$, hence $c=1\mathrm{/}2$. The other two follow from ${\cos }^{2}x=(1+\cos 2x)\mathrm{/}2$, $\cos (\pi \mathrm{/}2)=0$, positivity on $(0,\pi \mathrm{/}2)$, and the nonnegative square root [F16]. For $c_5=\cos (\pi \mathrm{/}5)$, put $\zeta =e^{2\pi i\mathrm{/}5}$. The five distinct fifth roots of unity include $1$ and $\zeta \mathrm{\ne }1$, and since ${\zeta }^5=1$ the geometric-series identity gives $1+\zeta +{\zeta }^2+{\zeta }^3+{\zeta }^4=0$. Set $y=\zeta +{\zeta }^{-1}$; dividing by ${\zeta }^2$ and using $y^2={\zeta }^2+2+{\zeta }^{-2}$ gives $y^2+y-1=0$. Since ${\zeta }^4={\zeta }^{-1}$, Euler's formula and the even/odd parity of cosine and sine give $y=2\cos (2\pi \mathrm{/}5)>0$; positivity follows from $0<2\pi \mathrm{/}5<\pi \mathrm{/}2$ and strict decrease to $\cos (\pi \mathrm{/}2)=0$. Thus $(2y+1{)}^2=5$ and $2y+1>0$, so uniqueness of the nonnegative square root [F16] gives $y=(\sqrt{5}-1)\mathrm{/}2$. The double-angle identity then gives $c_5^2=(1+\cos (2\pi \mathrm{/}5))\mathrm{/}2=(3+\sqrt{5})\mathrm{/}8$.

Suppose the underlying graph contains a cycle on a vertex set $T$, with $r\ge 3$ vertices. On $T$ put the all-$3$ cycle $\mathrm{\Delta }={\tilde{A}}_{r-1}$ and let $u$ be the sum of its $r$ basis vectors. Its quadratic value is $r-2r(1\mathrm{/}2)=0$, so its cosine matrix is not positive definite. The induced graph ${\mathrm{\Gamma }}_T$ contains $\mathrm{\Delta }$ and has labels at least those of $\mathrm{\Delta }$; if it strictly dominates $\mathrm{\Delta }$, the full affine diagram $\mathrm{\Gamma }$ also strictly dominates $\mathrm{\Delta }$ on $T$, so [F14] would make $\mathrm{\Delta }$ positive definite, a contradiction. If ${\mathrm{\Gamma }}_T=\mathrm{\Delta }$ but $T⊊S$, its principal matrix is not positive definite, again contradicting [F2]. Therefore $T=S$ and $\mathrm{\Gamma }=\mathrm{\Delta }$, which is a listed all-$3$ cycle.

If an edge has label $\mathrm{\infty }$, its two-vertex principal matrix is $\left(\begin{array}{cc}1& -1\\ -1& 1\end{array}\right)$, which is not positive definite because $(1,1)$ has quadratic value $0$. Since this is a proper principal submatrix when $n\ge 3$, it contradicts [F2]; thus no edge has label $\mathrm{\infty }$.

Suppose two distinct edges have labels at least $4$. Since the graph is acyclic by Step 1.3, the minimal connected subdiagram containing these edges is a path whose first and last edges have label at least $4$. Replace those two labels by $4$ and every internal edge by $3$; the resulting diagram is ${\tilde{C}}_k$ for some $k\ge 2$ by [F19], and is not positive definite by [F4]. If it is a strict subdiagram or any retained label is larger, [F14] would make it positive definite. If it is the whole diagram with equal labels, $\mathrm{\Gamma }={\tilde{C}}_k$. Hence the only possibility with two or more such edges is exactly a ${\tilde{C}}_k$ diagram; in particular there cannot be three such edges.

For a path with edge labels $m_1,\dots ,m_{k-1}$, let $d_k$ be the determinant of its leading $k\times k$ cosine matrix and put $d_0=d_1=1$. The last row has only the entries $-c$ and $1$, where $c=\cos (\pi \mathrm{/}{m}_{k-1})$; the diagonal cofactor is $d_{k-1}$, while the minor for the $-c$ entry is $-c{d}_{k-2}$ and its cofactor sign is $(-1{)}^{k+(k-1)}=-1$, so that cofactor is $c{d}_{k-2}$. The expansion from [F10] therefore gives $d_k=d_{k-1}-c^2{d}_{k-2}$. This is also the recurrence in the positive-definite path result F8(i). When every label is $3$, Step 1.2 gives $c=1\mathrm{/}2$, and induction yields $d_k=(k+1)\mathrm{/}{2}^k>0$. Thus an all-$3$ path is positive definite by [F9] and cannot have corank one.

For later use, suppose a path has exactly one edge labelled $m\ge 4$. Let that edge split the path into $i\le j$ vertices, both at least $1$, and put $c=\cos (\pi \mathrm{/}m)$. Weight the vertices on the two sides from their remote ends toward the large edge by $1,2,\dots ,i$ and $1,2,\dots ,j$, giving nonzero vectors $u,v$. Expanding along the all-$3$ parts gives $B(u,u)={\sum }_{h=1}^i{h}^2-{\sum }_{h=1}^{i-1}h(h+1)=i(i+1)\mathrm{/}2$, $B(v,v)=j(j+1)\mathrm{/}2$, and the only cross term is $B(u,v)=-ijc$. Since $B$ is positive semidefinite, $B(tu+v,tu+v)\ge 0$ for every real $t$; choosing $t=-B(u,v)\mathrm{/}B(u,u)$ yields $B(u,v{)}^2\le B(u,u)B(v,v)$ and hence $(i+1)(j+1)\ge 4ij{c}^2$. The strict inequality in F23(ii) assumes positive definiteness and cannot be used for the present semidefinite form; the derived non-strict inequality includes the affine equality cases.

Suppose exactly one edge has label at least $4$ and $\mathrm{\Gamma }$ has a vertex of degree at least $3$. A vertex of degree at least $4$, together with four of its neighbours, gives a subdiagram dominating ${\tilde{D}}_4$; two distinct degree-$3$ vertices, the path between them, and two additional neighbours at each end give a subdiagram dominating some ${\tilde{D}}_k$. These are standard affine diagrams and are not positive definite by [F20,F4]. A strict domination contradicts [F14]; an equal proper subdiagram contradicts [F2]. Equality on all vertices would make $\mathrm{\Gamma }$ a $\tilde{D}$ diagram with all labels $3$, contrary to the assumed large edge. Thus there is exactly one degree-$3$ vertex $v$. The unique large edge lies on one of its three arms. Retain the path from $v$ through that edge to its endpoint farther from $v$, and retain just the first edge on each of the other two arms. Lower the retained large label to $4$ (and all other retained edges already have label $3$). The resulting comparison diagram is ${\tilde{B}}_k$ with its terminal label $4$; it is not positive definite by [F4]. The same strict-domination and proper-principal arguments force it to be all of $\mathrm{\Gamma }$ with the large label exactly $4$. Therefore the branched case is precisely ${\tilde{B}}_k$. If there is no vertex of degree at least $3$, the connected acyclic graph is a path.

For an all-$3$ star with arms of $p,q,r$ vertices, each arm block is the positive definite all-$3$ path matrix $A_j$ from Step 2.3. Solving $A_{j}z=e_1$ gives $z_h=2(j+1-h)\mathrm{/}(j+1)$: the entries form an arithmetic progression, satisfy the endpoint and interior tridiagonal equations, and the solution is unique since $A_j$ is positive definite. Thus $(A_j^{-1}{)}_{11}=2j\mathrm{/}(j+1)$. If $x$ is the central coordinate and $y_a$ are the arm vectors, the quadratic form is $x^2+{\sum }_a(y_a^{\mathsf{T}}{A}_{j_a}{y}_a-x{e}_1^{\mathsf{T}}{y}_a)$. For each arm, $y_a^{\mathsf{T}}{A}_{j_a}{y}_a-x{e}_1^{\mathsf{T}}{y}_a=(y_a-\frac{x}{2}{A}_{j_a}^{-1}{e}_1{)}^{\mathsf{T}}{A}_{j_a}(y_a-\frac{x}{2}{A}_{j_a}^{-1}{e}_1)-\frac{x^2}{4}{e}_1^{\mathsf{T}}{A}_{j_a}^{-1}{e}_1$. Thus the remaining central coefficient is $1-\frac{p}{2(p+1)}-\frac{q}{2(q+1)}-\frac{r}{2(r+1)}=\frac{1}{2}(\frac{1}{p+1}+\frac{1}{q+1}+\frac{1}{r+1}-1)$. Hence the star is positive definite when that reciprocal sum exceeds $1$. In particular the finite stars $(1,1,r)$ for $r\ge 1$ and $(1,2,2),(1,2,3),(1,2,4)$ have positive definite forms, with central coefficients respectively $1\mathrm{/}(2(r+1)),1\mathrm{/}12,1\mathrm{/}24,1\mathrm{/}60$. By [F6] they are finite Coxeter systems, and F7,(3) identifies these as the finite $D$ and $E$ diagrams. The same reciprocal sum is the necessary three-arm bound supplied for positive definite diagrams by [F24].

The integer cases from Step 2.4 are as follows. If $m=4$, then $(i-1)(j-1)\le 2$, so $i=1$ with arbitrary $j$, or $(i,j)=(2,2)$ or $(2,3)$; the first paths are finite $B$ diagrams, $(2,2)$ is finite $F_4$, and $(2,3)$ is ${\tilde{F}}_4$ up to reversal. If $m=5$, then $4c^2=(3+\sqrt{5})\mathrm{/}2>9\mathrm{/}4$ because $2\sqrt{5}>3$ (indeed $\sqrt{5}>2$ by [F16,F17]); if $i\ge 2$, then $j\ge i$ and $(i+1)(j+1)\mathrm{/}(ij)=(1+1\mathrm{/}i)(1+1\mathrm{/}j)\le 9\mathrm{/}4$, contradicting Step 2.4. Thus $i=1$, and $2(j+1)\ge 4c^{2}j$ forces $j\le 4\mathrm{/}(\sqrt{5}-1)=\sqrt{5}+1<4$ since $\sqrt{5}<3$ by [F16,F17]; the formal cases $j=1,2,3$ are $I_2(5)$, $H_3$, and $H_4$, with $j=1$ already treated in rank $2$. If $m\ge 6$, then $4c^2\ge 3$; the same ratio bound excludes $i\ge 2$, so $i=1$, and $2(j+1)\ge 3j$ gives $j\le 2$. For $j=1$ rank $2$ was treated in Step 1.1, while $j=2$ requires $m=6$ (for $m>6$, strict monotonicity gives $4c^2>3$) and gives the path ${\tilde{G}}_2=(3,6)$. For completeness, the finite path claims just used follow from Step 2.3 and Sylvester: a terminal $4$-edge has final determinant $2^{-j}$ after an all-$3$ prefix, the $(3,4,3)$ path has leading determinants $1,3\mathrm{/}4,1\mathrm{/}4,1\mathrm{/}16$, and the $(5,3)$ and $(5,3,3)$ paths have leading determinants $1,(5-\sqrt{5})\mathrm{/}8,(3-\sqrt{5})\mathrm{/}8$ and $1,(5-\sqrt{5})\mathrm{/}8,(3-\sqrt{5})\mathrm{/}8,(7-3\sqrt{5})\mathrm{/}32$, respectively. The roots obey $2<\sqrt{5}<3$ by [F16,F17], and $3\sqrt{5}<7$ since both sides are positive and their squares satisfy $45<49$; hence all these determinants are positive. Thus the finite cases are positive definite by [F9], their groups are finite by [F6], and the finite classification [F7] gives their names; the equality paths are exactly the listed affine diagrams.

Now suppose there is no edge labelled at least $4$, so every edge has label $3$, and the tree has a vertex of degree at least $3$. A degree-$4$ vertex produces ${\tilde{D}}_4$ as in Step 3.1; if there are two degree-$3$ vertices, the same construction there produces a ${\tilde{D}}_k$ subdiagram. The subdiagram has the exact standard $\tilde{D}$ labels, is not positive definite by [F4], and therefore cannot be a proper principal submatrix by [F2]; it must be all of $\mathrm{\Gamma }$. If there is one degree-$3$ vertex, let $1\le p\le q\le r$ be the numbers of vertices on its arms. When $r\ge 2$, deleting a terminal vertex of the longest arm leaves a proper connected positive definite subdiagram by [F2]; applying the three-arm inequality [F24] to that subdiagram gives $\frac{1}{p+1}+\frac{1}{q+1}+\frac{1}{r}>1$. If $r=1$, the arms are $(1,1,1)$ and Step 3.2 shows the star is finite $D_4$ and positive definite, so it cannot be affine.

The integer solutions to the inequality in Step 4.1, with $p\le q\le r$, are $(1,1,r)$ for $r\ge 2$, $(1,2,r)$ for $2\le r\le 5$, $(1,3,3)$, and $(2,2,2)$. Indeed, $p\ge 3$ makes the sum at most $1\mathrm{/}4+1\mathrm{/}4+1\mathrm{/}3<1$. If $p=2$ and $q\ge 3$, the sum is at most $1\mathrm{/}3+1\mathrm{/}4+1\mathrm{/}3<1$, so $q=2$ and then $1\mathrm{/}3+1\mathrm{/}3+1\mathrm{/}r>1$ forces $r=2$. If $p=1$ and $q\ge 4$, the sum is at most $1\mathrm{/}2+1\mathrm{/}5+1\mathrm{/}4<1$, so $q\le 3$; with $q=2$ the inequality gives $r\le 5$, with $q=3$ it gives $r=3$, and $q=1$ allows every $r\ge 2$. The $(1,1,r)$ stars and $(1,2,2),(1,2,3),(1,2,4)$ are the positive definite finite stars of Step 3.2 and so are excluded. The remaining cases $(2,2,2)$, $(1,3,3)$, and $(1,2,5)$ are precisely ${\tilde{E}}_6,{\tilde{E}}_7,{\tilde{E}}_8$ by [F21], as required.

The cases above exhaust connected affine form type diagrams: rank at most $2$ gives only ${\tilde{A}}_1$; in rank at least $3$, Step 1.3 gives the all-$3$ cycle case or a tree, Step 2.2 handles two or more labels at least $4$, Step 3.1 handles a single large label with a branch, Step 2.3 excludes an all-$3$ path, Steps 4.1-5.1 handle the remaining all-$3$ trees, and Steps 2.4-3.3 handle the remaining paths. Reading the resulting graph shapes against [F3,F18,F19,F20,F21,F22] gives exactly the list in the statement. Its families have no infinite labels above rank $2$, all finite labels among $3,4,6$, and at most two edges labelled at least $4$; the cyclic case is exactly ${\tilde{A}}_n$ ($n\ge 2$). The low-rank aliases in the statement follow from [F15]. All witnesses and constructions use finitely many vertices and explicit formulas, so no Choice is used.