# Comptes Rendus
Mathématique

Asaf Ferber

Singularity of random symmetric matrices – simple proof

Volume 359, issue 6 (2021), p. 743-747

Published online: 2 September 2021

https://doi.org/10.5802/crmath.215

<figure><img src="image_1.png" /></figure>

This article is licensed under the

CREATIVE COMMONS ATTRIBUTION 4.0 INTERNATIONAL LICENSE.

http://creativecommons.org/licenses/by/4.0/

<figure><img src="image_2.png" /></figure>
<figure><img src="image_3.png" /></figure>

Probability theory / Probabilitées

# Singularity of random symmetric matrices –
simple proof

Asaf Ferber*, a

<sup>a</sup> Department of Mathematics, University of California, Irvine, USA.

**Abstract.** In this paper we give a simple, short, and self-contained proof for a non-trivial upper bound on the probability that a random ±1 symmetric matrix is singular.

**Funding.** Research is partially supported by an NSF grant DMS-1954395.

Manuscript received 16th February 2021, revised and accepted 14th April 2021.

## 1. Introduction

A widely studied model of discrete random matrices is that of random symmetric ±1 matrices. That is, let $M_n$ denote an $n \times n$ symmetric ±1 matrix chosen uniformly from the set of all such matrices.

One of the most natural problems is to estimate

$$p(n) = \Pr[M_n \text{ is singular}].$$

In this model, even proving that $p(n) = o(1)$ (this problem was posed by Weiss in the early 1990s) is quite challenging and was only settled in 2005 by Costello, Tao, and Vu [2], who showed that

$$p(n) = O(n^{-1/8+o(1)}).$$

In their work, they introduced and studied a quadratic variant of the Erdős–Littlewood–Offord inequality and a useful decoupling lemma, which serve as key tools in all subsequent works on this problem.

Following some intermediate works by Nguyen [6], Vershynin [7], and Ferber and Jain [3], the current best bound on $p(n)$ is

$$p(n) = 2^{-\omega(\sqrt{n})}$$

due to Campos, Mattos, Morris, and Morrison [1]. Moreover, as was noted in [1], this bound is the best one can hope to obtain using the existing technique.

The common belief is that $p(n) = (\frac{1}{2} + o(1))^n$, which, if true, is clearly best possible, as one can check by calculating the probability that $M_n$ has at least two identical rows/columns. Therefore,

<footnote>* Corresponding author.</footnote>
in order to make a further progress, it is required to come up with new ideas/techniques to tackle this problem. The aim of this note is to provide a proof for a non-trivial (but yet, quite weak) bound for $p(n)$ which completely avoids the difficulties from the previous approach (it might introduce new difficulties though).

Our main theorem is the following:

**Theorem 1.** There exists some $C > 0$ for which $p(n) = O(\frac{\log^C n}{n^{1/2}})$.

We did not try to improve the bound in Theorem 1 as we wanted to keep the proof short and simple. It is plausible that with some ideas from [3] one could significantly improve this bound, but in order to obtain an exponential bound it seems like one needs to come up with new ideas.

The proof is based on ideas from [4,5], but the details are much simpler. Roughly speaking, we actually prove the theorem over the finite field with $a$ elements, $\mathbb{Z}_q$, where $q$ is a carefully chosen prime. Let $K := |Ker(M)|$ be the random variable that outputs the size of the kernel of $M$ over $\mathbb{Z}_q$, and we will show, using an elegant Fourier-type argument, that $\mathbb{E}[K] \le 2+o(1)$. Then, observe that if $M$ is singular, then $K \ge q$, so by Markov's inequality we obtain that the probability to be singular is at most $\frac{2+o(1)}{q}$. In fact, the same argument gives a bound of $\frac{1+o(1)}{q-1}$ (if we define $K$ to be the number of non-zero vectors in the kernel), but it does not really matter for us as our bound is far from being the conjectured (or even the best known) bound.

## 2. Auxiliary lemmas

Let $q$ be some prime number, let $\mathbf{a} \in \mathbb{Z}_q^n$, and let $r \in \mathbb{Z}_q$. The $r$th level set of $\mathbf{a}$ is

$$L_r(\mathbf{a}) = \{i \in [n] | a_i = r\}.$$

For convenience, we will use the notation $L_{\ne r} := [n] \setminus L_r$, and we also set $m(\mathbf{a})$ to be the size of the largest level set.

Finally, we let

$$\mathcal{L} := \{ \mathbf{a} \in \mathbb{Z}_q^n \mid m(\mathbf{a}) \ge n - n / \log^2 n \}$$

