9
$\begingroup$

I'm trying to figure out how many ways there are to construct a $k \times n$ binary matrix such that it has rank $r$ and no column is repeating. I've tried a bunch of different approaches. The attempt that I assign the highest confidence is the following:

We want to enumerate all possible $B_r = [\textbf{b}_1,\dots \textbf{b}_n]$ such that $\textbf{b}_i \in \mathbb{F}_2^k$, $\textbf{b}_i \neq \textbf{b}_j$ and Rank$(B_r) = r$.

The number of ways to pick a basis of dimension $r$ from a subspace of dimension $k$ is given by the Gaussian binomial ${k \brack r}$. Since we have $n$ column slots and this basis will occupy $r$ of these slots, we can insert the basis in $\binom{n}{r}$ different ways.

To fill the remaining $n-r$ columns, we must not choose a vector outside of the span of this basis, which means we must fill the remaining $n-r$ rows from a set of $2^r-r$ candidates.

There are $2^r-r$ ways of choosing $\textbf{b}_{r+1}$ and $2^r-r-i$ ways of choosing $\textbf{b}_{r+i}$, where $i= 1,\dots,n-r$, so the number of possible rank $r$ matrices of dimension $k \times n$ with no repeating columns is given by

$$|\{M \in \mathbb{F}_2^{n \times k}: \text{Rank}(M)=r, \textbf{m}_i \neq \textbf{m}_j\}| = \binom{n}{r}{k \brack r}\prod_{i=1}^{n-r} (2^r - r-i).$$

EDIT: After comparing joriki's expression with simulations in Matlab I just didn't get the right results. Let me try to reformulate my thought process as clearly as possible.

Begin by considering the number of possible $r$-dimensional subspaces of $\mathbb{F}_2^k$, given by ${k \brack r}$. Enumerate all ways of building a $k \times n$ matrix only using elements from such a subspace, which is $\frac{2^r!}{(2^r-n)!}$. The problem is that all of these ${k \brack r}\frac{2^r!}{(2^r-n)!}$ matrices will not have rank $r$ (but none will have rank \emph{more} than $r$).

To begin with, we must subtract all $k \times n$ rank $r-1$ submatrices. How many of these are there? Well the columns are eminating from a $r$-dimensional binary space. So we count the number of subspaces of dimension $r-1$ to an $r$-dimensional space and multiply with the number of ways of choosing $n$ vectors from this space. We get ${r \brack r-1}\frac{2^{r-1}!}{(2^{r-1}-n)!}$. But once again we have the problem that not all these have rank $r-1$. So from this we must subtract ${r-1 \brack r-2}\frac{2^{r-2}!}{(2^{r-2}-n)!}$ and so forth.

