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

Solution 1:

I think there is a way to generate the matrices : We start with a permutation matrix $P$. There are $n!$ permutations with each of them having $n$ non zero entries.

So now we are going to add $ E_1 $ such that $E_1$ equals zero everywhere except its $(i,j)$ entry. We want the sum to still be non-singular so $i$ and $j$ can take $n^2-n$ values in total. We can add a one to any entry that was previously zero.

If we want to add another matrix $E_2$ we have $n^2 - n -1$ possible entries for the non zero element. If we repeat the process $m$ times $Card(E_m)=n^2-(n+m-1)$. We continue until $m$ verifies that $m=k-n .$ And we have generated a non singular matrix with exactly $k$ non zero entries.

We can conclude that: $$M_k^n=(n!*(n^2-n)*(n^2-n-1)...*(n^2-k+1)).$$ We just multiplied the number of possibilites allowed at each step of the process. I'am not 100% sure so if anything seems out of touch please tell me. All this reasoning for $n<k<n^2 -n +1 $.