# positive definite binary matrix

What are the conditions for a binary matrix $A$ (matrix with elements 0 or 1) to be positive definite (not even symmetric), i.e.

$\forall x\neq 0, x^TAx>0, A_{ij}\in \{0,1 \}$

Put it another way, what adjacency matrices are positive definite?

-
I guess you want $x^tAx>0$ for $x\neq 0$. – Davide Giraudo Sep 12 '12 at 21:15
Yes, you are right. Sorry. I fixed it now. – user25004 Sep 12 '12 at 21:16
We have $A_{ii}=1$ and for $i\neq j$, we should have $A_{ij}=0$ or $A_{ji}=0$ (that only necessary conditions). – Davide Giraudo Sep 12 '12 at 21:21
$A_{ii} = e_i^T A e_i$ where $e_i$ is the $i$'th standard unit vector, and $A_{ii} + A_{jj} - A_{ij} - A_{ji} = (e_i - e_j)^T A (e_i - e_j)$ – Robert Israel Sep 12 '12 at 22:15
Another necessary condition is that for any disjoint subsets $S$ and $T$ of $\{1,\ldots,n\}$ (where your matrix is $n \times n$), there are more ordered pairs $(i,j)$ where $A_{ij}=1$ with $i$ and $j$ both in $S$ or both in $T$ than there are with one in $S$ and the other in $T$. For example, this is violated in my example above with $S = \{1,2\}$ and $T = \{3,4\}$. – Robert Israel Sep 12 '12 at 23:07