{
  "id": "math/0703503",
  "version": "v2",
  "published": "2007-03-16T21:58:20.000Z",
  "updated": "2008-01-31T22:28:22.000Z",
  "title": "The Littlewood-Offord Problem and invertibility of random matrices",
  "authors": [
    "Mark Rudelson",
    "Roman Vershynin"
  ],
  "comment": "Introduction restructured, some typos and minor errors corrected",
  "categories": [
    "math.PR",
    "math.FA"
  ],
  "abstract": "We prove two basic conjectures on the distribution of the smallest singular value of random n times 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 of a_k X_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.",
  "revisions": [
    {
      "version": "v2",
      "updated": "2008-01-31T22:28:22.000Z"
    }
  ],
  "analyses": {
    "subjects": [
      "15A52",
      "11P70"
    ],
    "keywords": [
      "littlewood-offord problem",
      "random matrices",
      "smallest singular value",
      "invertibility",
      "minimal moment assumptions"
    ],
    "note": {
      "typesetting": "TeX",
      "pages": 0,
      "language": "en",
      "license": "arXiv",
      "status": "editable",
      "adsabs": "2007math......3503R"
    }
  }
}