In graph isomorphism problem, for which Babai's quasi polynomial algorithm is currently under review (stack), we ask if two adjacency matrices: of $\{0,1\}$ coefficients differ only by a permutation.
Is general problem: without coefficient restriction more difficult, or we can also assume that it is quasi-polynomial?
Formally: having two $n\times n$ matrices: $A$, $B$ let say of algebraic coefficients, we would like to test if they are not only similar: $B=O^T A O$ for some orthogonal $O$, but additionally that it can be done with $O$ being a permutation.
Testing similarity is simple: just check if $\textrm{Tr}(A^k)=\textrm{Tr}(B^k)$ for $k=1..n$.
The difficulty is that there can be a large space of $O$ matrices between them. For example adjacency matrix of strongly regular graphs (SRG) has only 3 eignevalues: there are two very degenerated eigenspaces, and so there is large space of possible $O$ matrices (searching permutation there seems tough).
Are there tests restricting this space of possible $O$ matrices? I have just used the following: $$A'_{ab}=\sum_{ij} A_{ai} A_{aj} A_{ij} A_{ib} A_{jb}\qquad B'_{ab}=\sum_{ij} B_{ai} B_{aj} B_{ij} B_{ib} B_{jb}$$ and testing $\textrm{Tr}(A'^k)=\textrm{Tr}(B'^k)$ (for $k=1..n$) has started distinguishing strongly regular graphs (tests) - their similarity restricts the space of possible $O$ matrices (contains permutations, simpler constructions did not distinguish SRGs).
How to characterize this restriction of $O$ matrices? Can we restrict to only permutations this way - solving the problem? (also graph isomorphism)
Generally, is this problem essentially more difficult than graph isomorphism problem?
Testing if two matrices differ only by permutation is basically just testing two coloured graphs (where both vertices and edges are coloured) for isomorphism. It is not difficult to see that this problem is GI-complete.
Your problem is probably that you attach special significance to the concrete entries in the matrices. However, all that matters about them is whether they are equal or not. Hence the entries just create specific colour classes. You can use an arbitrary numbering of those colour classes and replace the entries by the number of their colour class.