# Number of zero entries in symmetric (0-1)-matrix with full diagonal

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$ ?

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.

• Thanks Gerry. Is the situation similarly hopeless when the determinant is nonzero? – Nasos Evangelou-Oost Oct 19 '12 at 3:26
• 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. – Gerry Myerson Oct 19 '12 at 5:41