Let $M\_1$ and $M\_2$ be two real positive-semidefinite matrices. Is there any algorithm to compute a permutation matrix $P$ to minimize $\| M\_1-PM\_2P^T \|\_F^2$ or equivalently to maximize $trace(M\_1PM\_2P^T)$?


To be simple, for $i=1,2$, further assume $M\_i=Q\_iQ\_i^T$, where $Q\_i$ has orthonormal columns.



matching two positive-semidefinite matrices
It is a graph-matching problem, which is NP-hard. But some solutions available if relaxing the perturbation matrix assumption. See example at <https://doi.org/10.1016/j.patcog.2016.07.015>


