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 superdiagonal 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 supersuperdiagonals 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 wellknown 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$ 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 01 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