On the singularity probability of random Bernoulli matrices
On the singularity probability of random Bernoulli matrices
复制标题
DOI：
10.1090/s0894-0347-07-00555-3
复制
发表时间：
2005-01
影响因子：
3.9
通讯作者：
T. Tao;V. Vu
中科院分区：
文献类型：
--
作者：
T. Tao;V. Vu
设$n$是一个大整数，$M_n$是一个随机的$n$乘$n$矩阵，其元素是独立同分布的。Bernoulli随机变量（每个条目是$\pm 1$，概率为1/2）。我们证明了$M_n$是奇异的概率至多为$（3/4 +o（1））^n$，改进了Kahn，Koml\'os和Szemer\' edi的早期估计，以及作者的早期工作.关键的新成分是应用Freiman型逆定理和其他工具从添加剂组合。
Let $n$ be a large integer and $M_n$ be a random $n$ by $n$ matrix whose entries are i.i.d. Bernoulli random variables (each entry is $\pm 1$ with probability 1/2). We show that the probability that $M_n$ is singular is at most $(3/4 +o(1))^n$, improving an earlier estimate of Kahn, Koml\'os and Szemer\'edi, as well as earlier work by the authors. The key new ingredient is the applications of Freiman type inverse theorems and other tools from additive combinatorics.