Probability a determinant is odd

[ehrenfest]

[SOLVED] probability a determinant is odd

Homework Statement

The elements of a determinant are arbitrary integers. Determine the probability that the value of the determinant is odd. (Hint: Work mod 2).

Homework Equations

The Attempt at a Solution

When n=1, the probability is 1/2. When n = 2, the probability is 3/8. That is the last case I can do by hand. I am trying to find a recursion, but that is hard as the following example illustrates.

For n=3, if you expand along the first column, you can multiply the probability that a_{11} is odd by the probability that its cofactor is odd and than do the same for a_{21} and a_{31}. You can ignore the sign of the cofactor because we are working mod 2. So, we can just add these three terms.

It would be nice if you could apply the n=2 case to the cofactors, but the probability the cofactor of a_{11} is odd is not independent of the probability that the a_{21} cofactor is odd, so I don't think that you can just replace those probabilities by P_{n-1}.

 

[ehrenfest]

anyone?

 

[Dick]

Let P(n) be the probability an nxn matrix has 0 determinant mod 2. Do a row reduction on the first column. Add rows until there is a single 1 and the rest 0's. Let Q(n) be the probability you cannot do this (i.e. the whole first column is 0's). Argue that the (n-1)x(n-1) minor is still a random matrix mod 2. So the probability P(n)=Q(n)+(1-Q(n))P(n-1). Test it. Q(2)=1/4, P(1)=1/2, so P(2)=1/4+(3/4)*(1/2)=5/8.

 

[ehrenfest]

Here is the complete proof:

Consider a random random n by n matrix mod 2.

Let P(n) be the probability an nxn matrix has determinant equal to 1.
Let Q(n) be the probability that every element in the first column is a 0. In this case the determinant is 0.

If there are any 1s in the first column, select one, say a_{i0}. Add a_i to every other row that has a one in the first column. I claim that the (n-1)by(n-1) submatrix induced by deleting row i and column 0 is still random. To prove this, I need to show that the probability of having a 0 in any of its elements is exactly 1/2. Let a_jk be a given a element in this submatrix. The probability that a_jk is 0 after our row reductions is:

P(a_jk=0)*P(a_j0 = 0)+P(a_jk= 0)*P(a_j0 = 1)*P(a_ik=0)+P(a_jk = 1)*P(a_j0 = 1)*P(a_ik=1) =1/2*1/2+1/2*1/2*1/2+1/2*1/2*1/2 = 1/4+1/8+1/8=1/2

where each of the probabilities are for the INITIAL RANDOM MATRIX.

Therefore, 1-P(n) = Q(n)+(1-Q(n))(1-P(n-1)).

Q(n)=(1/2)^n P(1)=1/2.
The answer is then P(n) = 1 - (1/2)^n +((1/2)^n-1)(1-P(n-1)) = ((1/2)^n-1)(-1+1-P(n-1))=(1-(1/2)^n)P(n-1).

 

[Dick]

Seems ok to me. I don't much like the 'proof' that the (n-1)x(n-1) submatrix is truly 'random' but I can't think of anything better without getting long winded. The row operations are reversible and the first column is independent of the other columns so it's sort of 'obvious'.

 

[ehrenfest]

I don't see anything wrong with my proof that the (n-1)x(n-1) submatrix is random. I edited that post, so maybe you read the old version.

 

[Dick]

That I don't 'like' it doesn't mean I don't accept it. You don't have a formal definition of a 'random' matrix either, so I don't think it's worth putting a lot of worry time in. Let's just stick with what you have.