Skip to main content
1 of 2
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).

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