کد مقاله | کد نشریه | سال انتشار | مقاله انگلیسی | نسخه تمام متن |
---|---|---|---|---|
5778597 | 1633778 | 2017 | 58 صفحه PDF | دانلود رایگان |
عنوان انگلیسی مقاله ISI
Invertibility of sparse non-Hermitian matrices
ترجمه فارسی عنوان
معکوس کردن ماتریس های غیر ارمیتی ناقص
دانلود مقاله + سفارش ترجمه
دانلود مقاله ISI انگلیسی
رایگان برای ایرانیان
کلمات کلیدی
موضوعات مرتبط
مهندسی و علوم پایه
ریاضیات
ریاضیات (عمومی)
چکیده انگلیسی
We consider a class of sparse random matrices of the form An=(ξi,jδi,j)i,j=1n, where {ξi,j} are i.i.d. centered random variables, and {δi,j} are i.i.d. Bernoulli random variables taking value 1 with probability pn, and prove a quantitative estimate on the smallest singular value for pn=Ω(logâ¡nn), under a suitable assumption on the spectral norm of the matrices. This establishes the invertibility of a large class of sparse matrices. For pn=Ω(nâα) with some αâ(0,1), we deduce that the condition number of An is of order n with probability tending to one under the optimal moment assumption on {ξi,j}. This in particular, extends a conjecture of von Neumann about the condition number to sparse random matrices with heavy-tailed entries. In the case that the random variables {ξi,j} are i.i.d. sub-Gaussian, we further show that a sparse random matrix is singular with probability at most expâ¡(âcnpn) whenever pn is above the critical threshold pn=Ω(logâ¡nn). The results also extend to the case when {ξi,j} have a non-zero mean. We further find quantitative estimates on the smallest singular value of the adjacency matrix of a directed ErdÅs-Réyni graph whenever its edge connectivity probability is above the critical threshold Ω(logâ¡nn).
ناشر
Database: Elsevier - ScienceDirect (ساینس دایرکت)
Journal: Advances in Mathematics - Volume 310, 13 April 2017, Pages 426-483
Journal: Advances in Mathematics - Volume 310, 13 April 2017, Pages 426-483
نویسندگان
Anirban Basak, Mark Rudelson,