3
$\begingroup$

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.

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

2 Answers 2

Reset to default
1
$\begingroup$

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.

Improve this answer
$\endgroup$
1
  • $\begingroup$ what happens in the non-typical case of fixed rank? $\endgroup$
    – user94040
    Commented Dec 29, 2016 at 1:56
0
$\begingroup$

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.

Improve this answer
$\endgroup$
3
  • $\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
    Commented Dec 29, 2016 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
    Commented Dec 29, 2016 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
    Commented Dec 29, 2016 at 0:37

You must log in to answer this question.