2
$\begingroup$

If you consider all $m$ by $n$ matrices with entries that are either $0$ or $1$, there are ${2^{n} \choose m}$ with no repeated rows (up to row permutation) and ${2^{m} \choose n}$ with no repeated columns (up to column permutation). Is it possible to get an explicit estimate for how many there are with neither any repeated rows nor columns (up to either row or column permutation)? I am interested in the case where $m$ is large and $m \leq n \leq m^2$.

[Extended version of a previous unanswered MSE question ]

$\endgroup$
3
  • 1
    $\begingroup$ Almost all matrices of these dimensions have no repeated rows or columns (the probability that two rows are the same is bounded by $\binom m2 2^{-n}$ and the probability that two columns are the same is at most $\binom n2 2^{-m}$. So a good estimate is $2^{nm}$. $\endgroup$ Feb 22, 2014 at 22:03
  • 1
    $\begingroup$ Continuing Anthony's comment, almost none of them have any symmetries either (slightly harder to prove) so to allow for row and column permutations asymptotically just divide my $m!\,n!$. $\endgroup$ Feb 23, 2014 at 1:30
  • 5
    $\begingroup$ The problem of counting these matrices up to row and column permutations is solved in I. M. Gessel and J. Li, Enumeration of point-determining graphs, J. Combinatorial Theory Ser. A 118 (2011), 591-612, available online at arxiv.org/abs/0705.0042. (In the paper they are called "semi-point-determining bicolored graphs".) Of course, as in most unlabeled graphical enumeration problems, the formula is not simple, and might not be so helpful in deriving an asymptotic formula. The numbers in Richard's formula are sequence A181230 in the OEIS. $\endgroup$
    – Ira Gessel
    Feb 23, 2014 at 17:16

1 Answer 1

6
$\begingroup$

Let $f(m,n)$ denote the number of matrices being counted (not up to row and column permutation). We can try to compute $f(m,n)$ by Inclusion-Exclusion, allowing the rows to be distinct and sieving out the possible ways in which columns can be equal. This is just Möbius inversion on the lattice $\Pi_n$ of partitions of an $n$-element set. Plugging into the techniques of Enumerative Combinatorics, vol. 2, Section 5.1, gives $$ F(x,y):=\sum_{m,n\geq 0} f(m,n)\frac{x^m}{m!}\frac{y^n}{n!} = \sum_{n\geq 0}(1+x)^{2^n}\frac{(\log(1+y))^n}{n!}. $$ It is curious that $F(x,y)=F(y,x)$. It shouldn't be difficult to get some good estimates for $f(m,n)$ from $F(x,y)$.

It seems more difficult to count the matrices up to row and column permutations because even if all the rows are distinct and all the columns are distinct, a matrix can still be fixed by a nontrivial permutation of rows and columns.

$\endgroup$
1

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.