16
$\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
    $\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
  • 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 '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
  • 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$ – Timothy Chow Jan 15 at 22:27
18
$\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$
  • $\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
14
$\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$
1
$\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, privacy policy and cookie policy

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