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

Your Answer

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

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