# matching two positive-semidefinite matrices

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.

• As a cheap observation, we can equivalently maximize $\|Q_1^T P Q_2 \|_F$ over doubly stochastic matrices. – Mahdi Nov 22 '18 at 18:17
• Also, we have $\|Q_1^T P Q_2 \|_F^2 = \sum_{1\leq i,j\leq k}(a_i^TPb_j)^2 = \sum_{1\leq i,j\leq k} \tr(PQ_{ij})^2$, where $a_i$'s and $b_i$'s are respectively columns of $Q_1$ and $Q_2$ and $Q_{ij}=a_ib_j^T$. – Mahdi Nov 22 '18 at 18:17
• @Mahdi, I think you meant $Q_{ij}=b_ja_i^T$. So, we need to maximize $\sum_{1\le i,j,\le k}tr(PQ_{ij})^2$. Could you explain a little bit more to maximize it? Here, $P$ is a permutation matrix. – John Nov 23 '18 at 21:31
• Yes, that was a typo. Since $\|Q_1^T P Q_2 \|_F$ is a convex function, the optimum value didn't change if we get optimum over the convex hull of all permutation matrices, which is equal to doubly stochastic matrices. I am not sure, is there any exact algorithm, for maximizing that quadratic function over some linear constraints. – Mahdi Nov 23 '18 at 21:54
• @Mahdi, did you mean to get a continuous $P$ first via optimization, then make it discrete with {0,1} elements? – John Nov 23 '18 at 21:59