4
$\begingroup$

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.

$\endgroup$
6
  • 1
    $\begingroup$ (1) math.stackexchange.com/questions/54246/… $\endgroup$
    – d.k.o.
    Nov 30 '19 at 11:55
  • 1
    $\begingroup$ (2) math.stackexchange.com/questions/71288/… $\endgroup$
    – d.k.o.
    Nov 30 '19 at 11:55
  • 1
    $\begingroup$ 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? $\endgroup$
    – joriki
    Jan 18 '20 at 8:38
  • $\begingroup$ @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. $\endgroup$ Jan 18 '20 at 9:32
  • $\begingroup$ OK -- I've reopened the question. $\endgroup$
    – joriki
    Jan 18 '20 at 17:32
3
$\begingroup$

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

$\endgroup$
0

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.