If $A\approx_\varepsilon D$, where $D$ is diagonal, is $A$ already almost diagonal?

Question

Let $D$ and $A$ be symmetric positive semidefinite Hermitian matrices such that $\|D-A\|_1 \leq \varepsilon$, where $\|X\|_1 = \operatorname{tr}(\sqrt{X^*X})$. Moreover, let $D$ be diagonal.

Does there exist a unitary $U$ such that $UAU^* = D'$ (we diagonalize $A$) such that $\|D - D'\|_1$ is bounded in terms of $\varepsilon$?

Answer 1

Firstly, note that instead of $\|\cdot\|_1$ we can look at the Hilbert-Schmidt norm $\|A\|_2 = \sqrt{\operatorname{Tr}(A^*A)}$ since $$\|A\|_2 \le \|A\|_1 \le \sqrt{n}\|A\|_2$$ and these constants do not change boundedness/unboundedness.

Secondly, note that we can WLOG assume that $D$ is sorted in increasing order. Then $D'$ becomes $\Lambda(A)$, which is the matrix of eigenvalues of $A$ sorted in increasing order. We can always pass to such situation by looking at $P^*AP$ and $P^*DP$ where $P$ is a permutation matrix.

Thirdly, note that we can assume $\|A\|_2 \le 1$ and $\|D\|_2 \le 2$. Indeed, clearly we can assume $\varepsilon \in \langle 0,1\rangle$ and then $$\|A-D\|_2 \le \varepsilon \implies \left\|\frac{A}{\|A\|_2}-\frac{D}{\|A\|_2}\right\|_2 \le \frac{\varepsilon}{\|A\|_2}, \quad\left\|\frac{D}{\|A\|_2}\right\|_2 \le 1+\varepsilon \le 2$$ which if we prove the claim for $\|A\|_2 \le 1$ and $\|D\|_2 \le 2$ will imply $$\left\|\frac{\Lambda(A)}{\|A\|_2}-\frac{D}{\|A\|_2}\right\|_2 \le \frac{\varepsilon}{\|A\|_2} \implies \|\Lambda(A) - D\|_2\le \varepsilon.$$

Now our claim is that for every $\varepsilon > 0$ there exists a constant $M_\varepsilon >0$ such that for all positive semidefinite matrices $A,D$ with $\|A\|_2 \le 1, \|D\|_2 \le 2$ and $D$ is diagonal sorted in increasing order we have the implication $$\|A-D\|_2 \le \varepsilon \implies \|\Lambda(A)-D\|_2 \le M_\varepsilon \varepsilon.$$

We prove the following lemma:

Let $(A_n)_n$ and $(D_n)_n$ be sequences of positive semidefinite matrices where $\|A_n\|_2 \le 1, \|D_n\|_2 \le 2$ and $D_n$ is a diagonal matrix sorted in increasing order. Assume that $\|A_n - D_n\|_2 \to 0$. Then $\|\Lambda(A_n) - D_n\|_2 \to 0$.

Proof.

Assume $\|A_n-D_n\|_2 \to 0$. Denote $D(A_n)$ the diagonal matrix which consists of the diagonal of $A_n$. We have $$\|A_n-D(A_n)\|_2^2 = \sum_{i\ne j} |(A_n)_{ij}|^2 \le \sum_{i\ne j} |(A_n)_{ij}|^2 + \sum_{i=1}^n |(A_n)_{ii} - (D_n)_{ii}|^2 = \|A_n-D_n\|_2^2 \to 0.$$

Now recall the fact that the eigenvalues of a matrix are continuous functions of its entries. In particular, they are uniformly continuous on the closed ball of radius $2$. So we get $$\|A_n-D(A_n)\|_2 \to 0 \implies \|\Lambda(A_n)-D(A_n)\|_2 = \|\Lambda(A_n)-\Lambda(D(A_n))\|_2 \to 0.$$ Finally, we have by triangle inequality \begin{align} \|\Lambda(A_n)- D_n\|_2 &=\|\Lambda(A_n)-D(A_n)\|_2 + \|D(A_n)-D_n\|_2 \\ &\le \|\Lambda(A_n)-D(A_n)\|_2 + \|A_n-D_n\|_2\\ &\xrightarrow{n\to\infty} 0 \end{align} which proves the lemma.

Now assume that our claim from above is false. This means there exists $\varepsilon > 0$ and sequences of positive semidefinite matrices $(A_n)_n$ and $(D_n)_n$ such that $\|A_n\| \le 1$, $\|D_n\| \le 2$, $D_n$ is diagonal sorted in increasing order such that $$\|A_n - D_n\|_2 \le\varepsilon, \quad \text{ but }\quad \|\Lambda(A_n)-D_n\|_2 \ge n^2\varepsilon.$$

Consider sequences $\left(\frac1nA_n\right)_n$ and $\left(\frac1nD_n\right)_n$. These satisfy the assumptions of our lemma since $$\left\|\frac1nA_n - \frac1nD_n\right\|_2 = \frac1n \|\Lambda(A_n)-D_n\|_2 \le\frac{\varepsilon}n \to 0$$ so $$n\varepsilon \le \left\|\frac1n\Lambda(A_n) - \frac1nD_n\right\|_2 = \left\|\Lambda\left(\frac1n A_n\right) - \frac1nD_n\right\|_2\to 0$$ which is a contradiction. Therefore, our claim is true.