18
$\begingroup$

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

$\endgroup$
6
  • 6
    $\begingroup$ research.att.com/~njas/sequences/A046747 $\endgroup$ Mar 18, 2010 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$ Mar 18, 2010 at 22:32
  • 2
    $\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, 2012 at 16:15
  • 2
    $\begingroup$ The link Steve Huntsman gives has been moved to oeis.org/A046747 $\endgroup$
    – David Roberts
    Oct 30, 2013 at 22:26
  • 1
    $\begingroup$ The asymptotics of this sequence were recently obtained by Tikhomirov. arxiv.org/pdf/1812.09016.pdf Someone should probably update the OEIS for A046747 and oeis.org/A057982 $\endgroup$ Jan 15, 2019 at 22:27

3 Answers 3

22
$\begingroup$

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.

$\endgroup$
4
  • $\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, 2010 at 19:34
  • $\begingroup$ Not that I know of, but I'm hardly an expert on random matrices. $\endgroup$ Mar 18, 2010 at 19:36
  • 20
    $\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$ Mar 18, 2010 at 19:58
  • 4
    $\begingroup$ I think you mean "linearly dependent". $\endgroup$ Mar 24, 2010 at 6:55
17
$\begingroup$

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\}$).

$\endgroup$
2
$\begingroup$

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.

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

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