2020/07/13 by Tran, Tuan
#60B20 #Combinatorics (math.CO) #FOS: Mathematics #Probability (math.PR)
paper · doi:10.48550/arxiv.2007.06318
Let Qn be a random n× n matrix with entries in \0,1\ whose rows are independent vectors of exactly n/2 zero components. We show that the smallest singular value sn(Qn) of Qn satisfies ℙ\sn(Qn)≤ (ε)/(√(n))\ ≤ Cε + 2 e-cn ∀ ε ≥ 0, which is optimal up to the constants C,c>0. This improves on earlier results of Ferber, Jain, Luh and Samotij, as well as Jain. In particular, for ε=0, we obtain the first exponential bound in dimension for the singularity probability ℙ\Qn is singular\ ≤ 2 e-cn. To overcome the lack of independence between entries of Qn, we introduce an arithmetic-combinatorial invariant of a pair of vectors, which we call a Combinatorial Least Common Denominator (CLCD). We prove a small ball probability inequality for the combinatorial statistic ∑i=1naivσ(i) in terms of the CLCD of the pair (a,v), where σ is a uniformly random permutation of \1,2,…,n\ and a:=(a1,…,an), v:=(v1,…,vn) are real vectors. This inequality allows us to derive strong anti-concentration properties for the distance between a fixed row of Qn and the linear space spanned by the remaining rows, and prove the main result.