Two matrices related by a permutation $B = P A P^T$ - complexity
It is equivalent to deciding whether two given multigraphs (or edge-labelled graphs) are isomorphic or not, which is known to be equivalent to the usual graph isomorphism problem.