Given a unitary matrix Q and a symmetric matrix B, I am trying to find a permutation matrix P such that  

$ || QBQ^{T} - PBP^{T} ||_{F} $ 

is minimized.  

The straightforward method of minimizing $ || Q - P ||_{F} $ does not work.  

I was wondering if there would be some way to orthogonally project the orbit of B under conjugation by unitary matrices onto the orbit of B under conjugation by permutation matrices.  I don't know precisely how that would work though. 

Does anyone have any suggestions?  



Thanks,

Charles

Edit:

An example that shows that minimizing $||Q-P||_{F}$ does not work is as follows:


B = \begin{array}{cc}
0 & 1 & 1 & 1 \newline
1 & 0 & 0 & 0 \newline
1 & 0 & 0 & 0 \newline
1 & 0 & 0 & 0 \newline
\end{array}

Q =  
\begin{array}{rr}
-0.6544  & -0.6544  &  0.1585  &  0.3440 \newline
-0.0473 &  -0.0473 &  -0.9624  &  0.2633 \newline
-0.6864  &  0.3136  & -0.1561  & -0.6373 \newline
 0.3136 &  -0.6864 &  -0.1561  & -0.6373 \newline
\end{array}

$P_{1}$ = 
\begin{array}{rr}
     0  &   0 &    1&     0 \newline
     0   &  0  &   0 &    1 \newline
     0    & 1   &  0  &   0 \newline
     1    & 0    & 0   &  0 \newline
\end{array}

$P_{2}$ = 
\begin{array}{rr}
     1&     0&     0 &    0\newline
     0 &    0 &    1  &   0\newline
     0  &   1  &   0   &  0\newline
     0   &  0   &  0    & 1\newline
\end{array}



With these matrices,

\begin{align} 
|| Q - P_{1} || &< || Q - P_{2} ||
\end{align}

but 
\begin{align} 
|| QBQ^{T} - P_{1}BP_{1}^{T} || &> || QBQ^{T} - P_{2}BP_{1}^{T} ||
\end{align}