# Showing that a certain matrix is not positive definite

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?

• One should easily be able to test this by computer brute force up to $k=4$ or $k=5$ - have you done so? – Nate Eldredge Sep 28 '16 at 20:02
• @NateEldredge Actually I did, yes. Assuming I didn't messed up the computation I've checked the claim for $k=6$ as well. – Jernej Sep 28 '16 at 20:11
• For those who, like me, do not like inverse matrices in the formulae, $(J_k-I)^{-1}=\frac{1}{k-1}J_k-I$. – fedja Sep 28 '16 at 22:21
• 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. – Karl Fabian Sep 28 '16 at 22:44
• Maybe "$X_M$" should be $X_B$? (Not that this helps answer the question . . .) – 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})$.
• 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). – Noam D. Elkies Sep 29 '16 at 0:35