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

Any help will be appreciated.

|cite|improve this question
$\endgroup$
  • 3
    $\begingroup$ 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. $\endgroup$ – Eric Wofsey Dec 8 '18 at 8:49
  • 1
    $\begingroup$ 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$. $\endgroup$ – antkam Dec 12 '18 at 20:29
  • 3
    $\begingroup$ 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. $$ $\endgroup$ – san Dec 14 '18 at 6:38
  • 2
    $\begingroup$ 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. $\endgroup$ – san Dec 14 '18 at 7:09
  • 1
    $\begingroup$ 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$. $\endgroup$ – DLeMeur Jan 11 at 16:31
0
$\begingroup$

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

|cite|improve this answer
$\endgroup$
  • $\begingroup$ How do you reason that $i$ and $j$ can take $n^2-n$ values for the matrix to remain non-singular? $\endgroup$ – Will Fisher Dec 14 '18 at 0:10
  • $\begingroup$ 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$... $\endgroup$ – antkam Dec 14 '18 at 1:04
  • $\begingroup$ 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 ? $\endgroup$ – Nassoumo Dec 14 '18 at 11:08
  • $\begingroup$ do you understand what "non-singular" mean? $\endgroup$ – antkam Dec 15 '18 at 3:57
  • $\begingroup$ $\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$. $\endgroup$ – Jakob B. Jan 9 at 19:41

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.