0

I am teaching a class in linear algebra and I asked myself the following question: what is the chance to get an invertible matrix if I write a random one? My impulsive answer is "very likely". Of course, over the reals the probability is $1$ because singular matrices have codimension 1.

On the other hand, if we restrict to integer numbers and bound the maximum coefficient $N$ that appears, the answer becomes much more difficult ( see here). I then recalled there is a discrete case in which one manages to calculate a number. Indeed, over finite fields the fraction of $\mathbb{F}_q$- invertible matrices is (see here)

$$ \left ( 1- \frac{1}{q^n} \right ) \cdot \ldots \cdot \left ( 1- \frac{1}{q} \right ) \simeq 1- \frac{1}{q} = \frac{ q-1}{q} $$

This however excludes the matrices which have determinant multiple of $q$ but nonzero. We conclude that there are at least $(q-1)/q$ invertible matrices with nonnegative coefficients $< q$. My question is

Can you generalize this estimate for non prime $q$ ?

Andrea Marino
  • 1,944
  • 1
    The question is written in a confusing way, but it is asking for a lower bound on the number of matrices with entries in ${0, \ldots, m-1}$ that are nonsingular as real matrices (and points out that in the case of $m$ prime we get a bound by considering the finite field). – Sam Hopkins Jun 08 '22 at 20:47
  • The answer depends on $m$ and on the size of the matrix. Are we fixing one of these, and letting the other go to infinity? or are we letting both go to infinity in some precisely defined manner? or are we asking for a formula/estimate valid for all values of both variables? – Gerry Myerson Jun 08 '22 at 23:15
  • 1
    https://oeis.org/A055165 is "Number of invertible $n\times n$ matrices with entries equal to $0$ or $1$." The tabulation there only goes up to $n=8$, for which the entry is $10160459763342013440$. There are some links and references there that may be useful. – Gerry Myerson Jun 08 '22 at 23:24
  • 1
    https://oeis.org/A062801 tabulates "Number of $2\times2$ non-singular integer matrices with entries from ${,0,\dots,n,}$" up to $n=33$. The entry for $n=33$ is $1327606$. – Gerry Myerson Jun 08 '22 at 23:34
  • Related: https://mathoverflow.net/questions/20534/characterizing-invertible-matrices-with-0-1-entries and https://mathoverflow.net/questions/18636/number-of-invertible-0-1-real-matrices – Gerry Myerson Jun 08 '22 at 23:40
  • Yes, the question is somewhat vague... It was meant to be lighthearted :) I don't need this for any application, so a variant of the estimate is ok too! – Andrea Marino Jun 09 '22 at 22:05
  • Regarding the size of $m,n$: I'd like to have an estimate in both variables (like a taylor expansion in $1/m, 1/n$), but it's ok if we fix the size of the matrix and we let the bound for the coefficients go to infinity. – Andrea Marino Jun 09 '22 at 22:23
  • OK. So, have you had a look at the links I posted, and at the further links and references given at those links? Did you find anything useful that way? – Gerry Myerson Jun 10 '22 at 03:28
  • The link about 0,1 matrices is not that relevant to me, while the OEIS link for $2\times2$ matrices is nice. With a simple python program it's easy to see that the probability $p(n)$ of being non-singular with nonnegative coefficients up to $n$ is such that $p(n)/(1-1/n)$ is strictly decreasing and greater than $1$ (from some point on), so that one can conjecture that $p(n) \le (1+C)(1-1/n)$ for some positive constant $C<1/40$ (since for $n=31$ we get less than $1/40$. I'll look at the other links soon – Andrea Marino Jun 11 '22 at 21:57

0 Answers0