Take the 2-minute tour ×
Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. It's 100% free, no registration required.

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|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
1  
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
2  
$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
2  
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
show 3 more comments

Your Answer

 
discard

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

Browse other questions tagged or ask your own question.