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.

What is the probability that a random $\{0,1\}$, $n \times n$ matrix is invertible? Assume the 0 and 1 are each present in an entry with probability $\frac{1}{2}$. Is there an explicit formula as a function of $n$? Does it tend to 1 as $n$ grows large? I'm sure this is all known...

Thanks!

share|improve this question
    
Over which ring do you mean? $\mathbb F_2$, $\mathbb Z$ or $\mathbb R$? –  joriki Jul 28 '11 at 12:06
6  
Tao and Vu have looked at the problem over $\mathbf R$. The probability tends toward 1, but an exact formula isn't known. Here's a quote from the abstract of Tao and Vu's paper: "We show that the probability that $M_n$ is singular is at most $(3/4 +o(1))^n$..." The preprint is here. The paper appeared in JAMS. –  Will Orrick Jul 28 '11 at 12:33
6  
You are correct, but the answer is the same for both problems. There's a 1-1 map from $n\times n$ $\{-1,1\}$ matrices normalized so that the first row and column are all ones and $(n-1)\times(n-1)$ $\{1,0\}$ matrices. Under this map, the determinant changes by a factor of $2^{1-n}$. –  Will Orrick Jul 28 '11 at 12:44
1  
Incidentally, the result that the singularity probability tends toward zero is due to Komlos. See Tao and Vu's earlier paper for the history of the problem. –  Will Orrick Jul 28 '11 at 12:50
3  
@Joseph: this was discussed on MO at mathoverflow.net/questions/18636/… . –  Qiaochu Yuan Jul 28 '11 at 13:30
show 3 more comments

1 Answer

Here's the answer over $\mathbb F_2$; I don't know about other rings:

The first row vector has a $1$ in $2^n$ chance to be linearly dependent, the second $2$ in $2^n$ and so on, so the probability for an $n\times n$ matrix to be invertible is

$$p(n)=\prod_{k=1}^{n}(1-2^{-k})\;,$$

and the limit is

$$\lim_{n\to\infty}p(n)=\prod_{k=1}^{\infty}(1-2^{-k})\approx0.288788$$

as calculated by W|A.

share|improve this answer
3  
Interesting! Let's call that joriki's number. :-) –  Joseph O'Rourke Jul 28 '11 at 12:30
4  
I can't resist: en.wikipedia.org/wiki/Pentagonal_number_theorem –  t.b. Jul 28 '11 at 12:47
    
@Joseph: I strengthened my claim to it by using it in another answer. :-) –  joriki Oct 24 '12 at 9:25
add comment

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.