Invertibility of random matrices: norm of the inverse

Abstract

Let A be an n × n matrix, whose entries are independent copies of a centered random variable satisfying the subgaussian tail estimate.We prove that the operator norm of A -1 does not exceed Cn 3/2 with probability close to 1. IntroductionLet A be an n × n matrix, whose entries are independent, identically distributed random variables.The spectral properties of such matrices, in particular invertibility, have been extensively studied (see, e.g.[M] and the survey [DS]).While A is almost surely invertible whenever its entries are absolutely continuous, the case of discrete entries is highly nontrivial.Even in the case, when the entries of A are independent random variables taking values ±1 with probability 1/2, the precise order of probability that A is singular is unknown.Komlós [K1], [K2] proved that this probability is o(1) as n → ∞.This result was improved by Kahn, Komlós and Szemerédi [KKS], who showed that this probability is bounded above by θ n for some absolute constant θ < 1.The value of θ has been recently improved in a series of papers by Tao and Vu [TV1], [TV2] to θ = 3/4 + o(1) (the conjectured value is θ = 1/2 + o(1)).However, these papers do not address the quantitative characterization of invertibility, namely the norm of the inverse matrix, considered as an operator from R n to R n .Random matrices are one of the standard tools in geometric functional analysis.They are used, in particular, to estimate the Banach-Mazur distance between finite-dimensional Banach spaces and to construct sections of convex bodies possessing certain properties.In all these questions condition number or the distortion A • A -1 plays the crucial role.Since the norm of A is usually highly concentrated, the distortion is determined by the norm of A -1 .The estimate of the norm of A -1 is known only in the case

Locations

• arXiv (Cornell University) - View - PDF
• Annals of Mathematics - View - PDF