论文标题
稀疏随机矩阵的奇异性：简单的证明
Singularity of sparse random matrices: simple proofs
论文作者
论文摘要
考虑一个随机的$ n \ times n $零矩阵，带有“密度” $ p $，根据以下两个模型之一进行采样：要么每个条目都独立地视为具有概率$ p $的一个（“ bernoulli”型号），要么每行都是从所有长度 - $ n $ n $ nepther-n $ n $ Zero-One Vector中独立地均匀地采样的，与$ n $零vector $ pn $组合$ COMBIN（我们给出了简单的证明（本质上是最有可能的）事实，即在这两个模型中，如果$ \ min（p，1-p）\ geq（1+ \ varepsilon）\ log n/n $对于任何常数$ \ varepsilon> 0 $，那么我们的随机矩阵是非含量的，含有可能性$ 1-O（1- o（1）$。在Bernoulli模型中，这一事实已经是众所周知的，但是在组合模型中，这解决了Aigner-Horev和人的猜想。
Consider a random $n\times n$ zero-one matrix with "density" $p$, sampled according to one of the following two models: either every entry is independently taken to be one with probability $p$ (the "Bernoulli" model), or each row is independently uniformly sampled from the set of all length-$n$ zero-one vectors with exactly $pn$ ones (the "combinatorial" model). We give simple proofs of the (essentially best-possible) fact that in both models, if $\min(p,1-p)\geq (1+\varepsilon)\log n/n$ for any constant $\varepsilon>0$, then our random matrix is nonsingular with probability $1-o(1)$. In the Bernoulli model this fact was already well-known, but in the combinatorial model this resolves a conjecture of Aigner-Horev and Person.
