# Approximate action of unitary matrix with permutation matrix

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}

-
Why doesn't the straightforward method work? Did you find a counterexample? If so could you show us? I think the minimum distance is bounded by a constant independent of the dimension of the matrix, but would depend on the spectral norm of $B$. – John Jiang Nov 23 '11 at 19:20
I have included a counterexample in the edit to my question. Thanks for your help. – Charles Bailey Nov 23 '11 at 20:36
Your counterexample only shows that the map from $SU(n)$ to the conjugacy class doesn't preserve monotonicity of distance. It could still be true that the minimum in the conjugacy orbit is always attained by the minimizer in $SU(n)$, unless you can demonstrate that $P_2$ is the minimizer in your example. – John Jiang Nov 23 '11 at 22:35
I apologize for not being clear in my edit. P1 is a minimizer of $||Q - P||$ and P2 is a minimizer of $||QBQ^{T} - PBP^{T}||$. I say "a minimizer" because there are multiple minimizers, but choosing a different representative does not necessarily make P1 behave as desired. – Charles Bailey Nov 24 '11 at 1:28
How large can $n$ be? it seems like some kind of graph-matching might resolve it, maybe not! – Suvrit Nov 24 '11 at 22:24