1. Not finding help here? Sign up for a free 30min tutor trial with Chegg Tutors
    Dismiss Notice
Dismiss Notice
Join Physics Forums Today!
The friendliest, high quality science and math community on the planet! Everyone who loves science is here!

Probability a determinant is odd

  1. Jan 1, 2008 #1
    [SOLVED] probability a determinant is odd

    1. The problem statement, all variables and given/known data
    The elements of a determinant are arbitrary integers. Determine the probability that the value of the determinant is odd. (Hint: Work mod 2).


    2. Relevant equations



    3. 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}.
     
  2. jcsd
  3. Jan 2, 2008 #2
    anyone?
     
  4. Jan 3, 2008 #3

    Dick

    User Avatar
    Science Advisor
    Homework Helper

    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.
     
    Last edited: Jan 3, 2008
  5. Jan 3, 2008 #4
    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).
     
    Last edited: Jan 3, 2008
  6. Jan 3, 2008 #5

    Dick

    User Avatar
    Science Advisor
    Homework Helper

    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'.
     
  7. Jan 3, 2008 #6
    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.
     
  8. Jan 3, 2008 #7

    Dick

    User Avatar
    Science Advisor
    Homework Helper

    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.
     
Know someone interested in this topic? Share this thread via Reddit, Google+, Twitter, or Facebook

Have something to add?