# Probability that random nonnegative integer matrix is singular

Q. What is the probability that an $n \times n$ matrix, whose elements are independent uniformly random integers in $\{0,1,\ldots,k\}$, is singular?

For example, for $n=3$ and $k=2$, the first matrix below is singular and the second nonsingular: $$\left| \begin{array}{ccc} 2 & 1 & 2 \\ 0 & 2 & 0 \\ 0 & 2 & 0 \\ \end{array} \right| = 0 \;,$$ $$\left| \begin{array}{ccc} 0 & 2 & 0 \\ 0 & 0 & 1 \\ 2 & 2 & 2 \\ \end{array} \right| = 4 \;.$$ For $n=3$ and $k=1,2,...,14$, the probabilities that the matrices are singular are $338/512 = 66.0\%,$ $6891/19683 = 35.0\%,$ $49246/(4^9) = 18.8\%,$ $228737/(5^9) = 11.7\%,$ $716214/(6^9) =7.11\%,$ $... 259500567/(15^9) = 0.675\%$. See A059976.

I find experimentally that for $n=5$ and $k=2$, about 20.8% are singular. For $n=5$ and $k=10$, about .07% are singular. Here is a graph for $n=3$: Can results for these $(n,k)$-cases be derived from analogous results, e.g.,

Tao, Terence, and Van Vu. "On random $\pm 1$ matrices: Singularity and determinant." Random Structures & Algorithms 28.1 (2006): 1-23. (arXiv abstract.)

Voigt, Thomas, and Günter M. Ziegler. "Singular 0/1-matrices, and the hyperplanes spanned by random 0/1-vectors." Combinatorics, Probability and Computing 15.03 (2006): 463-471. (Cambridge link.) (PDF download pre-publication version.)

?

• For fixed $n$ and large $k$, the probability is known to go to zero. See for example this paper of Martin and Wong which contains more references: math.ubc.ca/~gerg/papers/downloads/AAIMHNIE.pdf . Also, the work of Rudelson and Vershynin arxiv.org/pdf/math/0703503.pdf which gives very general situations where the probability goes to zero. – Lucia Jun 29 '15 at 2:59
• While mathematically distinct from your problem, you can get a feel for the probability through an example like this: Given n randomly chosen vectors in {0,...,k}^n viewed as a cubic lattice, what is the likely hood that all n land on a face of the cube (the jth component has all 0 or all k for the n vectors)? – The Masked Avenger Jun 29 '15 at 3:48
• It has been conjectured that the probability that an $n\times n$ $\pm 1$ matrix $M$ is singular is asymptotic to the probability that two rows or columns of $M$ are equal up to sign (which is easy to compute). See users.uoa.gr/~apgiannop/matrices/Kahn_Komlos_Szemeredi_1995.pdf. Perhaps an analogue holds for matrices with entries $0,1,\dots,k$, e.g., two rows or columns being linearly dependent. – Richard Stanley Jun 29 '15 at 8:09
• @DouglasZare: Thanks, Douglas, for finding A059976 and other significant improvements to the question. – Joseph O'Rourke Jun 29 '15 at 19:31
• Corollary 1.2 of Bourgain-Vu-Wood arxiv.org/pdf/0905.0461.pdf gives an upper bound of $(1 / \sqrt{k+1}+o(1))^n$ in the regime where $k$ is fixed and $n$ goes to infinity. This can be compared with the trivial lower bound of $(1/(k+1))^n$, coming from the event that the first two rows (say) agree. – Terry Tao Jun 29 '15 at 20:32

In the situation where $n$ is fixed, and $k$ is large, an asymptotic formula for this probability was found by Yonatan Katznelson. From Theorem 1 of his paper (taking there ${\mathcal B}$ to be the box $[0,1]^{n^2}$) the chance of being singular is $$\sim C \frac{\log k}{k^n},$$ for a constant $C$. Katznelson considers more generally singular matrices with integer entries lying in a large dilate of a fixed region ${\mathcal B}$ in ${\Bbb R}^{n^2}$ (the box $[0,1]^{n^2}$ being the example of this question). His asymptotic is a little different from an earlier result (the difference is the $\log k$ factor) of Duke, Rudnick, and Sarnak who counted such matrices with a given non-zero determinant. Other references, dealing with variants of this problem, or in the regime where $k$ is fixed and $n$ is large may be found in the comments.