Linear Algebra – Understanding equivalence classes of binary matrices under permutations of rows/columns

Question

Consider an MxN matrix A consisting entirely of 1's and 0's.
Let C be the equivalence class of A under permutations of its rows and permutations of its columns (but not rows with columns).
Given A, how can I compute an invariant of C which is different for different equivalence classes?
How many classes are there for a given M and N?

Answer 1

It is not at all easy to count how many classes there are for a given $M$ and $N$. Mostly because to even know the size of particular equivalence class, you need to know the size of its stabilizer group.

Each such binary matrix corresponds to a bipartite graph with $M$ vertices in the first part and $N$ vertices in the second part. Equivalence classes under permutations of rows/columns correspond to isomorphism classes of graphs, where the two parts are distinguished (and so are not allowed to be swapped). Computing the size of the stabilizer group of a matrix is thus equivalent to computing the automorphism group of the associated graph. This is a hard problem. Counting the number of nonisomorphic bipartite graphs is also very hard (though I think it can be done using Polya enumeration).

Your best bet for an invariant for the equivalence classes is to come up with a canonical form; if you can impose an order on the set of matrices, then you can represent an equivalence class with the "smallest" of its members. (You can look up "canonical graph labeling" to get an idea of how this works.)