# 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!$$. However, I do not know, how to deal with the situation, where $$n < k < n^2 - n + 1$$.

Any help will be appreciated.

• One more easy case: if $k=n+1$ then you must have a permutation matrix plus one more $1$ (which can be anywhere). The permutation matrix is uniquely determined (all but one of the columns have only one $1$ and a permutation is determined by its values on all but one point) so that gives $n!(n^2-n)$ possibilities. – Eric Wofsey Dec 8 '18 at 8:49
• Another case: if $k = n^2 - n + 1$, there are $n-1$ zeros and they must necessarily be on different columns and different rows (otherwise there are 2 columns or 2 rows with all $1$s). So the $n-1$ zeros also define a permutation (of which one entry gets replaced by a $1$). Thus $M \le n! \times n$. For sufficiency: consider any subset of $c>1$ columns. Since $c > 1$, at least $1$ row has exactly one $0$ in it. Also, there exists a row with all $1$s in it. These $2$ rows cannot simultaneously sum to $0$. So any subset is independent and the matrix is non-singular. So $M = n! \ n$. – antkam Dec 12 '18 at 20:29
• If $k=n+2$, you can start with a permutation matrix $P$, i.e., $P_{i,j}=\delta_{j,\sigma(i)}$, where $\sigma$ is a permutation. Then you have to add two non-zero entries. So you have $\binom {n^2-n}{2}$ choices. But if one entry is $i,j$, you cannot choose the entry $\sigma^{-1}(j),\sigma(i)$ as the other entry, and this is the only exception, so you have $\frac{n^2-n}{2}$ invalid pairs. Then you have $$\binom {n^2-n}{2}-\frac{n^2-n}{2}=(n^2−n)(n^2−n−2)/2$$ valid pairs, and so the total number of non-singular matrices is $$n!(n^2−n)(n^2−n−2)/2.$$ – san Dec 14 '18 at 6:38
• It gets ugly very rapidly. If $k=n+3$ and you start from a permutation, you have to rule out adding the trhree additional 1's at $(i,j),(k,\sigma(i)),(\sigma^{-1}(j),\sigma(k))$, besides the previous restrictions. – san Dec 14 '18 at 7:09
• It might be useful : det(M) = 1 if and only if we can "include" (with a natural meaning) an odd number of permutations in M ; this is just a consequence of the determinant formula. In terms of permutations, you want to know when the number of permutations such that $\sigma(i) \in I_i$ for given sets $I_1, .. I_n$ is odd or not, or at least to count the odd ones. It might also be useful to consider the following problem : counting the invertible matrix which has exactly $\alpha_i$ nonzero termes in the $i-th$ column for all $1 \leq i \leq n$. – DLeMeur Jan 11 at 16:31

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.

• How do you reason that $i$ and $j$ can take $n^2-n$ values for the matrix to remain non-singular? – Will Fisher Dec 14 '18 at 0:10
• There aren't $n^2 - n - 1$ possibilities for $E_2$. Without loss you can imagine the original permutation to be the identity matrix, and the $E_1$ to have its $1$ at $(0,1)$. Then you cannot add another $1$ at $(1,0)$. I think this is the only prohibited spot, so $E_2$ has $n^2 - n - 2$ possibilities for the matrix to remain singular. But I don't think this kind of logic generalizes easily beyond $E_2$... – antkam Dec 14 '18 at 1:04
• The reasoning to justify that $i$ and $j$ can take $n^2-n$ values is that the permutation matrix contains $n$ non zero entries. And $i$ and $j$ can initialy take any $n^2$ value if we do not add any constraint but we don't want to add a 1 to another 1 because if would become a 0 in the sum of the matrices. So how many possibilities remain ? Well the initial number of positions minus the number of positions already filled with a non zero entry. Did you find this helpful ? – Nassoumo Dec 14 '18 at 11:08
• do you understand what "non-singular" mean? – antkam Dec 15 '18 at 3:57
• $\begin{pmatrix} 1 & 0 & 0 \\ 0 & 1 & 0 \\ 0 & 0 & 1 \end{pmatrix} \leadsto \begin{pmatrix} 1 & 1 & 0 \\ 0 & 1 & 0 \\ 0 & 0 & 1 \end{pmatrix} \leadsto \begin{pmatrix} 1 & 1 & 0 \\ 1 & 1 & 0 \\ 0 & 0 & 1 \end{pmatrix}$ which is singular. Similar constructions can be made for bigger matrix dimensions $n$. – Jakob B. Jan 9 at 19:41