2
$\begingroup$

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?

  • 0
    I guess you want $x^tAx>0$ for $x\neq 0$.2012-09-12
  • 0
    Yes, you are right. Sorry. I fixed it now.2012-09-12
  • 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).2012-09-12
  • 0
    So you say any positive definite relation is reflexive and antisymmetric? Why is that true?2012-09-12
  • 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)$2012-09-12
  • 0
    The condition is not sufficient, though, since e.g. $$\pmatrix{1 & 0 & 1 & 1\cr 0 & 1 & 1 & 1\cr 0 & 0 & 1 & 0\cr 0 & 0 & 0 & 1\cr}$$ is not positive definite.2012-09-12
  • 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\}$.2012-09-12
  • 0
    How about positive semi-definite relations? Is there any reflexive, transitive, and nonsymmetric relation, which is PSD?2012-09-19

0 Answers 0