Is Sun's spectral variation bound for normal matrices optimal?

Question

In On the variation of the spectrum of a normal matrix, Sun proves the following result (Corollary 1.2):

Let $A$ be an $n$-square normal matrix and $B$ an arbitrary $n$-square matrix. Then $$ \min_{\sigma \in S_n} \max_{1\le i\le n} |\lambda_i(A) - \lambda_{\sigma(i)}(B)| \le C(n) \|A-B\|,\quad C(n) = n, \label{1}\tag{$\star$}$$ where $\|\cdot\|$ is the spectral norm.

This result is a direct consequence of a result for the Frobenius norm (Theorem 1.1), which is shown to be optimal. However, the spectral norm result above is not shown to be optimal: the example provided only shows that the constant $C(n)$ in \eqref{1} must be at least $\sqrt{n}$.

Further work by Li and Sun provides additional hypotheses under which $C(n)$ can be taken to be smaller, but I have not seen any results which improve \eqref{1} under the sole hypothesis of normality of $A$.

I'm interested in the optimality of the constant $C(n)$ in \eqref{1}. Can the constant $C(n)$ in \eqref{1} be improved? Is it possible that $C(n) = o(n)$ works? Is there a lower bound better than $C(n) = \Omega(\sqrt{n})$ as shown by Sun?

Answer 1

Theorem(Sun) Let $A$ be an $n × n$ normal matrix having eigenvalues $λ_1, \dots , λ_n$ and $B$ be any n×n matrix having eigenvalues $μ1, \dots , μn$. Then there is a permutation $p$ on ${1, 2, . . . , n}$ such that $$ (\sum_{i=1}^n |λi − μ_{p(i)}|^2)^{1/2} \leq \sqrt{n}∥A − B∥_F. $$