# Canonical permutation of a symmetric matrix

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?

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

• 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. – Daniel Lichtblau Apr 5 at 13:28
• 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. – Daniel Lichtblau Apr 5 at 13:40
• @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 – Fidel I. Schaposnik Apr 7 at 7:33
• (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. – Daniel Lichtblau Apr 7 at 15:12