Geodesic
On the singularity probability of random Bernoulli matrices
Tao, Terence1 ; Vu, Van2
1 Department of Mathematics, UCLA, Los Angeles, California 90095-1555
2 Department of Mathematics, Rutgers University, Piscataway, New Jersey 08854-8019
Journal of the American Mathematical Society, Tome 20 (2007) no. 3, pp. 603-628

Voir la notice de l'article provenant de la source American Mathematical Society

Let $n$ be a large integer and let $M_n$ be a random $n \times 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ós and Szemerédi, 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.
DOI : 10.1090/S0894-0347-07-00555-3

Tao, Terence 1 ; Vu, Van 2

1 Department of Mathematics, UCLA, Los Angeles, California 90095-1555
2 Department of Mathematics, Rutgers University, Piscataway, New Jersey 08854-8019 
@article{10_1090_S0894_0347_07_00555_3,
     author = {Tao, Terence and Vu, Van},
     title = {On the singularity probability of random {Bernoulli} matrices},
     journal = {Journal of the American Mathematical Society},
     pages = {603--628},
     publisher = {mathdoc},
     volume = {20},
     number = {3},
     year = {2007},
     doi = {10.1090/S0894-0347-07-00555-3},
     url = {http://geodesic.mathdoc.fr/articles/10.1090/S0894-0347-07-00555-3/}
}
TY  - JOUR
AU  - Tao, Terence
AU  - Vu, Van
TI  - On the singularity probability of random Bernoulli matrices
JO  - Journal of the American Mathematical Society
PY  - 2007
SP  - 603
EP  - 628
VL  - 20
IS  - 3
PB  - mathdoc
UR  - http://geodesic.mathdoc.fr/articles/10.1090/S0894-0347-07-00555-3/
DO  - 10.1090/S0894-0347-07-00555-3
ID  - 10_1090_S0894_0347_07_00555_3
ER  - 
%0 Journal Article
%A Tao, Terence
%A Vu, Van
%T On the singularity probability of random Bernoulli matrices
%J Journal of the American Mathematical Society
%D 2007
%P 603-628
%V 20
%N 3
%I mathdoc
%U http://geodesic.mathdoc.fr/articles/10.1090/S0894-0347-07-00555-3/
%R 10.1090/S0894-0347-07-00555-3
%F 10_1090_S0894_0347_07_00555_3
Tao, Terence; Vu, Van. On the singularity probability of random Bernoulli matrices. Journal of the American Mathematical Society, Tome 20 (2007) no. 3, pp. 603-628. doi: 10.1090/S0894-0347-07-00555-3

[1] Bilu, Yuri Structure of sets with small sumset Astérisque 1999

[2] Bilu, Y. F., Lev, V. F., Ruzsa, I. Z. Rectification principles in additive number theory Discrete Comput. Geom. 1998 343 353

[3] Cassels, J. W. S. An introduction to the geometry of numbers 1959

[4] Chang, Mei-Chu A polynomial bound in Freiman’s theorem Duke Math. J. 2002 399 419

[5] Erdã¶S, P. On a lemma of Littlewood and Offord Bull. Amer. Math. Soc. 1945 898 902

[6] Freä­Man, G. A. Foundations of a structural theory of set addition 1973

[7] Green, Ben, Ruzsa, Imre Z. Sets with small sumset and rectification Bull. London Math. Soc. 2006 43 52

[8] Halã¡Sz, G. Estimates for the concentration function of combinatorial number theory and probability Period. Math. Hungar. 1977 197 211

[9] John, Fritz Extremum problems with inequalities as subsidiary conditions 1948 187 204

[10] Kahn, Jeff, Komlã³S, Jã¡Nos, Szemerã©Di, Endre On the probability that a random ±1-matrix is singular J. Amer. Math. Soc. 1995 223 240

[11] Komlã³S, J. On the determinant of (0,1) matrices Studia Sci. Math. Hungar. 1967 7 21

[12] Komlã³S, J. On the determinant of random matrices Studia Sci. Math. Hungar. 1968 387 399

[13] Odlyzko, A. M. On subspaces spanned by random selections of ±1 vectors J. Combin. Theory Ser. A 1988 124 133

[14] Ruzsa, I. Z. Generalized arithmetical progressions and sumsets Acta Math. Hungar. 1994 379 388

[15] Ruzsa, Imre Z. An analog of Freiman’s theorem in groups Astérisque 1999

[16] Tao, Terence, Vu, Van On random ±1 matrices: singularity and determinant Random Structures Algorithms 2006 1 23

Cité par Sources :