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

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?

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.$$
• This response does not answer my question; you’ve just quoted theorem Theorem 1.1 in the linked paper which bounds the optimal matching distance in the 2-norm in terms of the Frobenius norm. I’m interested in bounding the optimal matching distance in the $\infty$-norm in terms of the spectral norm. Aug 1, 2021 at 17:14