# Number of full-rank binary matrices with no rows of weight 1

For $m > n$, I want to calculate the number of binary matrices with $m$ rows and $n$ columns for which two conditions hold:

• the rank of a matrix is $n$ (i.e. it is full-rank, as $m > n$);
• there are no rows with a single 1 - in other words, there are no rows of Hamming weight 1.

I need either closed formula or some polynomial-time algorithm to calculate this number (for example via some recurrent formula).

Note. "Binary" means that matrix is considered over Galois field $\mathbb F_2$.

• Can you use inclusion-exclusion? – Anthony Quas Mar 15 '17 at 18:27
• I am not sure I see how to use it... – Yauhen Yakimenka Mar 15 '17 at 18:31
• The number of full rank matrices with no weight 1 rows is (the total number of full rank matrices) - (the number of full rank matrices with one weight 1 row) + (the number of full rank matrices with two weight 1 rows) ... – Anthony Quas Mar 15 '17 at 18:39
• I think calculating the number of full-rank matrices with k rows of weight 1 (for k=1, 2, ...) is harder than the original question (which was for k=0). Or do I miss something? – Yauhen Yakimenka Mar 15 '17 at 18:53
• YauhenYakimenka: I think @AnthonyQuas is thinking of Waring's formula by which you can calculate exactly k rows of weight 1 occuring in the binary matrix. You can also read my answer here: stats.stackexchange.com/questions/132944/… – Henry.L Mar 15 '17 at 19:17

First let us count the number of matrices $m\times n$ over $\mathbb F_2$ of full rank (without the second restriction). Let $r_i$ ($i=1,2,\dots,m$) be the $i$-th row of such a matrix, $V_i=\langle r_1,\dots,r_i\rangle$ be the vector space spanned by the first $i$ rows, and $d_i = \dim V_i$. Then $|V_i|=2^{d_i}$, and $d_0=0, d_1=1, d_2, \dots, d_{m-1}, d_m=n$ forms a nondecreasing sequence.

Now, let us pick the set of indices $I\subset [m]:=\{1,2,\dots,m\}$ such that $d_i=d_{i-1}+1$ for all $i\in I$. Clearly, we have $|I|=n$, $\{ d_i\mid i\in I\}=[n]$, and $\{ d_{i-1}\mid i\in I\}=\{0,1,\dots,n-1\}$. The rows with indices from $I$ form a nondegenerate $n\times n$ matrix, which we denote $M_I$. Furthermore, for every $i\in[m]$, we have $r_i\notin V_{i-1}$ if $i\in I$, and $r_i\in V_{i-1}$ if $i\notin I$.

The number of matrices $M_I$ can easily computed: its rows are formed by arbitrary elements of the complements $\mathbb F_2^n \setminus V_{i-1}$ of size $2^n - 2^{d_{i-1}}$ (where $i\in I$), and so the number of such matrices is $$f_n = \prod_{i\in I} (2^n - 2^{d_{i-1}})=\prod_{j=0}^{n-1} (2^n - 2^j).$$

We can view the original $m\times n$ matrix as $M_I$ "augmented" with $m-n$ rows of indices $i\notin I$. If the number of preceding elements from $I$ to such an index is $t$ ($0\leq t\leq n$), then the row can take $2^t$ different values (e.g., for $t=0$ we can have only the zero vector, and thus the number of values is $2^0=1$). We remark that the choice of particular $t_1\leq t_2\leq \dots\leq t_{m-n}$ from $\{0,1,\dots,n\}$ fully determines the set $I$ itself.

The above analysis implies that the number of matrices we look for is the coefficient of $x^{m-n}$ in $f_n\cdot \prod_{t=0}^n \frac{1}{1-2^tx}$, which is the same as the coefficient of $x^{m+1}$ in $$F_n(x) = f_n\cdot \prod_{t=0}^n \frac{x}{1-2^tx}.$$

We will also need a modification of the above formula that addresses the case of matrices with exactly $z$ zero rows. It is not hard to see that the number of such matrices is given by the coefficient of $x^{m}$ in $$G_{m,n,z}(x) = \binom{m}{z}\cdot x^z\cdot f_n\cdot\prod_{t=1}^n \frac{x}{1-(2^t-1)x}.$$ This can be proved by first removing the zero rows from a matrix, and then by proceeding as above. The only difference is that the augmentation now cannot use zero vectors, each time leaving us with just $2^t-1$ values for a row instead of $2^t$.

Now, let us address the restriction on rows with single 1. We will use the inclusion-exclusion to do so.

Let $P_i$ ($i=1,\dots,n$) be the property that there is a row with single 1 at $i$-th coordinate. Suppose that an $m\times n$ matrix satisfy properties with indices from a set $R$ with $|R|=k$. Then the set of row indices is partitioned as $$[m] = J \sqcup \overline{J},$$ where $J$ consists of the indices corresponding to rows with single 1 at a coordinate from $R$. Let $j=|J|$ (we have $j\geq k$).