\begin{align} |\mathcal{N}_{r,k}| = &{k \brack r}\frac{2^r!}{(2^r-n)!} - \sum_{i=1}^r \Big({r \brack r-i}\frac{2^{r-i}!}{(2^{r-i}-n)!} \\ &- \sum_{j=1}^{r-i}\Big({r-i \brack r-i-j}\frac{2^{r-i-j}!}{(2^{r-i-j}-n)!} - \sum_{\ell=1}^{r-i-j} \Big(\dots \end{align} So how do we define this recursively? Define \begin{align} a_0 &:= {k \brack r}\frac{2^r!}{(2^r-n)!} \\ a_{p,q} &:= {p \brack q}\frac{2^q!}{(2^q-n)!} - \sum_{i=1}^p a_{q,q-i}. \end{align} Then we should have \begin{align} |\mathcal{N}_{r,k}| = a_0 - \sum_{i=1}^r a_{r,r-i}. \end{align}

Tested this in Matlab and it does not work - it doesn't subtract enough matrices. The effect is greatest when $n,r < k$ and all parameters are not tiny.

It is kind of weird how $k$ never enters into the enumeration of rank $r-i$ matrices of size $k\times n$. I guess it COULD make sense that the enumeration is conditionally independent on $k$ given that we know this new $r-i$ dimesional subspace is embedded in an $r<k$ dimensional space. But clearly undercounting is done somewhere in the recursion and this seems like the likeliest candidate.

I guess the question is: Is counting the ways we can build a $k \times n$ matrix by only using elements from an $r-i$ dimensional subspace really the same as counting $r-i$ dimensional subspaces of $r<k$-dimensional space times the number of ways we can choose $n$ vectors out of this space? It does not seem right.

EDIT 2: Back to where I started, essentially can't see the problem of the original attempt

$$|\mathcal{N}_{r,k}| = {k \brack r}\frac{2^r!}{(2^r-n)!} - \sum_{i=1}^r |\mathcal{N}_{r-i,k}|.$$

Just count the number of $k \times n$ matrices with rank $r$ or less, then subtract all $k \times n$ matrices with rank less than $r$. This expression should essentially hold by definition. Really frustrating.

EDIT 3: So the fault is ${k \brack r}\frac{2^r!}{(2^r-n)!}$ as a formula for counting all $k \times n$ matrices with rank at most $r$. It is overcounting by quite a bit. This is because the same matrix could be formed by choosing $n$ different components from two different subspaces. Consider subspaces $A = \{x_1,\dots, x_n, a_{n+1},\dots, a_{2^r}\}$ and $B = \{x_1,\dots,x_n, b_{n+1},\dots,b_{2^r}\}$. They're two distinct subspaces but we are counting the matrix formed from taking the first $n$ vectors from $A$ and the matrix formed from taking the first $n$ vectors from $B$ as two different matrices. Clearly they're not.

Which makes one wonder if this can be solved with some kind of additional inclusion-exclusion trick, or if it's just one of those really tricky problems.

$\endgroup$
  • $\begingroup$ Ok I think I know what the problem might be. In the case someone is curious about this problem and want partial updates, I would not mind. But I guess I should avoid clutter until I have a nice solution otherwise. $\endgroup$ – Benjamin Lindqvist Apr 27 '16 at 9:49
3
$\begingroup$

If I understand your calculation correctly, you're massively overcounting, since many other subsets of $r$ columns would serve as a basis that could have been chosen in the first step.

I'd do this using inclusion-exclusion. Recursively define coefficients

$$ c_j=\begin{cases}1&j=r\;,\\-\sum_{l=j+1}^rc_l\binom lj_2&j\lt r\;.\end{cases} $$

Then the count you want is

$$ \sum_{j=\lceil\log_2 n\rceil}^rc_j\binom kj_2\frac{2^j!}{(2^j-n)!}\;, $$

where the summand is the number $\binom kj_2$ of $j$-dimensional subspaces of the $k$-dimensional column space, $\frac{2^j!}{(2^j-n)!}$ is the number of ways to choose $n$ different vectors from such a space in order, and the $c_j$ are defined such as to subtract out selections of lower rank.

$\endgroup$
  • $\begingroup$ Ooh, very good point. I'll try to wrap my head around this for a minute or two. $\endgroup$ – Benjamin Lindqvist Apr 1 '16 at 10:48
  • $\begingroup$ So the gameplan is counting the number of ways to construct a subspace of dimension $r$ in the term corresponding to $c_j=1$, then subtracting all the ways the addition of the $n-r$ additional vectors 'accidentally overlaps' with the choice of subspace? This is a great information. But I' not sure why we're starting with $j=\lceil \log_2 n\rceil$... $\endgroup$ – Benjamin Lindqvist Apr 1 '16 at 11:14
  • 2
    $\begingroup$ @BenjaminLindqvist: No, the subtraction isn't to account for overlap with $n-r$ additional vectors (note that $n$ doesn't occur in the definition of the $c_j$). The substraction serves to subtract selections from the $r$-dimensional subspaces that have rank $\lt r$. It might be a good idea to try it on a small example to get a feel for it. The reason for starting with $j=\lceil \log_2 n\rceil$ is that otherwise the denominator would be undefined; we need at least $2^j=n$ vectors in the $j$-dimensional subspace to be able to select $n$ of them. $\endgroup$ – joriki Apr 1 '16 at 11:19
  • 2
    $\begingroup$ @BenjaminLindqvist :This concept of "$n-r$ additional columns" doesn't occur in the way I'm approaching this. The $j=r$ term is simply the number of $r$-dimensional subspaces times the number of ways of selecting $n$ different elements from them. The remaining terms subtract out selections that have rank $\lt r$. All of these selections are selections of $n$ vectors; there are never any $r$ vectors that are privileged or selected first (and thus also no $n-r$ vectors that are "additional"). $\endgroup$ – joriki Apr 1 '16 at 11:47
  • 2
    $\begingroup$ @BenjaminLindqvist: No, I'm sorry to have given that impression. I wouldn't consider it easy. In fact it helped me sort out my thinking about inclusion-exclusion (math.SE questions have a tendency to do that :-). What makes it difficult is that subspaces can overlap in complicated ways. Easy inclusion-exclusion problems have $n$ conditions where it's easy to count the number of ways that $k$ of them can overlap. That allows the result to be written as a single sum, whereas here I had to define the $c_j$ recursively to allow each rank to compensate for the overcount in all higher ranks. $\endgroup$ – joriki Apr 1 '16 at 12:12

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.