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}

Improve this question
$\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
    Commented Nov 23, 2011 at 19:20
  • $\begingroup$ I have included a counterexample in the edit to my question. Thanks for your help. $\endgroup$
    – Charles Bailey
    Commented 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
    Commented 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$
    – Charles Bailey
    Commented 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
    Commented Nov 24, 2011 at 22:24

0

Reset to default

You must log in to answer this question.

Browse other questions tagged .