Skip to main content
2 of 6
edited tags; edited title; deleted 198 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$?

VA.
  • 13.1k
  • 2
  • 50
  • 63