Count the $n\times n$ binary matrices with odd/even determinant.

linear algebramatrices

To be specific :
How many $4\times4$ matrices with entries from $0$, $1$ have odd determinant?

P.S : Please do post comment/answer by fully reading it first and which satisfies what I asked for which I cleared at my best possible.

Approach :
I didn't go for combinatorial approach as it was a multiple choice question .
So what i thought of is :
Consider Half of them are even and remaining are odd.
Total is $2^{4\times 4}$ so half would be $65536/2$ hence 2 of the options i have eliminated.
Now, One option was "20160" and other was "32767" but reason i choose 1st option because there are some matrices with "0" determinant so it wont be "32767" , actually less than that so i go for "20160" .

But though I got correct answer , i wasn't satisfied by own intuition so tried it for $2\times 2$ matrix.
What I found is "10" zero matrices , "6" odd and "0" even matrices.
( I didn't considered "0" in the category of even just to separate it from odd/even)

With the $2\times 2$ matrix it didn't satisfy my above intuition of dividing into half.
So my question is :

  1. Whether I got the correct answer by luck?

  2. Where my intuition gone wrong?

  3. How to proceed with generalisation?

Best Answer

Note that in $\mathbb{F}_2$ the only possible odd determinant has value $1$ and the only even determinant has value $0$, implying the matrix is not invertible and thus the columns are not linearly independent.

Now this is just a counting problem that asks: How many matrices are there in $\text{M}_{4 \times 4}\left(\mathbb{F}_2\right)$ with linearly independent columns?

For the first column, there are $2^4-1$ options, all columns except the $0$ column. For the second column, the only stipulation is that it cannot be the same exact column and it cannot be $0$, and it is linearly independent. So there are $2^4-2$ possibilities. For the third, it cannot be either of those columns or the sum or $0$, so there are $2^4-4$ possibilities. And for the remaining column, any possible candidates would have to be not the sum of any combination of the three columns, for which there are $2^3$ sums (including $0$, the sum of none of them).

Thus, $(2^4-1)(2^4-2)(2^4-4)(2^4-2^3) = 20,160$.

I think your intuition would work reasonably well for fields with more elements, where the determinant would act more randomly.

Related Question