2
$\begingroup$

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

$\endgroup$
7
  • $\begingroup$ Can you use inclusion-exclusion? $\endgroup$ – Anthony Quas Mar 15 '17 at 18:27
  • $\begingroup$ I am not sure I see how to use it... $\endgroup$ – Yauhen Yakimenka Mar 15 '17 at 18:31
  • $\begingroup$ 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) ... $\endgroup$ – Anthony Quas Mar 15 '17 at 18:39
  • $\begingroup$ 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? $\endgroup$ – Yauhen Yakimenka Mar 15 '17 at 18:53
  • $\begingroup$ 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/… $\endgroup$ – Henry.L Mar 15 '17 at 19:17
3
$\begingroup$

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

$\endgroup$
18
  • 2
    $\begingroup$ Me too :) to fix all typos... $\endgroup$ – Max Alekseyev Mar 16 '17 at 22:12
  • 1
    $\begingroup$ 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. $\endgroup$ – Yauhen Yakimenka Mar 16 '17 at 23:34
  • 1
    $\begingroup$ By the way, it seems the last formula gives an explicit hint for a (bit) shorter proof. $\endgroup$ – Yauhen Yakimenka Mar 20 '17 at 23:01
  • 1
    $\begingroup$ The paper where we used this formula (Appendix B) has been put on arXiv: arxiv.org/abs/1804.06770 $\endgroup$ – Yauhen Yakimenka Jun 13 '18 at 15:47
  • 1
    $\begingroup$ The paper has been accepted for publication: ieeexplore.ieee.org/document/8478307, the citation has been changed to link to this question. $\endgroup$ – Yauhen Yakimenka Jan 20 '19 at 16:06

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.