Skip to main content
3 of 6
added 1850 characters in body
VA.
  • 13.1k
  • 2
  • 50
  • 63

Integral positive definite quadratic forms and graphs

Let me start with a question for which I know the answer. Consider a symmetric integral $n\times n$ matrix $A=(a_{ij})$ such that $a_{ii}=2$, and for $i\ne j$ one has $a_{ij}=0$ or $-1$. One can encode such a matrix by a graph $G$: it has $n$ vertices, and two vertices $i,j$ are connected by an edge iff $a_{ij}=-1$.

Question 1: Which graphs correspond to positive definite $A$?

Answer 1: (Classical, well-known, and easy) $G$ is a disjoint union of $A_n$, $D_n$, $E_n$.

Now let me put a little twist to this. Let us also allow $a_{ij}=+1$ for $i\ne j$, and encode this by putting a broken edge between $i$ and $j$ (or an edge of different color, if you prefer).

Real question: Which of these graphs correspond to positive definite $A$?


Let me add some partial considerations which do not quite go far enough. (Some of these were in Gjergji's answer, which I appreciated, which he unfortunately removed.)

(1) Clearly, the standard basis vectors $e_i$ are roots (they have square 2), and generate the lattice $\mathbb Z^n$. By the standard result about root lattices, $\mathbb Z^n$ is then a direct sum of the $A_n$, $D_n$, $E_n$ root lattices, and one can restrict to the case of a single direct summand.

Then $e_i$'s are some of the roots in $R$, and we ask: what are the collections of such roots spanning the vector space, and with the property that the pairwise dot products $(e_i,e_j)$ are 0,-1,+1.

The case of $R=A_n$ is relatively easy. The roots are of the form $f_a-f_b$, with $a,b \in (1,\dots,n+1)$. Every collection $e_i$ corresponds to a spanning tree on the set $(1,\dots,n+1)$. The 2-colored graph is computed from that tree. I don't see a clean description of the graphs obtained via this procedure, but it is something.

For $D_n$, the procedure may be similar but messier. And for $E_6,E_7,E_8$ there are of course only finitely many cases, but for me the emphasis is on MANY, very many.

So has anybody done this? Is there a table in some paper or book which contains all the 2-colored graphs obtained this way, or -- better still -- a clean characterization of such graphs?

(2) There is a notion of "weakly positive quadratic forms" used in the cluster theory (see for example the first pages of LMN1099 (Tame Algebras and Integral Quadratic Forms) by Ringel. And there is some kind of classification theory for them. Maybe I am mistaken, but this seems to be quite different: a quadratic form $q$ is "weakly positive" if $q\ge 0$ on the first quadrant $\mathbb Z_{\ge0}^n$. So there is no direct relation to my question, it seems.

VA.
  • 13.1k
  • 2
  • 50
  • 63