be the set of all $\mathbf{a} \in \mathbb{Z}_q^n$ with some level set of size larger than $n - \frac{n}{\log^2 n}$.

Now we are ready to state our auxiliary lemmas. First, let us make the following simple (but yet, useful) observation:

**Observation 2.** Let $\mathbf{a} \in \mathbb{Z}_q^n \setminus \{\mathbf{0}\}$. Then,

$$\Pr[M_n \cdot \mathbf{a} = \mathbf{0}] \le 2^{-n}.$$

**Proof.** Indeed, let $1 \le j \le n$ be some coordinate for which $a_j \ne 0 \mod q$, and expose all the entries of $M_n$ but the entries in the $j$th row and column. It is now straightforward to see that we obtain the desired. $\square$

The following lemma is basically the key lemma for our proof. Roughly speaking, it asserts that if $\mathbf{a} \notin \mathcal{L}$, then $M_n \cdot \mathbf{a}$ is (more or less) equally likely to be any vector from $\mathbb{Z}_q^n$.

**Lemma 3.** Let $q$ be a prime such that $q = O(n^{1/2}/\log^C n)$. Let $\mathbf{a} \notin \mathcal{L}$, and $\mathbf{v} \in \mathbb{Z}_q^n$. Then,

$$\Pr[M_n \cdot \mathbf{a} = \mathbf{v}] = \frac{1 + o(1)}{q^n}.$$

Before proving Lemma 3, let us first state (and prove) two simple statements that will be used in the proof of the lemma.

**Proposition 4.** Let $\mathbf{a} \notin \mathcal{L}$ and let $\ell \in \mathbb{Z}_q^n$ be a vector with support of size $s < \frac{n}{2\log^2 n}$. Then, there are at least $\frac{sn}{2\log^2 n}$ pairs $1 \le i < j \le n$ for which $\ell_i a_j + \ell_j a_i \ne 0 \mod q$.
**Proof.** Since $\mathbf{a} \notin \mathcal{L}$, we have that $|L_{\neq 0}(\mathbf{a})| \geq \frac{n}{\log^2 n}$ and therefore we have that $J := L_0(\mathbf{\ell}) \cap L_{\neq 0}(\mathbf{a})$ is of size at least $|L_{\neq 0}(\mathbf{a})| - s \geq \frac{n}{2\log^2 n}$. Now, observe that for every $i \in L_{\neq 0}(\mathbf{\ell})$ and $j \in J$ we have that $\ell_i a_j + \ell_j a_i = \ell_i a_j \neq 0 \bmod q$. In particular, there are at least

$$|L_{\neq 0}(\mathbf{\ell})| \cdot |J| \geq \frac{sn}{2\log^2 n}$$

such pairs. This completes the proof.

**Proposition 5.** Let $\mathbf{a} \notin \mathcal{L}$ and let $\mathbf{\ell} \in \mathbb{Z}_q^n$ be a vector with support of size $s \geq \frac{n}{2\log^2 n}$. Then, there are at least $\min\{s^2/20, \frac{sn}{2\log^2 n}\}$ pairs $1 \leq i < j \leq n$ for which $\ell_i a_j + \ell_j a_i \neq 0 \bmod q$.

**Proof.** We split into two cases:

**Case 1.** $|L_0(\mathbf{a}) \cap L_{\neq 0}(\mathbf{\ell})| \geq s/2$. In this case, let $I := L_0(\mathbf{a}) \cap L_{\neq 0}(\mathbf{\ell})$ and $J = L_{\neq 0}(\mathbf{a})$. Clearly, for all $i \in I$ and $j \in J$ we have $\ell_i a_j + \ell_j a_i = \ell_i a_j \neq 0 \bmod q$, and therefore, there are at least $|I| \cdot |J| \geq \frac{sn}{2\log^2 n}$ such pairs.

**Case 2.** $|L_{\neq 0}(\mathbf{a}) \cap L_{\neq 0}(\mathbf{\ell})| \geq s/2$. For all $r \in \mathbb{Z}_q$ we define $J_r := L_r(\mathbf{a}) \cap L_{\neq 0}(\mathbf{\ell})$, and observe that $s' := \sum_{r \neq 0} |J_r| \geq s/2$. Next, define an auxilairy graph $G$ on vertex set $V = L_{\neq 0}(\mathbf{a}) \cap L_{\neq 0}(\mathbf{\ell})$, where two vertices $i, j \in V$ are connected by an edge if and only if $\ell_i a_j + \ell_j a_i = 0 \bmod q$. We show that $G$ is triangle free, and therefore, by Mantel's theorem we have $e(G) \leq \frac{1}{2} \cdot \binom{|V|}{2}$. In particular, it means that there are at least $\frac{1}{2} \cdot \binom{|V|}{2} \geq s^2/20$ pairs $i, j \in V$ for which $\ell_i a_j + \ell_j a_i \neq 0 \bmod q$ as desired.

