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

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

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