# A canonical form for this equivalence relation on matrices

This question is inspired by https://cs.stackexchange.com/q/19250/755.

Define the equivalence relation $\sim$ as follows: If $M,N$ are two $8\times 8$ (or $n\times n$ if you prefer generality) $(0,1)$ matrices (all elements are $0$ or $1$), say that

$$M \sim N \text{ iff there is a permutation matrix P such that }M=PNP,$$ ie 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, $$\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).$$ 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? In particular, can we construct the canonical form of a given matrix without constructing every other matrix in its conjugacy class?

A good answer to this question might help solve https://cs.stackexchange.com/q/19250/755.

This is at least as hard as graph isomorphism,(which is your problem for $M$ adjacency matrix of a graph) which is not known to be in $P,$ so I would not hold my breath for anything too speedy.