22
$\begingroup$

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!

  • 0
    Over which ring do you mean? $\mathbb F_2$, $\mathbb Z$ or $\mathbb R$?2011-07-28
  • 0
    @joriki: I meant over $\mathbb{R}$, but you are right, there are several questions here...2011-07-28
  • 7
    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](http://arxiv.org/abs/math/0501313). The paper appeared in JAMS.2011-07-28
  • 0
    @Will: I think they examine $\{-1,+1\}$ matrices...?2011-07-28
  • 7
    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}$.2011-07-28
  • 1
    Incidentally, the result that the singularity probability tends toward zero is due to Komlos. See Tao and Vu's earlier [paper](http://arxiv.org/abs/math/0411095) for the history of the problem.2011-07-28
  • 3
    @Joseph: this was discussed on MO at http://mathoverflow.net/questions/18636/number-of-invertible-0-1-real-matrices .2011-07-28
  • 0
    @Will & Qiaochu: Thank you! The MO posting is quite informative.2011-07-28

1 Answers 1

16

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.

  • 3
    Interesting! Let's call that joriki's number. :-)2011-07-28
  • 8
    I can't resist: http://en.wikipedia.org/wiki/Pentagonal_number_theorem2011-07-28
  • 0
    @Joseph: I strengthened my claim to it by using it in [another answer](http://math.stackexchange.com/questions/219552/probability-that-a-sequence-repeats-itself/219978#219978). :-)2012-10-24