0
$\begingroup$

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

Improve this question
$\endgroup$
9
  • 1
    $\begingroup$ 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). $\endgroup$
    – Sam Hopkins
    Jun 8, 2022 at 20:47
  • $\begingroup$ 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? $\endgroup$
    – Gerry Myerson
    Jun 8, 2022 at 23:15
  • 1
    $\begingroup$ 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. $\endgroup$
    – Gerry Myerson
    Jun 8, 2022 at 23:24
  • 1
    $\begingroup$ 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$. $\endgroup$
    – Gerry Myerson
    Jun 8, 2022 at 23:34
  • $\begingroup$ Related: mathoverflow.net/questions/20534/… and mathoverflow.net/questions/18636/… $\endgroup$
    – Gerry Myerson
    Jun 8, 2022 at 23:40

0

Reset to default

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.