1
$\begingroup$

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.

Improve this question
$\endgroup$
2
  • $\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, 2015 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, 2015 at 10:46

2 Answers 2

Reset to default
4
$\begingroup$

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.

Improve this answer
$\endgroup$
3
  • $\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, 2015 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, 2015 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, 2015 at 12:22
3
$\begingroup$

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.

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

Your Answer

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