3
$\begingroup$

Let $S$ be an $n\times n$ symmetric matrix whose diagonal consists only of $1$s and whose other entries are either $0$ or $1$ .

If the determinant and rank of $S$ are known, what can be said about the number of zero entries in $S$ ?

$\endgroup$
1
$\begingroup$

I'm thinking, not a lot.

Suppose $S$ is $10\times10$ with determinant zero and rank 5. $S$ could have a $6\times6$ matrix of all-ones in the upper left corner, no other ones except the 4 on the diagonal, for 40 ones and 60 zeros.

Or, it could have $2\times2$ squares of ones down the diagonal, zero everywhere else, 20 ones and 80 zeros.

Rank 3, you could have a zero in the upper right corner and one in the lower left, or three blocks of ones on the diagonal, so anywhere from 2 zeros to $100-16-9-9=66$ zeros.

Seems like there's a lot of wiggle room.

EDIT: Similar example with nonzero determinant: if $n$ is even, then the matrix that is all ones except for having zeros down the "other" diagonal has determinant $n-1$. So for example the $4\times4$ has 12 ones, 4 zeros, and determinant 3; the $28\times28$ has 756 ones, 28 zeros, and determinant 27. Now make a $28\times28$ matrix that has three of the $4\times4$ matrices along the diagonal, ones down the rest of the diagonal, zeros everywhere else. It also has determinant 27, but only 52 ones, and 732 zeros.

$\endgroup$
  • $\begingroup$ Thanks Gerry. Is the situation similarly hopeless when the determinant is nonzero? $\endgroup$ – Nasos Evangelou-Oost Oct 19 '12 at 3:26
  • 1
    $\begingroup$ I don't know for certain, but that would be my expectation. There are a lot of nonsingular symmetric zero-one matrices with ones down the diagonal, and I expect most of them have a pretty small determinant, so you should be able to find many with the same determinant but with very different numbers of zeros. $\endgroup$ – Gerry Myerson Oct 19 '12 at 5:41

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.