Skip to main content
added 469 characters in body
Source Link
Kevin P. Costello
  • 5.8k
  • 2
  • 30
  • 37

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 a long time for this problem iswas $(\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).

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

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

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

Source Link
Kevin P. Costello
  • 5.8k
  • 2
  • 30
  • 37

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