Consider the collection of all integer matrices and partition them via an equivalence relation $A\sim B\Leftrightarrow \exists$ a permutation matrix $P$ such that $B=PAP^T$. Is some canonical form possible for the representative of each equivalence class? In general what properties characterize a given class.

  • $\begingroup$ A first thought: Consider an integer matrix whose diagonal entries are all distinct. You can use permutation matrices to order these entries so that they are strictly increasing as you go down the diagonal. There will only be one such matrix in the equivalence class that you describe so you could consider this a canonical form for this type of matrix. (Note that this works fine for real matrices, not just integer matrices.) I'm not sure how to extend this to matrices with repeated diagonal entries... $\endgroup$ – Nick Gill Mar 6 '15 at 10:24
  • $\begingroup$ ... Actually, it's possible that you can then just consider super-diagonal entries and order these to be strictly increasing. You'd need to prove that this is (a) possible, and (b) unique (neither of which I'm sure about). Supposing this works, then iterating (considering super-super-diagonals etc) would yield a canonical form. $\endgroup$ – Nick Gill Mar 6 '15 at 10:46

Yes, sure it is possible; e.g. you can find $P$ so that $B$ gives the lexicographically maximal vector $(B_1,\dots,B_n)$ obtained by concatenating the rows $B_i$ of $B$.

This is a well-known approach in fact, and there are computer programs available that will compute it for you. On the other hand all the known algorithms will take in the worst case an exponential in $n$ number of operations.

  • $\begingroup$ I doubt that a canonical representation is possible (as mentioned above). But, at least, you can claim that the spectra of the matrices from the same class are similar, as the matrices are congruent. $\endgroup$ – victor Mar 6 '15 at 10:01
  • $\begingroup$ well, as I said, it's a classical idea in the graph isomorphism agorithms (and obviously generalised to the weighted case). $\endgroup$ – Dima Pasechnik Mar 6 '15 at 12:20
  • $\begingroup$ moreover, spectrum is a very weak invariant - it doesn't even distinguish trees, leave alone more general graphs. $\endgroup$ – Dima Pasechnik Mar 6 '15 at 12:22

I would say that no. Because even if you consider the subset of 0-1 matrices that are adjacency matrices of graphs, for this subset such a relation becomes simply the isomorphism of graphs. And the problem of isomorphism of graphs is complicated (for a first glance, see http://en.wikipedia.org/wiki/Graph_isomorphism_problem ).

If there were a good canonical representative and a good algorithm of reducing to it, one would be able to solve the graph isomorphism problem by reducing both graphs to their canonical representatives, and checking if these representatives coincide.

  • 3
    $\begingroup$ canonical representatives are surely possible, they are just hard to find, apparently. See my answer for details. $\endgroup$ – Dima Pasechnik Mar 6 '15 at 10:51
  • $\begingroup$ @DimaPasechnik: Yes, you are right. Good point! $\endgroup$ – Victor Kleptsyn Mar 6 '15 at 12:24

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.