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?

  • 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 '16 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 '16 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 '16 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 '16 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 '16 at 23:59

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

  • 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 '16 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.