12
$\begingroup$

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$:


          Singular


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.)

?

$\endgroup$
  • 4
    $\begingroup$ 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. $\endgroup$ – Lucia Jun 29 '15 at 2:59
  • 2
    $\begingroup$ 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)? $\endgroup$ – The Masked Avenger Jun 29 '15 at 3:48
  • 6
    $\begingroup$ 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. $\endgroup$ – Richard Stanley Jun 29 '15 at 8:09
  • $\begingroup$ @DouglasZare: Thanks, Douglas, for finding A059976 and other significant improvements to the question. $\endgroup$ – Joseph O'Rourke Jun 29 '15 at 19:31
  • 5
    $\begingroup$ 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. $\endgroup$ – Terry Tao Jun 29 '15 at 20:32
4
$\begingroup$

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.

$\endgroup$

Your Answer

By clicking "Post Your Answer", you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.