Return to 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$. (http://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.

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.

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

(1) Consider the set $R$ 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.

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$. (http://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.

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.

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

(1) Consider the set $R$ 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.