# Probability that a random binary matrix is invertible? [duplicate]

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$? Jul 28, 2011 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. Jul 28, 2011 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}$. Jul 28, 2011 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. Jul 28, 2011 at 12:50
• @Joseph: this was discussed on MO at mathoverflow.net/questions/18636/… . Jul 28, 2011 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. :-) Jul 28, 2011 at 12:30
• I can't resist: en.wikipedia.org/wiki/Pentagonal_number_theorem
– t.b.
Jul 28, 2011 at 12:47
• @Joseph: I strengthened my claim to it by using it in another answer. :-) Oct 24, 2012 at 9:25
• @JosephO'Rourke: Turns out the number already had an OEIS entry in $2007$, so no claim to a name, I'm afraid :-) Mar 17, 2023 at 15:03