On the least singular value of random symmetric matrices

Hoi H Nguyen (University of Pennsylvania)

Abstract


Let $F_n$ be an $n$ by $n$ symmetric matrix whose entries are bounded by $n^{\gamma}$ for some $\gamma>0$. Consider a randomly perturbed matrix $M_n=F_n+X_n$, where $X_n$ is a {\it random symmetric matrix} whose upper diagonal entries $x_{ij}, 1\le i\le j,$ are iid copies of a random variable $\xi$. Under a very general assumption on $\xi$, we show that for any $B>0$ there exists $A>0$ such that $\mathbb{P}(\sigma_n(M_n)\le n^{-A})\le n^{-B}$.

Full Text: Download PDF | View PDF online (requires PDF plugin)

Pages: 1-19

Publication Date: July 15, 2012

DOI: 10.1214/EJP.v17-2165

References

  • Barvinok, Alexander. Polynomial time algorithms to approximate permanents and mixed discriminants within a simply exponential factor. Random Structures Algorithms 14 (1999), no. 1, 29--61. MR1662270
  • Costello, Kevin P.; Tao, Terence; Vu, Van. Random symmetric matrices are almost surely nonsingular. Duke Math. J. 135 (2006), no. 2, 395--413. MR2267289
  • Costello, Kevin P.; Vu, Van. Concentration of random determinants and permanent estimators. SIAM J. Discrete Math. 23 (2009), no. 3, 1356--1371. MR2556534
  • Erdësh, L. Universality of Wigner random matrices: a survey of recent results. (Russian) Uspekhi Mat. Nauk 66 (2011), no. 3(399), 67--198; translation in Russian Math. Surveys 66 (2011), no. 3, 507--626 MR2859190
  • Erdős, László; Schlein, Benjamin; Yau, Horng-Tzer. Wegner estimate and level repulsion for Wigner random matrices. Int. Math. Res. Not. IMRN 2010, no. 3, 436--479. MR2587574
  • Erdös, P. On a lemma of Littlewood and Offord. Bull. Amer. Math. Soc. 51, (1945). 898--902. MR0014608
  • Friedland, Shmuel; Rider, Brian; Zeitouni, Ofer. Concentration of permanent estimators for certain large matrices. Ann. Appl. Probab. 14 (2004), no. 3, 1559--1576. MR2071434
  • Guionnet, A.; Zeitouni, O. Concentration of the spectral measure for large matrices. Electron. Comm. Probab. 5 (2000), 119--136 (electronic). MR1781846
  • Halász, G. Estimates for the concentration function of combinatorial number theory and probability. Period. Math. Hungar. 8 (1977), no. 3-4, 197--211. MR0494478
  • Kleitman, Daniel J. On a lemma of Littlewood and Offord on the distributions of linear combinations of vectors. Advances in Math. 5 1970 155--157 (1970). MR0265923
  • Littlewood, J. E.; Offord, A. C. On the number of real roots of a random algebraic equation. III. Rec. Math. [Mat. Sbornik] N.S. 12(54), (1943). 277--286. MR0009656
  • H. Nguyen, phInverse Littlewood-Offord problems and the singularity of random symmetric matrices, Duke Mathematics Journal Vol. 161, 4 (2012), 545-586. skip .05in
  • H. Nguyen, phA continuous variant of the inverse Littlewood-Offord problem for quadratic forms, to appear in Contribution to Discrete Mathematics. skip .05in
  • Nguyen, Hoi; Vu, Van. Optimal inverse Littlewood-Offord theorems. Adv. Math. 226 (2011), no. 6, 5298--5319. MR2775902
  • Odlyzko, A. M. On subspaces spanned by random selections of $\pm 1$ vectors. J. Combin. Theory Ser. A 47 (1988), no. 1, 124--133. MR0924455
  • Rudelson, Mark; Vershynin, Roman. The Littlewood-Offord problem and invertibility of random matrices. Adv. Math. 218 (2008), no. 2, 600--633. MR2407948
  • Smale, Steve. On the efficiency of algorithms of analysis. Bull. Amer. Math. Soc. (N.S.) 13 (1985), no. 2, 87--121. MR0799791
  • Spielman, Daniel A.; Teng, Shang-Hua. Smoothed analysis of algorithms: why the simplex algorithm usually takes polynomial time. J. ACM 51 (2004), no. 3, 385--463 (electronic). MR2145860
  • Tao, Terence; Vu, Van. On random $\pm1$ matrices: singularity and determinant. Random Structures Algorithms 28 (2006), no. 1, 1--23. MR2187480
  • Tao, Terence; Vu, Van. On the singularity probability of random Bernoulli matrices. J. Amer. Math. Soc. 20 (2007), no. 3, 603--628. MR2291914
  • Tao, Terence; Vu, Van. Random matrices: the circular law. Commun. Contemp. Math. 10 (2008), no. 2, 261--307. MR2409368
  • Tao, Terence; Vu, Van. From the Littlewood-Offord problem to the circular law: universality of the spectral distribution of random matrices. Bull. Amer. Math. Soc. (N.S.) 46 (2009), no. 3, 377--396. MR2507275
  • Tao, Terence; Vu, Van H. Inverse Littlewood-Offord theorems and the condition number of random discrete matrices. Ann. of Math. (2) 169 (2009), no. 2, 595--632. MR2480613
  • Tao, Terence; Vu, Van. Smooth analysis of the condition number and the least singular value. Math. Comp. 79 (2010), no. 272, 2333--2352. MR2684367
  • Tao, Terence; Vu, Van. Random matrices: universality of local eigenvalue statistics. Acta Math. 206 (2011), no. 1, 127--204. MR2784665
  • Tao, Terence; Vu, Van. Additive combinatorics. Cambridge Studies in Advanced Mathematics, 105. Cambridge University Press, Cambridge, 2006. xviii+512 pp. ISBN: 978-0-521-85386-6; 0-521-85386-9 MR2289012
  • R. Vershynin, Invertibility of symmetric random matrices, to appear in Random Structure and Algorithms.
Bookmark and Share


Creative Commons License
This work is licensed under a Creative Commons Attribution 3.0 License.