Q1 For which matrices deciding permutation similarity is polynomial?
It is not easier than graph isomorphism (and very likely is equivalent to it).
If necessary, assume the entries are nonnegative integers.
Partial answer are the adjacency matrices of graphs in classes, where GI is polynomial.
