Maximizing Frobenius Norm of Commutator (an opposite Procrustes problem)

Question

I was wondering if anybody has any suggestions on the following problem:

Let $S$ be an $n\times n$ positive definite symmetric matrix. I wish to find an $n\times n$ orthogonal matrix $R$ which MAXIMIZES the Frobenius norm of the commutator, i.e.

$$ R = \arg\max_{R' \in O(N)}||[R',S]||_F^2 = \arg\max_{R' \in O(N)}||R'S - SR'||_F^2, $$ where $O(N)$ is the set of all orthogonal matrices.

Clearly $||[R,S]||_F^2 \leq 2||S||_F^2$, provides an upper bound. I've found some papers which are relevant to this problem, in particular Commutators with maximal Frobenius norm, which identify matrices which satisfy this upper bound, but the resulting matrices will not be orthogonal. I'm not confident the results there are so applicable.

Any ideas, help or suggestions would be greatly appreciated.

Answer 1

Unless I'm mistaken, the following argument provides a solution.

Since the Frobenius norm is orthogonally invariant we can assume without loss of generality that $S$ is diagonal. I'll write $Q$ instead of $R'$ to avoid confusion with matrix transposition.

\begin{equation*} \|QS-SQ\|_F^2 = \|QS\|^2 + \|SQ\|^2 - 2\text{tr}(SQ^TSQ). \end{equation*} So the task is to minimize the trace term (as the first two terms are independent of $Q$). But we know that \begin{equation*} \text{tr}(Q^TSQS) \ge \langle \lambda^{\uparrow}(Q^TSQ),\lambda^{\downarrow}(S)\rangle, \end{equation*} where $\lambda^\downarrow$ denotes the sorted vector of eigenvalues. From this it follows that $Q$ is a suitable permutation matrix that reorders the largest diagonal entries of $S$ to match up with the smallest ones.

Note: We did not require $S$ to be positive definite (the original $S$ in your question can be any symmetric matrix, not just a positive definite one).