Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. It's 100% free, no registration required.

Sign up
Here's how it works:
  1. Anybody can ask a question
  2. Anybody can answer
  3. The best answers are voted up and rise to the top

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


share|cite|improve this question
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… . – 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


and the limit is


as calculated by W|A.

share|cite|improve this answer
Interesting! Let's call that joriki's number. :-) – Joseph O'Rourke Jul 28 '11 at 12:30
I can't resist: – 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

Your Answer


By posting your answer, you agree to the privacy policy and terms of service.

Not the answer you're looking for? Browse other questions tagged or ask your own question.