I've got two square real matrices ($A$ and $B$) and I want to find a permutation of the rows and columns (same permutation) to best approximate the other matrix. E.g. with $P$ as a permutation matrix and say the Frobenius norm


$\min\_{P \in \Pi} || A - PBP^T ||\_F$


Now, I know (a) if $A = PBP^T$ then you can find $P$ through the eigenvalue decompositions since the eigenvectors of $B$ are permuted eigenvectors of $A$ and (b) if you only permute the rows (or cols), i.e. $\min\_P ||A - PB||\_F$ this is a linear assignment problem and can easily be solved.


Can anyone help by identifying what the problem is? I figure it must be well known but I haven't seen it yet. 



permute both rols and cols of one matrix to best approximate another?
This problem looks like the [famous Quadratic assignment problem](http://en.wikipedia.org/wiki/Quadratic_assignment_problem), which means that in general you are out of luck as far as an exact solution is concerned.


