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$
1
  • $\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$ Apr 27, 2016 at 9:49

1 Answer 1

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$
13
  • $\begingroup$ Ooh, very good point. I'll try to wrap my head around this for a minute or two. $\endgroup$ Apr 1, 2016 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$ Apr 1, 2016 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, 2016 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, 2016 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, 2016 at 12:12

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .