# Probability that a random binary matrix is invertible?

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!

-
Over which ring do you mean? $\mathbb F_2$, $\mathbb Z$ or $\mathbb R$? –  joriki Jul 28 '11 at 12:06
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
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
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
@Joseph: this was discussed on MO at mathoverflow.net/questions/18636/… . –  Qiaochu Yuan Jul 28 '11 at 13:30

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$$

-
Interesting! Let's call that joriki's number. :-) –  Joseph O'Rourke Jul 28 '11 at 12:30
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