Take the 2-minute tour ×
Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. It's 100% free, no registration required.

I'm interested in the number of binary matrices of a given size that are distinct with regard to row and column permutations.

If $\sim$ is the equivalence relation on $n\times m$ binary matrices such that $A \sim B$ iff one can obtain B from applying a permutation matrix to A, I'm interested in the number of $\sim$-equivalence classes over all $n\times m$ binary matrices.

I know there are $2^{nm}$ binary matrices of size $n\times m$, and $n!m!$ possible permutations, but somehow I fail to get an intuition on what this implies for the equivalence classes.

share|improve this question
3  
Intuitively, the average matrix has trivial stabilizer, so there ought to be roughly 2^{nm}/n!m! equivalence classes. This is probably a very hard question in general. –  Qiaochu Yuan Feb 15 '11 at 12:02
4  
There is the set $S:=[m]\times[n]$ on which the group $G:=S_m\times S_n$ acts, and we have to color $S$ with colors $0$ and $1$. How many colorings are there when two colorings that differ by a $g\in G$ are considered the same? Now there is a famous theory that addresses exactly this kind of questions; it is called Polya counting theory. I could imagine that your problem is a standard example in the field. –  Christian Blatter Feb 15 '11 at 13:24
    
If you view A as the incidence matrix of an unweighted undirected bipartite graph. Then I think the question you're asking is how many unique bipartite graphs up to isomorphism are there with the two vertex groups having n,m vertices respectively. –  JSchlather Feb 15 '11 at 17:53
add comment

1 Answer

up vote 7 down vote accepted

This is solved here using Pólya enumeration theory. For the square case ($n=m$), see this sequence.

Comment: I found these by searching for $1,2,7$ in the OEIS.

share|improve this answer
    
The relevant cycle indices for the square case are computed and applied at this MSE link. –  Marko Riedel Jan 25 at 22:35
    
The first is broken now but I would love to know the answer. Is there an alternative source? –  Raphael Feb 21 at 20:38
    
@Raphael Updated the link. –  Yuval Filmus Feb 21 at 20:46
add comment

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

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