<p>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.</p>

CC BY-SA 3.0
2012-07-13T13:30:02.660Z
2012-07-14T01:12:25.380Z
2012-07-14T01:12:25.380Z
Tsuyoshi Ito
<p>What is computational complexity of the following problem:</p>

<p>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.$$</p>

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

<p>Notes:</p>

<p>The problem stems from checking if two sets of vectors are related by an unitary rotation, see <a href="https://mathoverflow.net/questions/101694/sets-of-vectors-related-by-a-rotation">Sets of vectors related by a rotation - MathOverflow</a>. In that context $A$ and $B$ are their <a href="http://en.wikipedia.org/wiki/Gramian_matrix" rel="nofollow noreferrer">Gramian matrices</a>.</p>

<p>The problem is at least as hard as the <a href="http://en.wikipedia.org/wiki/Graph_isomorphism_problem" rel="nofollow noreferrer">graph isomorphism problem</a> - take $A$ and $B$ as adjacency matrices.</p>

<cc.complexity-theory><np-hardness><cg.comp-geom><linear-algebra><permutations>
Two matrices related by a permutation $B = P A P^T$ - complexity
Piotr Migdal
# Two matrices related by a permutation $B = P A P^T$ - complexity

(Asked by: username_0 on 2012-07-13)

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).

Notes:

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](https://mathoverflow.net/questions/101694/sets-of-vectors-related-by-a-rotation). In that context $A$ and $B$ are their [Gramian matrices](http://en.wikipedia.org/wiki/Gramian_matrix).

The problem is at least as hard as the [graph isomorphism problem](http://en.wikipedia.org/wiki/Graph_isomorphism_problem) - take $A$ and $B$ as adjacency matrices.

**Tags:** cc.complexity-theory, np-hardness, cg.comp-geom, linear-algebra, permutations


---

## 1 answers

### Answer by username_1 on 2012-07-13. Score: 18 | Accepted answer

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.


---

