What is computational complexity of the following problem:

given two complex $n\times n$ matrices $A$ and $B$ check if there is a permutation matrix $P$ such that: $$B = P A P^T.$$

If it helps, one can assume that $A$ and $B$ are hermitian (or even that $A$ and $B$ are real and symmetric).


The problem stems from checking if two sets of vectors are related by an unitary rotation, see Sets of vectors related by a rotation - MathOverflow. In that context $A$ and $B$ are their Gramian matrices.

The problem is at least as hard as the graph isomorphism problem - take $A$ and $B$ as adjacency matrices.


1 Answer 1


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.


Your Answer

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

Not the answer you're looking for? Browse other questions tagged or ask your own question.