Comptes Rendus Mathématique

Olivier Lafitte

Unstable spectrum of a Rayleigh–Bénard system with variable viscosity

Sergio Guerrero

Takéo Takahashi

Controllability to trajectories of a Ladyzhenskaya model for a viscous incompressible fluid

Asaf Ferber

Comptes Rendus
Mathématique
Asaf Ferber
Singularity of random symmetric matrices – simple proof
Volume 359, issue 6 (2021), p. 743-747
<https://doi.org/10.5802/crmath.215>
© Académie des sciences, Paris and the authors, 2021.
Some rights reserved.
This article is licensed under the
Creative Commons Attribution 4.0 International License.
http://creativecommons.org/licenses/by/4.0/
Les Comptes Rendus. Mathématique sont membres du
Centre Mersenne pour l’édition scientifique ouverte
www.centre-mersenne.org
Comptes Rendus
Mathématique
2021, 359, n 6, p. 743-747
https://doi.org/10.5802/crmath.215
Probability theory / Probabilitées
Singularity of random symmetric matrices –
simple proof
Asaf Ferber∗, a
a 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 Mn denote an n ×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[Mn 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 Erdő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−ω(
p
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) = ( 12 +o(1))n , which, if true, is clearly best possible, as one can
check by calculating the probability that Mn has at least two identical rows/columns. Therefore,
∗Corresponding author.
ISSN (electronic) : 1778-3569 https://comptes-rendus.academie-sciences.fr/mathematique/
744 Asaf Ferber
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( logC n
n1/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, Zq , where q is a carefully chosen
prime. Let K := |K er (M)| be the random variable that outputs the size of the kernel of M over
Zq , and we will show, using an elegant Fourier-type argument, that E[K ] ≤ 2+o(1). Then, observe
that if M is singular, then K ≥ q , so by Markov’s inequality we obtain that the probability to be
singular is at most 2+o(1)q . In fact, the same argument gives a bound of
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 a ∈Znq , and let r ∈Zq . The r th level set of a is
Lr (a) = {i ∈ [n]|ai = r } .
For convenience, we will use the notation L 6=r := [n]\Lr , and we also set m(a) to be the size of the
largest level set.
Finally, we let
L :=
{
a ∈Znq
∣∣∣m(a) ≥ n −n/log2 n}
be the set of all a ∈Znq with some level set of size larger than n − nlog2 n .
Now we are ready to state our auxiliary lemmas. First, let us make the following simple (but
yet, useful) observation:
Observation 2. Let a ∈Znq \ {0}. Then,
Pr[Mn ·a = 0] ≤ 2−n .
Proof. Indeed, let 1 ≤ j ≤ n be some coordinate for which a j 6= 0 mod q , and expose all the
entries of Mn but the entries in the j th row and column. It is now straightforward to see that we
obtain the desired. 
The following lemma is basically the key lemma for our proof. Roughly speaking, it asserts that
if a ∉L, then Mn ·a is (more or less) equally likely to be any vector from Znq .
Lemma 3. Let q be a prime such that q =O(n1/2/logC n). Let a ∉L, and v ∈Znq . Then,
Pr[Mn ·a = v ] = 1+o(1)
qn
.
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 a ∉L and let ` ∈Znq be a vector with support of size s < n2log2 n . Then, there are
at least sn
2log2 n
pairs 1 ≤ i < j ≤ n for which `i a j +` j ai 6= 0 mod q.
C. R. Mathématique — 2021, 359, n 6, 743-747
Asaf Ferber 745
Proof. Since a ∉L, we have that |L 6=0(a)| ≥ nlog2 n and therefore we have that J := L0(`)∩L 6=0(a) is
of size at least |L 6=0(a)|− s ≥ n2log2 n . Now, observe that for every i ∈ L 6=0(`) and j ∈ J we have that
`i a j +` j ai = `i a j 6= 0 mod q . In particular, there are at least∣∣L 6=0(`)∣∣ · |J | ≥ sn
2log2 n
such pairs. This completes the proof. 
Proposition 5. Let a ∉L and let ` ∈Znq be a vector with support of size s ≥ n2log2 n . Then, there are
at least min{s2/20, sn
2log2 n
} pairs 1 ≤ i < j ≤ n for which `i a j +` j ai 6= 0 mod q.
Proof. We split into two cases:
Case 1. |L0(a) ∩ L 6=0(`)| ≥ s/2. In this case, let I := L0(a) ∩ L 6=0(`) and J = L 6=0(a). Clearly, for
all i ∈ I and j ∈ J we have `i a j + ` j ai = `i a j 6= 0 mod q , and therefore, there are at least
|I | · |J | ≥ sn
2log2 n
such pairs.
Case 2. |L 6=0(a)∩ L 6=0(`)| ≥ s/2. For all r ∈ Zq we define Jr := Lr (a)∩ L 6=0(`), and observe that
s′ := ∑r 6=0 |Jr | ≥ s/2. Next, define an auxilairy graph G on vertex set V = L 6=0(a)∩L 6=0(`), where
two vertices i , j ∈ V are connected by an edge if and only if `i a j + ` j ai = 0 mod q . We show
that G is triangle free, and therefore, by Mantel’s theorem we have e(G) ≤ 12 ·
(|V |
2
)
. In particular,
it means that there are at least 12 ·
(|V |
2
) ≥ s2/20 pairs i , j ∈ V for which `i a j +` j ai 6= 0 mod q as
desired.
To this end, let i , j ,k ∈V be three distinct vertices. We distinguish between three cases:
Case 2.1. i , j ,k ∈ Jr for some r 6= 0. Observe that `i a j +` j ai = r (`i +` j ), and therefore, if it equals
0 mod q , then we have `i = −` j . Now, without loss of generality we can assume that `k 6= −` j
(the case `k 6= ` j is treated similarly). Then,
`k a j +` j ak = r
(
`k +` j
) 6= 0 mod q.
Case 2.2. i , j ∈ Jr1 and k ∈ Jr2 for some r1 6= r2 and both are not 0 mod q . If `i a j + ` j ai =
r1(`i +` j ) 6= 0 mod q then we are done. Otherwise, we have that `i = −` j . Now, consider the
expressions
`i ak +`k ai = `i r2 +`k r1, and ` j ak +`k a j =−`i r2 +`k r1.
Clearly, at least one of them is not 0 mod q .
Case 2.3. i ∈ Jr1 , j ∈ Jr2 and k ∈ Jr3 for some distinct r1,r2, and r3, all are not 0 mod q . Suppose
that we have
`i a j +` j ai = `i ak +`k ai = 0 mod q.
(if not, then we are done).
In particular, it means that
`i =
−` j ai
a j
= −` j r1
r2
,
and that
`i = −`k r1
r3
.
These two identities yield that
0 mod q = `k r2 −` j r3 = `k a j −` j ak ,
and in particular, since ` j ak 6= 0 mod q , we have that
`k a j +` j ak 6= 0 mod q
as desired. This completes the proof. 
C. R. Mathématique — 2021, 359, n 6, 743-747
746 Asaf Ferber
Now we are ready to prove Lemma 3.
Proof. Let a ∉L, let v ∈Znq , and let eq (x) = e
2πi x
q . Recalling that mi j = m j i , observe that
Pr[M ·a = v] = E [δ0 (M ·a − v)]
= 1
qn
∑
`∈Znq
E
[
eq
(
`T (Mn a − v)
)]
= 1
qn
∑
`∈Znq
eq
(−`T v) ·E[eq
(∑
i , j
mi j`i a j
)]
= 1
qn
∑
`∈Znq
eq
(−`T v) ∏
1≤ i < j ≤n
E
[
eq
(
mi j
(
`i a j +` j ai
))] n∏
i=1
E
[
eq (mi i`i ai )
]
= 1
qn
+ 1
qn
∑
` 6=0∈Znq
eq
(−`T v) ∏
1≤ i < j ≤n
cos
(
2π
q
(
`i a j +` j ai
)) n∏
i=1
cos
(
2π`i ai
q
)
.
This implies that∣∣∣∣Pr[M ·a = v]− 1qn
∣∣∣∣≤ 1qn ∑` 6=0∈Znq
∏
1≤ i < j ≤n
∣∣∣∣cos(2πq (`i a j +` j ai )
)∣∣∣∣ .
Therefore, it is enough to show that
Er r or := ∑
` 6=0∈Znq
∏
1≤ i < j ≤n
∣∣∣∣cos(2πq (`i a j +` j ai )
)∣∣∣∣= o(1).
Using the following simple estimate ∣∣∣∣cos πmq
∣∣∣∣≤ e− 2q2 ,
which holds for all m 6= 0 mod q, we can upper bound
Er r or ≤ ∑
`∈Znq \{0}
e−2 ·N (`, a)/q
2
,
where N (`, a) = |{(i , j ) ∈ [n]2 : i < j and `i a j +` j ai 6= 0 mod q}|.
Finally, to complete the proof, we split the above sum according to the size of the support of `,
and using Propositions 4 and 5 we obtain that
Er r or ≤
n∑
s=1
(
n
s
)
q s e−sn/q
2 log2 n +
n∑
s=n/log2 n
(
n
s
)
(q −1)s e−s2/20q2 ,
which can be easily seen to be o(1) as long as q =O(n1/2/logC n), for C ≥ 3/2. This completes the
proof. 
3. Proof of Theorem 1
We work over Zq , where q =Θ( n1/2logC n ) is some prime, and observe that
p(n) ≤ Pr[Mn is singular over Zq] := p ′(n).
Now, define the random variable
K =
∣∣∣K erZq (Mn)∣∣∣
and observe that
E[K ] = ∑
a∈Znq
Pr[M ·a = 0] .
C. R. Mathématique — 2021, 359, n 6, 743-747
Asaf Ferber 747
Our goal is to show that E[K ] ≤ 2+o(1), and then, by Markov’s inequality we obtain that
p ′(n) = Pr[K ≥ q]≤ (2+o(1))/q
as desired.
To this end, let us split the above according to whether a is in L or not (recall that L is the set of
all vectors a ∈Znq with a level set of size at least n−n/log2 n), and by Observation 2 and Lemma 3
we obtain that
E[K ] = ∑
a∉L
Pr[M ·a = 0]+ ∑
a∈L
Pr[M ·a = 0]
≤ 1+ 1+o(1)
qn
·qn +
(
n
n/log2 n
)
qn/log
2 n+12−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.
C. R. Mathématique — 2021, 359, n 6, 743-747


Singularity of random symmetric matrices – simple proof

Konstantin M. Dyakonov

A Rudin–de Leeuw type theorem for functions with spectral gaps

Christophe Eyral

Tadeusz Mostowski

Piotr Pragacz

On some properties of the Łojasiewicz exponent

Óscar Domínguez

Mario Milman

Sparse Brudnyi and John–Nirenberg Spaces

Alexandre Baldare

Rémi Côme

Victor Nistor

Fredholm conditions for operators invariant with respect to compact Lie group actions

Fatih Say

First-order general differential equation for multi-level asymptotics at higher levels and recurrence relationship of singulants

Takahiro Inayama

From Hörmander’s $L^2$-estimates to partial positivity

Andrea T. Ricolfi

The equivariant Atiyah class

Not a member yet