To this end, let $i, j, k \in V$ be three distinct vertices. We distinguish between three cases:

**Case 2.1.** $i, j, k \in J_r$ for some $r \neq 0$. Observe that $\ell_i a_j + \ell_j a_i = r(\ell_i + \ell_j)$, and therefore, if it equals 0 $\bmod q$, then we have $\ell_i = -\ell_j$. Now, without loss of generality we can assume that $\ell_k \neq -\ell_j$ (the case $\ell_k \neq \ell_j$ is treated similarly). Then,

$$\ell_k a_j + \ell_j a_k = r(\ell_k + \ell_j) \neq 0 \bmod q.$$

**Case 2.2.** $i, j \in J_{r_1}$ and $k \in J_{r_2}$ for some $r_1 \neq r_2$ and both are not 0 $\bmod q$. If $\ell_i a_j + \ell_j a_i = r_1(\ell_i + \ell_j) \neq 0 \bmod q$ then we are done. Otherwise, we have that $\ell_i = -\ell_j$. Now, consider the expressions

$$\ell_i a_k + \ell_k a_i = \ell_i r_2 + \ell_k r_1, \text{ and } \ell_j a_k + \ell_k a_j = -\ell_i r_2 + \ell_k r_1.$$

Clearly, at least one of them is not 0 $\bmod q$.

**Case 2.3.** $i \in J_{r_1}, j \in J_{r_2}$ and $k \in J_{r_3}$ for some distinct $r_1, r_2$, and $r_3$, all are not 0 $\bmod q$. Suppose that we have

$$\ell_i a_j + \ell_j a_i = \ell_i a_k + \ell_k a_i = 0 \bmod q.$$

(if not, then we are done).

In particular, it means that

$$\ell_i = \frac{-\ell_j a_i}{a_j} = \frac{-\ell_j r_1}{r_2},$$

and that

$$\ell_i = \frac{-\ell_k r_1}{r_3}.$$

These two identities yield that

$$0 \bmod q = \ell_k r_2 - \ell_j r_3 = \ell_k a_j - \ell_j a_k,$$

and in particular, since $\ell_j a_k \neq 0 \bmod q$, we have that

$$\ell_k a_j + \ell_j a_k \neq 0 \bmod q$$

as desired. This completes the proof.
Now we are ready to prove Lemma 3.

**Proof.** Let $\mathbf{a} \notin \mathcal{L}$, let $\mathbf{v} \in \mathbb{Z}_q^n$, and let $e_q(x) = e^{\frac{2\pi i x}{q}}$. Recalling that $m_{ij} = m_{ji}$, observe that

$$
\begin{align*}
\Pr[M \cdot \mathbf{a} = \mathbf{v}] &= \mathbb{E}[\delta_0(M \cdot \mathbf{a} - \mathbf{v})] \\
&= \frac{1}{q^n} \sum_{\ell \in \mathbb{Z}_q^n} \mathbb{E}[e_q(\ell^T (M_n \mathbf{a} - \mathbf{v}))] \\
&= \frac{1}{q^n} \sum_{\ell \in \mathbb{Z}_q^n} e_q(-\ell^T \mathbf{v}) \cdot \mathbb{E} \left[ e_q \left( \sum_{i,j} m_{ij} \ell_i a_j \right) \right] \\
&= \frac{1}{q^n} \sum_{\ell \in \mathbb{Z}_q^n} e_q(-\ell^T \mathbf{v}) \prod_{1 \le i < j \le n} \mathbb{E}[e_q(m_{ij}(\ell_i a_j + \ell_j a_i))] \prod_{i=1}^n \mathbb{E}[e_q(m_{ii} \ell_i a_i)] \\
&= \frac{1}{q^n} + \frac{1}{q^n} \sum_{\ell \neq 0 \in \mathbb{Z}_q^n} e_q(-\ell^T \mathbf{v}) \prod_{1 \le i < j \le n} \cos\left(\frac{2\pi}{q}(\ell_i a_j + \ell_j a_i)\right) \prod_{i=1}^n \cos\left(\frac{2\pi \ell_i a_i}{q}\right).
\end{align*}
$$

This implies that

$$
\left| \Pr[M \cdot \mathbf{a} = \mathbf{v}] - \frac{1}{q^n} \right| \le \frac{1}{q^n} \sum_{\ell \ne 0 \in \mathbb{Z}_q^n} \left| \prod_{1 \le i < j \le n} \cos\left(\frac{2\pi}{q}(\ell_i a_j + \ell_j a_i)\right) \right|.
$$

