This question is inspired from here, where it was asked what possible determinants an $n \times n$ matrix with entries in {0,1} can have over $\mathbb{R}$.

My question is: how many such matrices have non-zero determinant?

If we instead view the matrix as over $\mathbb{F}_2$ instead of $\mathbb{R}$, then the answer is

$(2^n-1)(2^n-2)(2^n-2^2) \dots (2^n-2^{n-1}).$

This formula generalizes to all finite fields $\mathbb{F}_q$, which leads us to the more general question of how many $n \times n$ matrices with entries in { $0, \dots, q-1$ } have non-zero determinant over $\mathbb{R}$?

  • 6
    $\begingroup$ research.att.com/~njas/sequences/A046747 $\endgroup$ – Steve Huntsman Mar 18 '10 at 19:00
  • 1
    $\begingroup$ In particular, follow Zivkovic's link on the page for A046747. He has the most recent data for small n that I have found. Gerhard "Ask Me About System Design" Paseman, 2010.03.18 $\endgroup$ – Gerhard Paseman Mar 18 '10 at 22:32
  • $\begingroup$ I have yet to find anyone addressing the spectrum question for (0,1,...,q-1) matrices or related questions. I look forward to anyone posting a pointer to such material. Gerhard "Ask Me About System Design" Paseman, 2010.03.18 $\endgroup$ – Gerhard Paseman Mar 18 '10 at 22:36
  • 1
    $\begingroup$ What does the obvious chinese remaindering argument give you: in other words, the biggest the determinant could be is $n^n$ (by Hadamard). Now, assuming (that's the big problem obviously) that the probability that a $0, 1$ matrix mod $p$ is singular is the same as the probability that a random matrix is singular, then you get an obvious product over primes for the probability. Is this close to the conjectured answer? $\endgroup$ – Igor Rivin Mar 23 '12 at 16:15
  • 2
    $\begingroup$ The link Steve Huntsman gives has been moved to oeis.org/A046747 $\endgroup$ – David Roberts Oct 30 '13 at 22:26

See Sloane, A046747 for the number of singular (0,1)-matrices. It doesn't seem like there's an exact formula, but it's conjectured that the probability that a random (0,1)-matrix is singular is asymptotic to $n^2/2^n$.

Over $F_2$ the probability that a random matrix is nonsingular, as $n \to \infty$, approaches the product $(1/2)(3/4)(7/8)\cdots = 0.2887880951$, and so the probability that a random large matrix is singular is only around 71 percent. I should note that a matrix is singular over $F_2$ if its real determinant is even, so this tells us that determinants of 0-1 matrices are more likely to be even than odd.

  • $\begingroup$ Thanks Michael. Is there an elementary proof of why the determinant is more likely to be even than odd? $\endgroup$ – Tony Huynh Mar 18 '10 at 19:34
  • $\begingroup$ Not that I know of, but I'm hardly an expert on random matrices. $\endgroup$ – Michael Lugo Mar 18 '10 at 19:36
  • 16
    $\begingroup$ Fill in a size $n$ square matrix over $\mathbb{F}_2$ row by row. If the first $n-1$ rows are linearly independent, the whole matrix will have zero determinant. Otherwise the last row will cause the determinant to vanish if its entries satisfy a linear equation; this happens with conditional probability $1/2$. $\endgroup$ – Robin Chapman Mar 18 '10 at 19:58
  • 3
    $\begingroup$ I think you mean "linearly dependent". $\endgroup$ – Douglas S. Stones Mar 24 '10 at 6:55

As Michael noted, the conjectured bound for the probability a random $(0,1)$ matrix is singular is conjectured to be $(1+o(1)) n^2 2^{-n} $. This corresponds to the natural lower bound coming from the observation that if a matrix has two equal rows or columns it is automatically singular.

The best bound currently known for this problem is $(\frac{1}{\sqrt{2}} + o(1) )^n$, and is due to Bourgain, Vu, and Wood. Corollary 3.3 in their paper also gives a bound of $(\frac{1}{\sqrt{q}}+o(1))^n$ in the case where entries are uniformly chosen from $\{0, 1, \dots, q-1\}$ (here the conjectured bound would be around $n^2 q^{-n})$

Even showing that the determinant is almost surely non-zero is not easy (this was first proven by Komlos in 1967, and the reference is given in Michael's Sloane link).


Lurking around MO, I found a question which is related to the second part of my question. Namely, Greg Martin and Erick B. Wong prove that assuming that the entries of an $n \times n$ matrix are chosen randomly with respect to a uniform distribution from the set $\{-k, \dots, k\}$, then the probability that the resulting matrix will be singular is $\ll k^{-2 + \epsilon}$.

See this MO question (where the above paragraph is plagarized from) and also here for the link to the Martin & Wong paper.


Your Answer

By clicking "Post Your Answer", you acknowledge that you have read our updated terms of service, privacy policy and cookie policy, and that your continued use of the website is subject to these policies.

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