Nearest symmetric matrix, of a given spectrum, to a given diagonal matrix

Question

Let $D_1$ and $D_2$ be real, $m\times m$ diagonal matrices, and define $$f(U)=\|D_1-U^\intercal D_2 U\|_F\;,$$ a function on $m\times m$ orthogonal matrices $U$. This is a "nearest matrix" problem in the Frobenius ($F$) norm.

I conjecture that the minimum of $f$ is always attained when $U$ is a permutation matrix. Any help proving this conjecture, or finding a counterexample, will be much appreciated! It's enough if you can prove that permutation matrices are the only critical points of $f$. If it helps, you may assume the elements of $D_1$ and $D_2$ are distinct real numbers.

Answer 1

This is treated as Problem A in Moody T. Chu and Kenneth R. Driessel, The Projected Gradient Method for Least Squares Matrix Approximations with Spectral Constraints (doi, nonpaywalled pdf). They give your desired result in the case of distinct eigenvalues. They also point to a follow up paper treating the case of repeated eigenvalues.

ADDED: The proof suggested in the comment by Nathaniel Johnston is much simpler than the one I pointed to. I thought I would include it here for completeness since it is very short:

$$\begin{aligned} f(U) &= \mathrm{tr}(D_1 - U^T D_2 U)^2 \\ &= \mathrm{tr}(D_1^2+D_2^2-2D_1U^TD_2U) \\ &= \mathrm{tr}(D_1^2+D_2^2-2(\mathbf{d}_1 \mathbf{d}_2^T)(U\circ U)) \end{aligned}$$ Since $U\circ U$ is doubly-stochastic it is a convex combination of permutation matrices. Since $f(U)$ is affine in $U\circ U$, it can be no smaller than the smallest value attained by a permutation matrix.

Answer 2

This more than answers my question, thank you! Much as I like Birkhoff-von Neumann, something more elementary would go over better with my audience. Here's what I came up with:

We'll assume the elements of $D_1$ are distinct and for finding critical points will work instead with the simpler function $$g(U)=\mathrm{Tr}(D_1 U D_2 U^\intercal)\;,$$ which differs from $f$ by a factor $-2$ and constants.

We are interested in the linear variation with $X$ of $g(U+X)$, where $X$ is subject to a linear constraint to keep $U+X$ orthogonal. From $$1=(U+X)(U+X)^\intercal=1+XU^\intercal+(XU^\intercal)^\intercal+O(X^2)\;,$$ we see that this constraint is that $XU^\intercal$ is antisymmetric. Let $A$ be any $m\times m$ antisymmetric matrix, then $X=AU$. Using this for the parametrization of the perturbation, we obtain $$g(U+AU)=g(U)+\mathrm{Tr}\left(A(UD_2U^\intercal D_1-D_1UD_2U^\intercal)\right)+O(A^2)\;,$$ where we used $A^\intercal=-A$. The linear term has the form $\mathrm{Tr}(AB)$, where $B$ is also antisymmetric. Since $A$ is any antisymmetric matrix, $\mathrm{Tr}(AB)=0$ implies $B=0$. To evaluate $B$, first define $C_2=UD_2U^\intercal$, and work out the $(i,j)$ element, for $i\ne j$: $$(B)_{i j}=\left((D_1)_{jj}-(D_1)_{ii}\right)(C_2)_{ij}\;.$$ Since these are all zero, and the elements of $D_1$ are distinct, this shows that $C_2$ is diagonal. But $C_2$ has the same spectrum as $D_2$, so the basis change $U$ must be just permutations and sign flips of the basis.