Therefore, it is enough to show that

$$
\text{Error} := \sum_{\ell \neq 0} \prod_{1 \le i < j \le n} \left| \cos\left(\frac{2\pi}{q}(\ell_i a_j + \ell_j a_i)\right) \right| = o(1).
$$

Using the following simple estimate

$$
\left| \cos \frac{\pi m}{q} \right| \leq e^{-\frac{2}{q^2}},
$$

which holds for all $m \neq 0 \bmod q$, we can upper bound

$$
\text{Error} \leq \sum_{\ell \in \mathbb{Z}_q^n \setminus \{0\}} e^{-2 \cdot N(\ell, \mathbf{a}) / q^2},
$$

where $N(\ell, \mathbf{a}) = |\{(i, j) \in [n]^2 : i < j \text{ and } \ell_i a_j + \ell_j a_i \neq 0 \bmod q\}|$.

Finally, to complete the proof, we split the above sum according to the size of the support of $\ell$,
and using Propositions 4 and 5 we obtain that

$$
\text{Error} \le \sum_{s=1}^{n} \binom{n}{s} q^s e^{-sn/q^2 \log^2 n} + \sum_{s=n/\log^2 n}^{n} \binom{n}{s} (q-1)^s e^{-s^2/20q^2},
$$

which can be easily seen to be $o(1)$ as long as $q = O(n^{1/2}/\log^C n)$, for $C \ge 3/2$. This completes the proof. $\square$

**3. Proof of Theorem 1**

We work over $\mathbb{Z}_q$, where $q = \Theta(\frac{n^{1/2}}{\log^C n})$ is some prime, and observe that

$$
p(n) \le \Pr[M_n \text{ is singular over } \mathbb{Z}_q] := p'(n).
$$

Now, define the random variable

$$
K = |\mathrm{Ker}_{\mathbb{Z}_q}(M_n)|
$$

and observe that

$$
\mathbb{E}[K] = \sum_{\mathbf{a} \in \mathbb{Z}_q^n} \Pr[M \cdot \mathbf{a} = 0].
$$
Our goal is to show that $\mathbb{E}[K] \le 2 + o(1)$, and then, by Markov's inequality we obtain that

$$p'(n) = \Pr[K \ge q] \le (2 + o(1))/q$$

as desired.

To this end, let us split the above according to whether $\mathbf{a}$ is in $\mathcal{L}$ or not (recall that $\mathcal{L}$ is the set of all vectors $\mathbf{a} \in \mathbb{Z}_q^n$ with a level set of size at least $n - n/\log^2 n$), and by Observation 2 and Lemma 3 we obtain that

$$\mathbb{E}[K] = \sum_{\mathbf{a} \notin \mathcal{L}} \Pr[M \cdot \mathbf{a} = 0] + \sum_{\mathbf{a} \in \mathcal{L}} \Pr[M \cdot \mathbf{a} = 0] \\ \le 1 + \frac{1 + o(1)}{q^n} \cdot q^n + \binom{n}{n/\log^2 n} q^{n/\log^2 n+1} 2^{-n} = 2 + o(1).$$

This completes the proof of Theorem 1. □

## Acknowledgements

The author is grateful to Vishesh Jain and Van Vu for helpful comments on the manuscript. The author is also grateful to Jozsi Balogh for suggesting some simplifications and improvements for Propositions 4 and 5.

## References

[1] M. Campos, L. Mattos, R. Morris, N. Morrison, "On the singularity of random symmetric matrices", https://arxiv.org/abs/1904.11478, 2019.

[2] K. P. Costello, T. Tao, V. H. Vu, "Random symmetric matrices are almost surely nonsingular", Duke Math. J. 135 (2006), no. 2, p. 395-413.

[3] A. Ferber, V. Jain, "Singularity of random symmetric matrices—a combinatorial approach to improved bounds", Forum Math. Sigma 7 (2019), article no. e22.

[4] A. Ferber, V. Jain, K. Luh, W. Samotij, "On the counting problem in inverse Littlewood-Offord theory", https://arxiv.org/abs/1904.10425, 2019.

[5] J. Huang, "Invertibility of adjacency matrices for random $d$-regular graphs", https://arxiv.org/abs/1807.06465, 2018.

[6] H. H. Nguyen, "Inverse Littlewood-Offord problems and the singularity of random symmetric matrices", Duke Math. J. 161 (2012), no. 4, p. 545-586.

[7] R. Vershynin, "Invertibility of symmetric random matrices", Random Struct. Algorithms 44 (2014), no. 2, p. 135-182.