18

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}$?

Tony Huynh
  • 31,500
  • 6
    http://www.research.att.com/~njas/sequences/A046747 – Steve Huntsman Mar 18 '10 at 19:00
  • 1
    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 – Gerhard Paseman Mar 18 '10 at 22:32
  • 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 – Gerhard Paseman Mar 18 '10 at 22:36
  • 2
    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? – Igor Rivin Mar 23 '12 at 16:15
  • 2
    The link Steve Huntsman gives has been moved to http://oeis.org/A046747 – David Roberts Oct 30 '13 at 22:26
  • 1
    The asymptotics of this sequence were recently obtained by Tikhomirov. https://arxiv.org/pdf/1812.09016.pdf Someone should probably update the OEIS for A046747 and http://oeis.org/A057982 – Timothy Chow Jan 15 '19 at 22:27

3 Answers3

22

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.

Emil Jeřábek
  • 44,710
Michael Lugo
  • 13,858
  • Thanks Michael. Is there an elementary proof of why the determinant is more likely to be even than odd? – Tony Huynh Mar 18 '10 at 19:34
  • Not that I know of, but I'm hardly an expert on random matrices. – Michael Lugo Mar 18 '10 at 19:36
  • 20
    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$. – Robin Chapman Mar 18 '10 at 19:58
  • 4
    I think you mean "linearly dependent". – Douglas S. Stones Mar 24 '10 at 06:55
17

As Michael noted, the conjectured bound for the probability a random $(0,1)$ matrix is singular is $(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 for a long time for this problem was $(\frac{1}{\sqrt{2}} + o(1) )^n$, 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).

Update: Konstantin Tikhimorov has uploaded a preprint giving a bound of $(\frac{1}{2}+o(1))^n$ on the singularity probability in the $(0,1)$ case, matching the lower bound up to the $o(1)$ in the exponent) (the result stated in his paper is for $\pm 1$ matrices, but there's a bijection showing that the singularity probability of an $n \times n$ $\pm 1$ matrix is the same as that of an $(n-1) \times (n-1)$ matrix with entries uniformly from $\{0,1\}$).

Kevin P. Costello
  • 5,751
2

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.

Community
  • 1
Tony Huynh
  • 31,500