26
$\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!

$\endgroup$
8
  • 1
    $\begingroup$ Over which ring do you mean? $\mathbb F_2$, $\mathbb Z$ or $\mathbb R$? $\endgroup$
    – joriki
    Jul 28, 2011 at 12:06
  • 7
    $\begingroup$ 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. $\endgroup$ Jul 28, 2011 at 12:33
  • 7
    $\begingroup$ 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}$. $\endgroup$ Jul 28, 2011 at 12:44
  • 1
    $\begingroup$ 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. $\endgroup$ Jul 28, 2011 at 12:50
  • 3
    $\begingroup$ @Joseph: this was discussed on MO at mathoverflow.net/questions/18636/… . $\endgroup$ Jul 28, 2011 at 13:30

1 Answer 1

22
$\begingroup$

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.

$\endgroup$
4
  • 5
    $\begingroup$ Interesting! Let's call that joriki's number. :-) $\endgroup$ Jul 28, 2011 at 12:30
  • 9
    $\begingroup$ I can't resist: en.wikipedia.org/wiki/Pentagonal_number_theorem $\endgroup$
    – t.b.
    Jul 28, 2011 at 12:47
  • $\begingroup$ @Joseph: I strengthened my claim to it by using it in another answer. :-) $\endgroup$
    – joriki
    Oct 24, 2012 at 9:25
  • 1
    $\begingroup$ @JosephO'Rourke: Turns out the number already had an OEIS entry in $2007$, so no claim to a name, I'm afraid :-) $\endgroup$
    – joriki
    Mar 17, 2023 at 15:03

Not the answer you're looking for? Browse other questions tagged .