Skip to main content
1 of 6
VA.
  • 13.1k
  • 2
  • 50
  • 63

Integral positive definite quadratic forms

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).

Question 2: Which of these graphs correspond to positive definite $A$?

I am reasonably confident that I can work this out myself, given time. But this looks like something that should have been known in the 19th century, if not before. Anybody knows the answer right away?

VA.
  • 13.1k
  • 2
  • 50
  • 63