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}