3
$\begingroup$

Let $A_n$ be a random $n \times n$ matrix with entries in $\{-1, +1\}$. As usual, "random" here means with respect to the uniform measure over such matrices.

The strong version of the singularity conjecture is that, as $n \to \infty$, $$ \mathbb{P}\{ \text{det}(A_n) = 0\} = (1 +o(1)) \, n^2 2^{-(n-1)} $$ I understand the right hand side comes from the fact that there are $2 \binom{n}{2} \sim n^2 $ possible selections of rows and columns and that $2^{-(n-1)}$ is the probability that any such pair is equal up to sign.

However, this is not a rigorous argument, since it ignores the dependence of such selections of rows and columns. Is there a rigorous lower bound that matches the asymptotics above that handles the dependence issues?

Improve this question
$\endgroup$
1
  • 1
    $\begingroup$ Shouldn't it be trivial to make that lower bound rigorous? The probability three rows are the same is like $2^{-2n}$... $\endgroup$
    – mathworker21
    Commented Dec 2 at 22:35

1 Answer 1

Reset to default
5
$\begingroup$

On the singularity of random Bernoulli matrices - novel integer partitions and lower bound expansions derives the lower bound (theorem 1) $$\mathbb{P}\{ \text{det}(A_n) = 0\} \geq 2^{2-n} \binom{n}{2}-2^{-2n} \left(12 \binom{n}{2}^2-4 \binom{n}{2}\right),$$ which is of order $n^2 2^{1-n}$ for $n\rightarrow\infty$. The "independent selection" contribution is the first term $2^{2-n} \binom{n}{2}$. The second term is smaller by a factor $n^2/2^n$ for large $n$.

Improve this answer
$\endgroup$
3
  • $\begingroup$ Yeah, I saw this paper. I guess their interest is in deriving an even sharper asymptotic expansion. However, I was wondering if there are any elementary arguments that lead to the leading order term (at least as a lower bound, obviously we can't expect this for the upper bound, otherwise we'd solve the strong conjecture) $\endgroup$
    – Drew Brady
    Commented Dec 2 at 20:07
  • 2
    $\begingroup$ The earlier comment gives the elementary argument you're looking for: for any pair, let $E_{i,j}$ be the event that the $i$th and $j$th rows are equal up to signs. Then a lower bound for $\mathbb P(\bigcup_{i<j}E_{i,j})$ is a lower bound for $\mathbb P(\det(A_n)=0)$. You can get a lower bound from the sum of the first two terms of inclusion-exclusion. The contributions to the second term are of the form $E_{i,j}\cap E_{i',j'}$. If $i,i',j,j'$ are distinct, this probability is $2^{-2(n-1)}$. If one of $i',j'$ agrees with one of $i,j$, it's also $2^{-2(n-1)}$. Now sum over $n^4$ many terms. $\endgroup$
    – Anthony Quas
    Commented Dec 3 at 0:09
  • $\begingroup$ Thanks. The inclusion-exclusion argument is obvious in retrospect, makes sense! $\endgroup$
    – Drew Brady
    Commented Dec 3 at 1:24

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .