3
$\begingroup$

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}

$\endgroup$
5
  • $\begingroup$ 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$. $\endgroup$
    – John Jiang
    Nov 23, 2011 at 19:20
  • $\begingroup$ I have included a counterexample in the edit to my question. Thanks for your help. $\endgroup$ Nov 23, 2011 at 20:36
  • $\begingroup$ 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. $\endgroup$
    – John Jiang
    Nov 23, 2011 at 22:35
  • $\begingroup$ 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. $\endgroup$ Nov 24, 2011 at 1:28
  • $\begingroup$ How large can $n$ be? it seems like some kind of graph-matching might resolve it, maybe not! $\endgroup$
    – Suvrit
    Nov 24, 2011 at 22:24

0

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Browse other questions tagged or ask your own question.