Integral positive definite quadratic forms and graphs

Question

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$. (https://en.wikipedia.org/wiki/Root_system)

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 the helpful Gjergji's answer.)

(1) Consider the set $R$ of shortest vectors in $\mathbb Z^n$; they have square 2. Reflections in elements $r\in R$ send $R$ to itself, and $R$ spans $\mathbb Z^n$ since it contains the standard basis vectors $e_i$. 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.

Hence, the question equivalent to the following: what are the graphs corresponding to all possible bases of $\mathbb R^n$ in which the basis vectors are roots?

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 an oriented 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$, similarly, a basis is described by an auxiliary connected graph $S$ on $n$ vertices with $n$ edges whose ends are labeled $+$ or $-$. The graph $G$ is computed from $S$.

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 algebra theory (see for example the first pages of LNM 1099 (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.

Answer 1

I have studied a closely related problem (but never published the results and my notes are messy). Consider a set $\mathcal S$ of roots in a simply laced root system. Associate to $\mathcal S$ the graph with edges given by pairs of distinct, non-opposite roots which are not orthogonal. (In other terms, forget the colouring of the edges in your graph.)

Up to 8 vertices you get all graphs in this way. For more than 8 vertices, there are graphs which are not of this form. (There are some necessary conditions related to the Arf invariant of an associated quadratic form over $\mathbb F_2$. One works of course only with connected components.)

The trick, if I remember correctly, is to work modulo $2$ and to show that in certain situations, one can "lift" a solution into (projective) subsets of roots.

More precisely, one can define invertible combinatorial moves (chirurgies) on graphs which come from transformations on subsets contained in root systems (and which amount to convections in symplectic spaces over $\mathbb F_2$).

For at most eight vertices, one can then look at the equivalence classes of such moves and show that each equivalence class contains a member realizable by a suitable subset of roots (in a uniquely defined minimal simply laced root-system). In particular, every graph with at most $8$ vertices has a a certain "root-type".

Answer 2

In Cluster algebras of finite type and positive symmetrizable matrices by Barot, Geiss and Zelevinsky (J. London Math. Soc. (2) 73 (2006), no. 3, 545--564, doi:10.1112/S0024610706022769, arXiv:math/0411341) we can see that positive definite quasi-Cartan matrices (defined the same as Cartan matrices but relaxing the condition of non-positivity of elements off the diagonal) actually come from positive definite Cartan matrices. That is, each positive definite quasi-Cartan matrix is equivalent to a positive definite Cartan matrix, where equivalence in the symmetric case is defined as $A\sim B$ if there is a matrix $E$ with determinant $\pm 1$ so that $A=E^TBE$. This is proved in proposition 2.9.

This means that the graphs you are looking for are classified up to the equivalence relation above. Since a such a matrix $E$ as above can be constructed easily for the case of trees for example this means that all trees that answer your question are also ADE.

A classification result that includes the trees example above is given in "Sincere weakly positive unit quadratic forms" by M.V. Zeldich (Canadian Mathematical Society, Conference proceedings, Vol 14, 1993) and again, this classification contains graphs that are obtained from ADE by some modifications, and the resulting graphs are described with 2-colored edges.