9
$\begingroup$

Suppose $M_{n}^{k}$ is the number of non-singular $n\times n$ matrices over $\mathbb{F}_2$, that have exactly $k$ non-zero entries. Is there some sort of formula to calculate $M_n^k$?

If $k < n$ or $k > n^2 - n + 1$, then $M_n^k = 0$ by pigeonhole principle (in the first case we always have at least one zero row, in the second case we always have at least two identical rows).

If $k = n$, then all such non-singular matrices have to be permutation matrices. Thus $M_n^n = n!$.

If $k = n + 1$, then the matrix differs from a permutation matrix by one additional non-zero entry. Thus $M_n^{n + 1} =n!n(n-1)$.

If $k = n^2 - n + 1$, then there are exactly $n - 1$ zeroes which are required to be in different rows and different columns. Thus, $M_n^{n^2 - n + 1} = n!n$.

However, I do not know, how to deal with the situation, where $n + 1 < k < n(n - 1)$.

Improve this question
$\endgroup$
2
  • 5
    $\begingroup$ An exact answer looks intractable to me. Perhaps one can determine the limiting distribution (after proper rescaling). For $n=3$ and $n=4$ the generating functions are $6x^3(3x^4+6x^3+12x^2+6x+1)$ and $24x^4(4x^9+25x^8+72x^7+108x^6+208x^5+198x^4+152x^3+60x^2+12x$ $+1)$. Note that $M_n^k$ is always divisible by $n!$ since a nonsingular matrix has distinct rows. $\endgroup$
    – Richard Stanley
    Commented Jun 12, 2019 at 21:20
  • $\begingroup$ This is now OEIS A309244 with credit to Weg and Stanley (also, I managed to work out the $n=5$ values). $\endgroup$
    – Brian Hopkins
    Commented Jul 19, 2019 at 15:57

0

Reset to default

You must log in to answer this question.