Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. Join them; it only takes a minute:

Sign up
Here's how it works:
  1. Anybody can ask a question
  2. Anybody can answer
  3. The best answers are voted up and rise to the top

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?

share|cite|improve this question
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

Your Answer


By posting your answer, you agree to the privacy policy and terms of service.

Browse other questions tagged or ask your own question.