The Littlewood–Offord problem and invertibility of random matrices

详细信息    查看全文

• 作者：Mark Rudelson ; Roman Vershynin
• 关键词：Random matrices ; Singular values ; Condition number ; Small ball probability ; Littlewood– ; Offord problem
• 刊名：Advances in Mathematics
• 出版年：2008
• 出版时间：1 June 2008
• 年：2008
• 卷：218
• 期：2
• 页码：600-633
• 全文大小：282 K

文摘

We prove two basic conjectures on the distribution of the smallest singular value of random n×n matrices with independent entries. Under minimal moment assumptions, we show that the smallest singular value is of order n^−1/2, which is optimal for Gaussian matrices. Moreover, we give a optimal estimate on the tail probability. This comes as a consequence of a new and essentially sharp estimate in the Littlewood–Offord problem: for i.i.d. random variables X_k and real numbers a_k, determine the probability p that the sum ∑_ka_kX_k lies near some number v. For arbitrary coefficients a_k of the same order of magnitude, we show that they essentially lie in an arithmetic progression of length 1/p.