# The number of non-singular $n\times n$ matrices over $\mathbb{F}_2$ with exactly $k$ non-zero entries

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

• 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. Jun 12 '19 at 21:20
• This is now OEIS A309244 with credit to Weg and Stanley (also, I managed to work out the $n=5$ values). Jul 19 '19 at 15:57