Take the 2-minute tour ×
Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. It's 100% free, no registration required.

Let $A$ be a $3\times 3$ matrix, and each of its entries takes value from $\{0, 1, 2, 3\}$ with probability $1/4$ for each value. What is the probability that A is invertible?

I have tried to list all possible combinations, but that is too complicated and I cannot proceed. Any help is appreciated.

The matrix operation is in R, not restricted modulo 4. For example, 2*2 = 4, not 0, so a matrix with determinant 4 is regarded as invertible.

share|improve this question

1 Answer 1

up vote 5 down vote accepted

Hint. For $A$ to be invertible, each column of $A$ must be linearly independent. With the exception of all $0$'s, all vectors in $\{0,1,2,3\}$ work for the first column, so there are $4^3-1$ possibilities for this vector. Then, for the second column, you can choose any vector which is linearly independent from the first column vector. Can you count the possible ways this can happen? The third column should be done similarly.

share|improve this answer
    
Thank you for your hint. I have tried this approach but I found that the number of linearly independent vector depends on the values of the first vector. So I have to list the 63 possible vectors first...And the third vector depends on the value of the previous two... –  NECing Feb 16 '13 at 20:38
    
See the general linear group over a finite field here: General_linear_group This should help. –  1015 Feb 16 '13 at 20:40
1  
@Shu If the maximum number in the first column vector $v$ is $1$, then $v$, $2v$ and $3v$ must be discounted from the $2$nd column. If it's $2$, only $v$ must be discounted, unless every entry is even, in which case $1/2v$ must also be discounted. If it's $3$, then only $v$ must be discounted, unless every entry is divisible by $3$ in which case $v/3$ must also be discounted. And so on. You can see how this can be divided up into cases. –  Alexander Gruber Feb 16 '13 at 20:43
    
@AlexanderGruber Right. This is a good way to calculate the possible 2nd vector. But how to deal with the third one, which should not be written as a linear combination of the first two? –  NECing Feb 16 '13 at 20:48
1  
You can do it in just the same way. You discount the same multiples of $v$, then do so for the second vector $w$. For linear combinations $av+bw$ with $a,b\not=0$, everything has to add up to be less than $4$, which admits a similar case by case analysis. It's pretty hard to have them $\leq 4$ by that point. If you write it out for just one case of fixed $v$ and $w$ I'm sure you'll see how to easily divide the rest of the combinations up into classes which have the same number of admissible $3$rd vectors. –  Alexander Gruber Feb 16 '13 at 21:02

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

Not the answer you're looking for? Browse other questions tagged or ask your own question.