3
$\begingroup$

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?

$\endgroup$
4
$\begingroup$

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.)

$\endgroup$
3
$\begingroup$

Partial answer.

You can assume $m \le n$.

There are clearly $n+1$ classes when $m=1$: all that matters is the number of $1$s in the only row.

In general, the two multisets that specify the number of $1$s in the rows and in the columns are clearly invariant. They are a complete set of invariants for the $2 \times 2$ case.

In the general case, any pair of multisets with the right cardinalities and equal sums will represent some set of equivalence classes. Swapping all the $1$'s for $0$s and vice versa halves the difficulty of the analysis.

Counting classes is at least as hard as the corresponding partition counting problem.

Are the multisets a complete set of invariants, or do you need to refine them? I suggest you work out the $2 \times 3$ and perhaps $3\times 3$ cases by brute force to see what might be going on.

@MorganRodgers 's answer suggests that this is a hard problem.

$\endgroup$

Your Answer

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

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