S.O.S. Mathematics CyberBoard

Let A be a nxn matrix whose entries are from {0,1}. Find the probability that the determinant of A is not zero.

I manage to get the sample space as . So when n=3, there are 512 determinants to compute. I know most of them are zero but I haven't find a systematic way to count the number of matrix whose det are nonzero.

Any idea ?

Characteristic 2 is just the order of GL_n(F_2), which is easy.

Characteristic 0 is a hard exercise in inclusion-exclusion because you don't have the symmetry characteristic 2 gives.

Oops, I've no idea what's GL_n(F_2).
And characteristics too...

The entries in a matrix have to come from somewhere.

If they all come from {0, 1}, and we adopt the convention that 1+1 = 0 (i.e. adopt mod 2 arithmetic), we can say they come from a "finite field" of order 2. The order is the number of elements.

There are rules about finite fields which lead to the fact that the order is always a power of a prime number. The prime number is the "characteristic".

If the field has an infinite number of elements, we say the characteristic is 0.

is a general linear group on a finite field of 2 elements, so it can be considered as the set of all 2x2 matrices with entries from {0,1} and non-zero determinants.

--------------------------------

Now, to count the number of matrices with non-zero determinant: no row can be a multiple of any other.

Start with the first row. It can't be all zero.

The second row can't be a multiple of the first. So it can't be 0 times the first row, or 1 times the first row.

The third row can't be a combination of the first or the second. So it can't be all zeroes, or 1 times the first row, or 1 times the second row, or the first row plus the second row.

Et cetera.

So there are (2^n)-1 possibilities for the first row, (2^n)-2 possibilities for the second row, (2^n)-4 possibilities for the third row, (2^n)-8 possibilities for the fourth row... et cetera.

For the last row there are possibilities.

Multiply these numbers together and you should get the number of matrices with non-zero determinant. Divide by the number of possible matrices. And that's it.

Thanks for the explanations.