A canonical representative, for this equivalence relation on matrices

Question

This question is inspired by Constructing inequivalent binary matrices.

Define the equivalence relation $\sim$ as follows: If $M,N$ are two $8\times 8$ binary matrices (all elements are $0$ or $1$), say that $M \sim N$ if you can transform $M$ into $N$ by a sequence of moves, where each move picks some pair $(i,j)$ and swaps rows $i$ and $j$ and then swaps columns $i$ and $j$. For example, \begin{equation} \left( \begin{array}{ccc} 0 & 0 & 0 \\ 0 & 1 & 1 \\ 1 & 0 & 0 \end{array} \right) \sim \left( \begin{array}{ccc} 1 & 0 & 1 \\ 0 & 0 & 0 \\ 0 & 1 & 0 \end{array} \right). \end{equation} This equivalence relation induces a set of equivalence classes.

Is there a way to define a canonical representative for each equivalence class, so that given any matrix $M$, we can efficiently compute the canonical representative $M^*$ corresponding to the equivalence class containing $M$? I'm hoping for a simple and efficient algorithm to compute the canonical representative.

For instance, one way to define a canonical representative for matrix $M$ would be as follows: among all matrices $N$ that are equivalent to $M$, choose the one that is lexicographically first. However, I don't know of any fast way to compute the canonical representative corresponding to a given matrix $M$. (One could enumerate all matrices that are equivalent to $M$ by trying all $8!$ possible permutations, and then check which one is lexicographically first, but this is inefficient: it requires $8! \approx 2^{15.3}$ steps of computation, which is too much.) Is there a better approach?

Alternatively, is there a way to define a canonical representative for each equivalence class, so that we can quickly test any given matrix $M$ to determine whether it is in canonical form? (i.e., there is an efficient algorithm to check this)

A good answer to this question might help solve Constructing inequivalent binary matrices.

Answer 1

Here are some ideas to get started. First, we can arrange that the diagonal is of the form $0 \cdots 0 1 \cdots 1$. This breaks the original problem into two new problems which are equivalent to each other. Let's concentrate on the part with zeroes on the diagonal. We can sort the rows according to Hamming weight, and can arrange the first row to be of the form $0\cdots 0 1\cdots 1$, say the one with minimal weight. If it is the only row having the same weight, then again we have broken the problem into two parts, and can continue recursively. If there are several rows with the same minimal weight, we can try tie-breaking using column weights, but this is not always enough. That's where this approach gets stuck, though perhaps one could be more creative and extract a normal form from these ideas.