论文标题
随机组合矩阵的最小奇异值
The smallest singular value of random combinatorial matrices
论文作者
论文摘要
令$ q_n $为一个随机的$ n \ times n $矩阵，其中的条目为$ \ {0,1 \} $，其行是恰好$ n/2 $零组件的独立向量。我们表明，最小的单数值$ s_n（q_n）$ q_n $满足\ [\ mathbb {p} \ big \ {s_n（q_n（q_n）\ le \ frac {\ frac {\ varepsilon} {\ sqrt {\ sqrt {n}}} \ quad \ forall \ varepsilon \ ge 0，\]，它是常数$ c，c> 0 $的最佳功能。这改善了Ferber，Jain，Luh和Samotij以及Jain的早期结果。特别是，对于$ \ varepsilon = 0 $，我们获得了第一个指数限制的奇异性概率\ [\ mathbb {p} \ big \ big \ \ {q_n \，\，\，\，\ text {as singular} \ big \} \ big \} \ big \} \ le 2 e^{ - cn $ cn $ priend priends $ priend comportions $ sclience comportions uctions cliend wissions。一对矢量的算术算术组合不变，我们称之为组合最少共同点（CLCD）。我们证明了组合统计量$ \ sum_ {i = 1}^{n} a_iv_ {σ（i）} $的小球概率不平等，从一对$（a，v）$的角度来看$ a：=（a_1，\ ldots，a_n），v：=（v_1，\ ldots，v_n）$是真实的向量。这种不等式使我们能够为$ q_n $的固定行与剩余行跨越的线性空间之间的距离得出强大的抗浓缩属性，并证明了主要结果。
Let $Q_n$ be a random $n\times 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 $s_n(Q_n)$ of $Q_n$ satisfies \[ \mathbb{P}\Big\{s_n(Q_n)\le \frac{\varepsilon}{\sqrt{n}}\Big\} \le C\varepsilon + 2 e^{-cn} \quad \forall \varepsilon \ge 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 $\varepsilon=0$, we obtain the first exponential bound in dimension for the singularity probability \[ \mathbb{P}\big\{Q_n \,\,\text{is singular}\big\} \le 2 e^{-cn}.\] To overcome the lack of independence between entries of $Q_n$, 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 $\sum_{i=1}^{n}a_iv_{σ(i)}$ in terms of the CLCD of the pair $(a,v)$, where $σ$ is a uniformly random permutation of $\{1,2,\ldots,n\}$ and $a:=(a_1,\ldots,a_n), v:=(v_1,\ldots,v_n)$ are real vectors. This inequality allows us to derive strong anti-concentration properties for the distance between a fixed row of $Q_n$ and the linear space spanned by the remaining rows, and prove the main result.
