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?

$\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$ 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
    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
    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$ Sep 28, 2016 at 22:44
  • 2
    $\begingroup$ Maybe "$X_M$" should be $X_B$? (Not that this helps answer the question . . .) $\endgroup$ Sep 28, 2016 at 23:59

1 Answer 1

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})$.

$\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$ Sep 29, 2016 at 0:35

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.