How many $M\in\{0,1\}^{r\times c}$ are there such that each row and each column of $M$ is distinct?

How many classes of matrices in $\{0,1\}^{r\times c}$ up to permutation equivalence are there such that each matrix in every class has each row and each column distinct?

What is the analogous count if rank over $\Bbb K$ is restricted to exactly $m$ where $\Bbb K$ is a field?

If $\Bbb K=\Bbb R$ then if $r=c$ then asymptotically I think we should have $2^{cm}$ matrices.

  • $\begingroup$ For the rank version, do you still want 0-1 matrices? $\endgroup$ – Brendan McKay Dec 29 '16 at 7:40
  • $\begingroup$ @BrendanMcKay Yes and I want $\Bbb K=\Bbb R$ case. $\endgroup$ – user94040 Dec 29 '16 at 8:10

This is OEIS sequence A181230. The square case $r=c$ is OEIS sequence A088310. See those pages for formulas. As Pat Devlin mentions, the asymptotic problem is trivial if both $r$ and $c$ increase quickly enough.

  • $\begingroup$ what happens in the non-typical case of fixed rank? $\endgroup$ – user94040 Dec 29 '16 at 1:56

Ok. Let's say $r \leq c$ and say $N = 2^r$.

Then the number of matrices with each column distinct is exactly $N(N-1)\cdots (N-c+1)$. This is an upper bound on the first question you asked.

Approximation time: suppose $r^2 \ll 2^c$ then almost all (asymptotically all) matrices will have distinct rows (birthday problem) anyway. Since $r \leq c$, this condition will happen provided $r \gg 1$. Therefore, having distinct rows basically always happens, so the upper bound given above is essentially the truth [this can be made more rigorous and exact as desired].

If you want to look at the equivalence class thing, then just use the fact that most matrices will have only one automorphism anyway. So just divide the answer by $r! c!$.

Punchline: the thing is asymptotically easy, and the answer is more or less exactly what you'd think.

  • $\begingroup$ So $2^{rc}$ and $\frac{2^{rc}}{r!c!}$ roughly? Can I ask what happens if I restrict the rank to exactly $m$ and ask similar count? $\endgroup$ – user94040 Dec 29 '16 at 0:04
  • $\begingroup$ Yes to the first question. For rank $m$ the count drops drastically. Almost all matrices have full rank. Degeneracy in rank is mostly due to repeated rows, so counting matrices with only $m$ different rows should be pretty close to the number of matrices with rank $m$. If you want low rank and all distinct rows, I'm not sure what to expect there. $\endgroup$ – Pat Devlin Dec 29 '16 at 0:16
  • 2
    $\begingroup$ Disclaimer: With the rank stuff, you quickly get into the world of a bunch of conjectures. For example, search something like "probability 0,1 matrix has zero determinant". This ought to be essentially the probability that the thing has two identical rows, but even proving it was exponentially small was tricky. $\endgroup$ – Pat Devlin Dec 29 '16 at 0:37

Your Answer

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