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).
No comments:
Post a Comment