On the singularity probability of discrete random matrices (Q1048175): Difference between revisions

This paper considers an \(n\times n\) random matrix \(M_n\) with entries given by independent discrete random variables (not necessarily identically distributed and possibly dependent on \(n\)) and bounds the probability that such a matrix is singular. The bound is of the form \((c+o(1))^n\), but a more precise statement (given below) requires to define first the main assumption on the distributions of entries. For a constant \(0<p<1\), a \(\mathbb Z\)-valued random variable \(\alpha\) is \textit{\(p\)-bounded of exponent \(r\)} if (very vaguely): the probability of any individual value for \(\alpha\) does not exceed \(p\) and the norm of the \(r\)-th moment of the moment generating function of \(\alpha\) is bounded by the moment generating function for another \(\mathbb Z\)-valued random variable, called \(\beta\). In addition, \(\beta\) has to be symmetric and satisfy its own constraints on the probabilities of each individual value (including, now, also a lower bound). The \textit{\(p\)-boundedness of exponent \(r\)} property is also defined for \(\mathbb Z/Q\mathbb Z\)-valued random variables (for large primes \(Q\)), and finally extended to collections of random variables. Note that it is not required in the case of a collection that all the \(\alpha\) variables be identically distributed, only that the associated \(\beta\)s collectively take finitely many values, and that the \(\alpha\)s take values in some structured set (the main theorem being proved in the case of a generalized arithmetic progression). Under the assumption that the collection of entries of the growing \(M_n\) is \textit{\(p\)-bounded of exponent \(r\)}, the authors prove that the probability that \(M_n\) is singular is at most \((p^{1/r}+o(1))^n\). This result improves or generalizes known results in several cases: for iid fair coin flips [\textit{T. Tao} and \textit{V. Vu}, J. Am. Math. Soc. 20, No. 3, 603--628 (2007; Zbl 1116.15021)], for iid lazy coin flips, for matrices with some deterministic rows, etc. The paper also provides an interesting discussion, in Section~3.5, of the probability that a matrix with integer entries has rational eigenvalues [see also \textit{G. Martin} and \textit{E. Wong}, Am. Math. Monthly 116, No. 7, 588--597 (2009)]. The proofs refine the techniques of \textit{J. Kahn}, \textit{J. Komlós} and \textit{E. Szemerédi} [J. Am. Math. Soc. 8, No. 1, 223--240 (1995; Zbl 0829.15018)] and rely on the structure theorem of \textit{T. Tao} and \textit{V. Vu} [J. Am. Math. Soc. 20, No. 3, 603--628 (2007; Zbl 1116.15021)], to which much of this paper refers.