Lower bound of the probability of singular random matrix over $\{\pm1\}$ in ``Singularity of random Bernoulli matrices"

Question

Suppose $M_{n}$ is an $n \times n$ matrix with independent ±1 entries. Recent breakthrough shows that the probability $\mathbb{P}(M_{n} \text{ is singular})$ is

$$(1) \quad\quad\qquad \mathbb{P}(M_{n} \text{ is singular})= \left(1/2 +o_{n}(1)\right)^{n}.$$

based on the main theorem below.

THEOREM A. For every $p \in(0,1 / 2]$ and $\varepsilon>0,$ there are $n_{p, \varepsilon}, C_{p, \varepsilon}>0$ depending only on $p$ and $\varepsilon$ with the following property. Let $n \geq n_{p, \varepsilon},$ and let an $B_{n}(p)$ be $n \times n$ random matrix with independent entries $b_{i j},$ such that $\mathbb{P}\left\{b_{i j}=1\right\}=p$ and $\mathbb{P}\left\{b_{i j}=0\right\}=1-p .$ Then for any $s \in[-1,0]$ $$ \mathbb{P}\left\{s_{\min }\left(B_{n}(p)+s 1_{n} 1_{n}^{\top}\right) \leq t / \sqrt{n}\right\} \leq(1-p+\varepsilon)^{n}+C_{p, \varepsilon} t, \quad t>0 $$

My question is, how can the author get the lower bound to show the probability? In the paper, the author mentioned about the lower bound two times, but maybe I did not clearly understand them. I really appreciate if someone gives a literature or idea of proof about the lower bound of (1).

Below are my trial to found the author's comments related to lower bound. First of all, in p.594, the author mentioned that

It is easy to see that the probability that the first column of $B_{n}(p)$ is equal to zero is $(1-p)^{n} .$ Thus, the theorem implies that, for a fixed $p \in(0,1 / 2]$, $$ \mathbb{P}\left\{B_{n}(p) \text { is singular }\right\}=\left(1-p+o_{n}(1)\right)^{n} $$ and further, when applied with $p=1 / 2$ and $s=-1 / 2,$ it gives (1) .

I definitely understand $\mathbb{P}\left\{B_{n}(p) \text { is singular }\right\}=\left(1-p+o_{n}(1)\right)^{n}$. However, I do not know how can we say something on $\mathbb{P}(M_{n} \text{ is singular})$ based on the probability $\mathbb{P}\left\{B_{n}(p) \text { is singular }\right\}$. For example, even if a matrix $M$ of $B_{n}(p)$ type is singular, it does not implies that $M-(1/2) 1_{n} 1_{n}^{\top}$ is singular; for example, $\left[\begin{smallmatrix}0 & 1 \\ 0 & 1\end{smallmatrix}\right]$ is singular but $1/2\left[\begin{smallmatrix}-1 & 1 \\ -1 & 1\end{smallmatrix}\right]$ is not. Also, I try to make a lower bound from the fact that $1_{n} 1_{n}^{\top}$ has eigenvalues $0$ and $n$, but failed. Moreover, the argument of $(1-p)^{n}$ to get the lower bound of $B_{n}(p)$ seems not applicable for $M_{n}$ since even if a matrix have columns of $-1$, it can be nonsingular.

Next, the author also mentioned this lower bound in p.596.

Thus, to show that $B_{n}(p)+s 1_{n} 1_{n}^{\top}$ is singular with probability $\left(1-p+o_{n}(1)\right)^{n},$ it is sufficient to check that the threshold of the random normal $Y_{n}$ is at most $\left(1-p+o_{n}(1)\right)^{n}$ with probability at least $1-\left(1-p+o_{n}(1)\right)^{n} .$

I know this is a summary of proof strategy, however, I still did not find how this statement came up from the lemma or theorems in further sections.

And these are all I found mentioning about the lower bound. Maybe I missed something in the further section, since (honestly) I did not understand his proof in precise manner.

Thank you very much for your consideration.

Answer 1

The first two rows are identical with probability $2^{-n}$, so $\mathbb{P}(\det M_n = 0) \geq 2^{-n}$.

Incidentally, there are $2 \times \binom{n}{2}$ events like this to consider, though not quite independent, so it is reasonable to expect $\mathbb{P}(\det M_n = 0) \approx n(n-1) 2^{-n}$, and this has been conjectured since the beginning of discrete random matrix theory (originally by Komlós perhaps).

For $B_n$ (the random matrix with $0/1$ entries instead of $\pm1$), one also has the events that a whole row or column is zero, so one may expect the headline to change to $n(n+1)2^{-n}$.