Let say I have two $n$ x $n$ matrices $A$ and $B$ where all elements are real positive values. I want to find some $n$ x $n$ permutation matrix $P$ such that $\operatorname{tr}(P A P ^T B)$ is minimized. Does there exist such an algorithm or technique?



Algorithm to minimize $\operatorname{tr}(PAP^TB)$?
This problem is NP-hard.


Let $A$ be the adjacency matrix of an $n$-cycle plus the all-ones matrix and $B$ the adjacency matrix of a graph $G$ plus the all-ones matrix.


Then, if $G$ has a Hamiltonian cycle, the maximum trace is achieved when the elements of $PAP^T$ with value $2$ corresponds to a Hamiltonian cycle in $G$. Since finding Hamiltonian cycles is NP-hard, your problem is NP-hard.