To enumerate the possible submatrices at $J\times [n]$, we notice that their columns essentially define an ordered partition of their rows into $k$ nonempty subsets. Hence, the number of such submatrices equals $k!\cdot S(j,k)$, where $S(\cdot,\cdot)$ is Stirling number of second kind.

The number of submatrices at $\overline{J}\times \overline{R}$ with exactly $z$ zero rows is given by the coefficient of $x^{m-j}$ in $G_{m-j,n-k,z}(x)$. They can be extended to submatrices at $\overline{J}\times [n]$ in $(2^k-k)^z\cdot (2^k)^{m-j-z}$ ways.

Putting all together and using inclusion-exclusion, we conclude that the required number of matrices (not satisfying any properties $P_i$) equals the coefficient of $x^m$ in $$\begin{split} &\sum_{k=0}^n (-1)^k \binom{n}{k} \sum_{j=k}^m \binom{m}{j}\cdot k!\cdot S(j,k) \sum_{z=0}^{m-j} x^j\cdot G_{m-j,n-k,z}(x)\cdot (2^k-k)^z\cdot (2^k)^{m-j-z}\\ =& n!\sum_{k=0}^n (-1)^k \frac{f_{n-k}}{(n-k)!}\cdot\prod_{t=1}^{n-k} \frac{x}{1-(2^t-1)x}\cdot\sum_{j=k}^m \binom{m}{j}\cdot S(j,k)\cdot \left(2^k+(2^k-k)x\right)^{m-j}\cdot x^j\\ =&\sum_{k=0}^n \binom{n}{k}\cdot f_{n-k}\cdot\prod_{t=1}^{n-k} \frac{x}{1-(2^t-1)x}\cdot \sum_{\ell=0}^k (-1)^\ell\cdot \binom{k}{\ell}\cdot \left(2^k+(2^k-k+\ell)x\right)^m. \end{split}$$

UPDATE. We can also get an explicit answer without using generating functions. As Yauhen noticed, $$[x^{m+1}]\ F_n(x) = \prod_{t=0}^{n-1} (2^m - 2^t).$$ Then the number of full-rank matrices with exactly $z$ zero rows can be obtained with inclusion-exclusion as $$[x^m]\ G_{m,n,z}(x) = \binom{m}{z}\sum_{p=0}^{m-z} (-1)^{m-z-p} \binom{m-z}{p} \prod_{t=0}^{n-1} (2^p - 2^t).$$ Using this expression, we can restate the number of full-rank matrices not satisfying any properties $P_i$ as $$\begin{split} &\sum_{k=0}^n (-1)^k \binom{n}{k} \sum_{j=k}^m \binom{m}{j}\cdot k!\cdot S(j,k) \sum_{z=0}^{m-j} \binom{m-j}{z}\cdot (2^k-k)^z\cdot (2^k)^{m-j-z}\\ \times&\sum_{p=0}^{m-j-z} (-1)^{m-j-z-p} \binom{m-j-z}{p} \prod_{t=0}^{n-k-1} (2^p - 2^t)\\ =&\sum_{k=0}^n (-1)^k \binom{n}{k} \sum_{j=k}^m \binom{m}{j}\cdot k!\cdot S(j,k) \sum_{p=0}^{m-j} (-1)^{m-j-p} \binom{m-j}{p}\cdot 2^{kp}\cdot k^{m-j-p} \prod_{t=0}^{n-k-1} (2^p - 2^t)\\ =&\sum_{k=0}^n \binom{n}{k} \sum_{\ell=0}^k (-1)^{k-\ell}\cdot \binom{k}{\ell} \sum_{p=0}^{m} \binom{m}{p}\cdot 2^{kp}\cdot (-\ell)^{m-p} \prod_{t=0}^{n-k-1} (2^p - 2^t)\\ =&\sum_{k=0}^n \binom{n}{k}\cdot k! \sum_{p=0}^{m} (-1)^{m-p}\cdot \binom{m}{p}\cdot 2^{kp}\cdot S(m-p,k) \prod_{t=0}^{n-k-1} (2^p - 2^t). \end{split}$$

• Me too :) to fix all typos... – Max Alekseyev Mar 16 '17 at 22:12
• And a side note: then number of $m \times n$ full-rank matrices is $\prod_{j=0}^{n-1} (2^m - 2^j)$ - it is easy to see if we count rank by columns. – Yauhen Yakimenka Mar 16 '17 at 23:34
• By the way, it seems the last formula gives an explicit hint for a (bit) shorter proof. – Yauhen Yakimenka Mar 20 '17 at 23:01
• The paper where we used this formula (Appendix B) has been put on arXiv: arxiv.org/abs/1804.06770 – Yauhen Yakimenka Jun 13 '18 at 15:47
• The paper has been accepted for publication: ieeexplore.ieee.org/document/8478307, the citation has been changed to link to this question. – Yauhen Yakimenka Jan 20 '19 at 16:06