18
$\begingroup$

Let $J_k$ be a $k \times k$ all ones matrix and $B$ any $k \times k$ binary matrix - that is $B$ only has entries from $\{0,1\}$.

I would like to show that the matrix $$X_B = (J_k -I) - B (J_k - I)^{-1} B^T\,,$$ is not positive-definite. In other words, I'd like to show that

At least one eigenvalue of $X_B$ is non-positive.

I can show that for certain specific matrices $B$ but don't see how to prove the more general statement. Does anybody know why this property seem to hold in general?

Improve this question
$\endgroup$
5
  • 1
    $\begingroup$ One should easily be able to test this by computer brute force up to $k=4$ or $k=5$ - have you done so? $\endgroup$
    – Nate Eldredge
    Commented Sep 28, 2016 at 20:02
  • 2
    $\begingroup$ @NateEldredge Actually I did, yes. Assuming I didn't messed up the computation I've checked the claim for $k=6$ as well. $\endgroup$
    – Jernej
    Commented Sep 28, 2016 at 20:11
  • 4
    $\begingroup$ For those who, like me, do not like inverse matrices in the formulae, $(J_k-I)^{-1}=\frac{1}{k-1}J_k-I$. $\endgroup$
    – fedja
    Commented Sep 28, 2016 at 22:21
  • $\begingroup$ Another helpful formula: If $\vec{b_i}$ is the $i$-th row of $B$, and $n_i=\vec{b_i}\cdot\vec{b_i}$, then $X_{ij} = 1- \frac{n_i\,n_j}{k-1} - \delta_{ij}+\vec{b_i}\cdot\vec{b_j}$. This gives the trace as $\sum \limits_{i=1}^k \left(1-\frac{n_i}{k-1}\right)\,n_i$. It looks like the largest eigenvalue is typically larger than the trace, but no proof so far. $\endgroup$
    – Karl Fabian
    Commented Sep 28, 2016 at 22:44
  • 2
    $\begingroup$ Maybe "$X_M$" should be $X_B$? (Not that this helps answer the question . . .) $\endgroup$
    – Noam D. Elkies
    Commented Sep 28, 2016 at 23:59

1 Answer 1

Reset to default
17
$\begingroup$

Counterexample: let $k=7$, and let $B$ be the circulant matrix with $B_{ij}=1$ iff $i-j \in \{1,2,4\} \bmod 7$. Then $X_B$ is $I + \frac12 J$, with characteristic polynomial $(x-1)^6 (x-\frac92)$. Or use $B+I$ instead to get $I + \frac13 J$, with characteristic polynomial $(x-1)^6 (x-\frac{10}{3})$.

Improve this answer
$\endgroup$
1
  • 5
    $\begingroup$ Likewise for $k=11$, $k=19$, and presumably an exercise to prove it for all larger prime powers congruent to $3 \bmod 4$ (though not $3$ itself). $\endgroup$
    – Noam D. Elkies
    Commented Sep 29, 2016 at 0:35

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .