2
$\begingroup$

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, \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? 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.

$\endgroup$
1
$\begingroup$

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.

$\endgroup$
  • $\begingroup$ Thanks for this Igor! As far as I understand, this means that it is very difficult to calculate a canonical form in polynomial time because then we could convert two different matrices to their canonical form and compare them, so this would imply that the graph isomorphism problem is in P. However, what I really need to do is slightly different: All I want is to construct a matrix in every equivalence class and run some tests on them. Is there any obvious reason why I cannot construct these fast? Thanks again! $\endgroup$ – Heterotic Jan 5 '14 at 14:54
  • 1
    $\begingroup$ @Heterotic this is not easy either. You should look at Brendan McKay's program nauty (google will tell you where to go), and for references thereto (the program generates isomorphism classes of graphs, so your problem restricted to graphs). $\endgroup$ – Igor Rivin Jan 5 '14 at 15:34

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.