23
$\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
    @Will & Qiaochu: Thank you! The MO posting is quite informative.2011-07-28

1 Answers 1

17

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.

  • 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