# What is the largest possible probability that a random matrix over $\mathbb{F}_2$ is non-singular?

Suppose $$A(p, n)=(a_{ij}(p))_{i, j \leq n}$$ is an $$n\times n$$ random matrix over $$\mathbb{F_2}$$, with all its entries being i.i.d. and such that $$P(a_{ij}(p) = 1) = p$$, where $$p$$ is some real number from $$[0; 1]$$. What is the largest possible probability, that $$A(p, n)$$ is non-singular and with what $$p$$ is it reached?

Note, that $$A(p, n)$$ in non-singular iff $$det(A(p, n)) = 1$$.

Solution for $$n=1$$:

$$det(A(p, 1)) = 1$$ with probability $$p$$. The maximum of $$det(A(p, 1))$$ is $$1$$ and it is reached with $$p = 1$$.

Solution for $$n = 2$$:

$$det(A(p, 2)) = 1$$ with probability $$2p^2(1 - p^2)$$. The maximum of $$P(det(A(p, 2))=1)$$ is $$\frac{1}{2}$$ and it is reached with $$p = \frac{1}{\sqrt{2}}$$.

However, I would like to know some sort of general formula (or at least asymptotics).

EDIT:

After I failed to solve this problem using determinants, I tried to prove this using the fact that asquare matrix is non-singular iff its rows are linearly dependent. As there exists only one non-zero element in $$\mathbb{F_2}$$, we can write linear dependence of the vector system $$\{v_i\}_{i \leq n}$$ in $$\mathbb{F}_2^n$$ as $$\forall S \subset \{1, ... , n\}$$ such that $$S \neq \emptyset$$ we have $$\sum_{i \in S} v_i \neq \overline{0}$$. I know the probability that a given set of vectors with i.i.d. random entries Bernoulli distributed with parameter $$p$$ $$\{v_i\}_{i \leq k}$$ over $$\mathbb{F}_2^n$$ satisfy $$\sum_{i = 1}^k v_i \neq \overline{0}$$ is $$(1 - \frac{p((1 - 2p)^k - 1)}{1 - 2p})$$. However, I do not know how to proceed further in this direction.

• Nov 30 '19 at 11:55
• Nov 30 '19 at 11:55
• Doesn't the question you marked as a duplicate (and also the other one in a comment above) only address the case $p=\frac12$? I think your question is considerably harder, since we can't use the symmetry in the way we used it in those other questions. Thus I don't think it's a duplicate? Jan 18 '20 at 8:38
• @joriki, when I marked this question as duplicate, I thought that the answers for $p = \frac{1}{2}$ can be easily generalised to the case of arbitrary $p$. Now I see, that it is not the case... I voted to reopen the question. Jan 18 '20 at 9:32
• OK -- I've reopened the question. Jan 18 '20 at 17:32

Random tests give the following results:

$$n;;p_{max};;\max(prob(det(A)=1))$$

2;;0.71;;0.500\$

3;;0.61;;0.387

4;;0.59;;0.343

5;;0.58;;0.317

6;;0.57;;0.305

7;;0.56;;0.299

8;;0.55;;0.293

9;;0.53;;0.293

10;;0.505;;0.290

20;;0.43;;0.290

100;;plateau for $$p\in [0.2,0.3]$$;;0.290

It seems that the lower bound is $$\approx 0.290$$.

EDIT. In fact, it seems that the above lower bound is $$\Pi_{k=1}^{\infty}(1-2^{-k})\approx 0.288788$$, that is $$lim_{n\rightarrow\infty} Prob(det(A)=1)$$ when $$p=1/2$$.