{
  "id": "2007.06318",
  "version": "v1",
  "published": "2020-07-13T11:28:41.000Z",
  "updated": "2020-07-13T11:28:41.000Z",
  "title": "The smallest singular value of random combinatorial matrices",
  "authors": [
    "Tuan Tran"
  ],
  "comment": "25 pages in the main body, 1 appendix",
  "categories": [
    "math.PR",
    "math.CO"
  ],
  "abstract": "Let $Q_n$ be a random $n\\times n$ matrix with entries in $\\{0,1\\}$ whose rows are independent vectors of exactly $n/2$ zero components. We show that the smallest singular value $s_n(Q_n)$ of $Q_n$ satisfies \\[ \\mathbb{P}\\Big\\{s_n(Q_n)\\le \\frac{\\varepsilon}{n^{3/2}}\\Big\\} \\le C\\varepsilon + 2 e^{-cn}, \\quad \\varepsilon \\ge 0. \\] This improves on earlier results of Ferber, Jain, Luh and Samotij, as well as Jain. In particular, for $\\varepsilon=0$, we obtain the first exponential bound in dimension for the singularity probability \\[ \\mathbb{P}\\big\\{Q_n \\,\\,\\text{is singular}\\big\\} \\le 2 e^{-cn}, \\] which is optimal up to the constant $c>0$. To overcome the lack of independence between entries of $Q_n$, we introduce an arithmetic-combinatorial invariant of a pair of vectors, which we call a Combinatorial Least Common Denominator (CLCD). We prove a small ball probability inequality for the combinatorial statistic $\\sum_{i=1}^{n}a_iv_{\\sigma(i)}$ in terms of the CLCD of the pair $(a,v)$, where $\\sigma$ is a uniformly random permutation of $\\{1,2,\\ldots,n\\}$ and $a:=(a_1,\\ldots,a_n), v:=(v_1,\\ldots,v_n)$ are real vectors. This inequality allows us to derive strong anti-concentration properties for the distance between a fixed row of $Q_n$ and the linear space spanned by the remaining rows, and prove the main result.",
  "revisions": [
    {
      "version": "v1",
      "updated": "2020-07-13T11:28:41.000Z"
    }
  ],
  "analyses": {
    "subjects": [
      "60B20"
    ],
    "keywords": [
      "smallest singular value",
      "random combinatorial matrices",
      "small ball probability inequality",
      "derive strong anti-concentration properties",
      "first exponential bound"
    ],
    "note": {
      "typesetting": "TeX",
      "pages": 25,
      "language": "en",
      "license": "arXiv",
      "status": "editable"
    }
  }
}