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?


1 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. $$

  • 2
    $\begingroup$ 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. $\endgroup$
    – eepperly16
    Aug 1, 2021 at 17:14

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.