1
$\begingroup$

In investigating How to generate the 8^th order symmetric binary matrices whose sum of absolute eigenvalues is 8? I wished to avoid considering matrices that differed only by the same permutation applied to their rows and columns.

My plan was to define a function perm transforming a matrix m to some canonical form and consider it only if perm[m]==m.

My naive approach defined

perm[u_?MatrixQ] := Module[{ord}, ord = Ordering[u]; #[[ord]] & /@ u[[ord]]]

but I now realise that this doesn't work as reordering the columns changes the orders of the rows. For example

m = {{0, 0, 0, 0, 0, 0}, {0, 0, 0, 0, 0, 0}, {0, 0, 1, 1, 1, 
    1}, {0, 0, 1, 1, 0, 0}, {0, 0, 1, 0, 1, 1}, {0, 0, 1, 0, 1, 1}};

perm[m] == perm[perm[m]]
(* False *)

Is there a simple way for defining and computing a canonical permutation?

Improve this question
$\endgroup$

1 Answer 1

Reset to default
2
$\begingroup$

One way to define perm would be to consider all permutations of the rows and columns of m, then take the resulting matrix elements to be base-2 digits of an integer number uniquely identifying each permuted matrix. The matrix presenting the minimal such number among all 8! permutations can then become your canonical matrix, i.e.

perm[m_] := First@MinimalBy[Table[m[[p, p]], {p, Permutations@Range@8}], FromDigits[Flatten@#, 2] &]

Of course, this is quite slow since each call to perm results in ~40.000 operations, but the problem you are trying to solve is in fact hard, in the sense that it can be reinterpreted as addressing the graph isomorphism problem: taking m to be the adjacency matrix of a graph, finding a canonical form for m is equivalent to relabeling the nodes in a canonical way, which could be used to check whether two graphs are isomorphic or not... and we know this to be an NP-complete problem. [EDIT: We don't know this, see comments below]

The observation above, however, leads to a better implementation of perm, taking advantage of Mathematica's pre-implemented heuristics for graph canonization:

perm[m_] := AdjacencyMatrix@CanonicalGraph@AdjacencyGraph@m

This should be faster than the "naive" implementation, but still too slow for large matrices (or lots of calls)...

Improve this answer
$\endgroup$
4
  • $\begingroup$ I don't think complexity of graph isomorphism is known to be NP-complete (or NP-anything, for that matter). This is still a reasonable answer though. $\endgroup$
    – Daniel Lichtblau
    Commented Apr 5, 2021 at 13:28
  • $\begingroup$ I think there is an optimization that could reduce complexity of this method. Step 1: Take any permutation that moves all 1's ir now 1 as far right as possible. Apply it both to rows and columns. Step 2: We now have row 1 as 0,...,0,1,...,1, that is, a block of 0s and a block of 1s. Within each block, take an permutation that moves 1s in row 2 as far to the right as possible. Apply it to rows and columns. We now have four blocks. Repeat block-wise on row 3, etc. I suspect the worst-case complexity will be due to the permutation matrix multiplications. $\endgroup$
    – Daniel Lichtblau
    Commented Apr 5, 2021 at 13:40
  • $\begingroup$ @DanielLichtblau Sorry, I mixed it up with the subgraph isomorphism problem also mentioned in the Wikipedia page, I've now edited my answer to avoid confusion. In any case, I expect optimizations such as the one you suggest are already implemented by CanonicalGraph $\endgroup$
    – Fidel I. Schaposnik
    Commented Apr 7, 2021 at 7:33
  • $\begingroup$ (1) I was wondering if you had intended subgraph rather than graph. (2) I imagine you are right about such optimizations though I do not know for certain. $\endgroup$
    – Daniel Lichtblau
    Commented Apr 7, 2021 at 15:12

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

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