Let the trace norm of $X$ be

$$\Vert X\Vert_1 := \operatorname{tr} \left(\,(X^\dagger X)^{1/2}\right)$$

and let the operator inequality $A \leq B$ denote that the operator $B-A$ is positive semidefinite.

If the quantum states (finite-dimensional Hermitian positive semidefinite matrices that have unit trace) $\rho$ and $\sigma$ are close to each other in the trace norm, $\Vert \rho - \sigma \Vert_1 \leq \epsilon$, for some small $\epsilon > 0$, does there exist a projector $\Pi$, such that

$$ \begin{aligned} \Pi \rho \Pi &\leq (1+g_1(\epsilon)) \sigma \\ \operatorname{tr} (\Pi \sigma) &\geq 1- g_2(\epsilon) \end{aligned} $$

for some small functions $g_1(\epsilon)$ and $g_2(\epsilon)$, i.e., both $g_1(\epsilon)$ and $g_2(\epsilon)$ tend to $0$ as $\epsilon \to 0$? Note $g_1$ and $g_2$ should be independent of the dimensions of the matrices. Some observations:

  1. This is true for classical states (matrices which commute) and also true when we also sandwich $\sigma$ in the operator inequality (proofs are here).

  2. It seems that this is also true for randomly selected matrices in small dimensions (program and description are here; the Jupyter notebook also contains some more observations).

So far, I have not been able to come up with a way which avoids having a projector on $\sigma$ as well. It seems that using the assumption $\Vert \sqrt{\rho}- \sqrt{\sigma} \Vert_2 \leq \epsilon$, which is equivalent (upto the exponent of $\epsilon$) to the original assumption, is far more easier, since there does not seem to be a lot of ways one can manipulate the trace norm. I have been trying to use a strengthened version of Gresgorin Theorem (Corollary 6.1.6 of Horn & Johnson's 2nd edition of Matrix Analysis) but no luck so far.

Any help or ideas are appreciated.

  • 1
    $\begingroup$ In convex algebraic geometry, the set of positive semidefinite matrices that have unit trace is called the spectraplex. $\endgroup$ Jun 29, 2023 at 6:23
  • $\begingroup$ @Noel : "It seems that this is also true for randomly selected matrices in small dimensions": Can you describe mathematically how you construct the projector? I cannot read your code. $\endgroup$ Jun 29, 2023 at 15:20
  • $\begingroup$ @IosifPinelis In the code, $\sigma$ is WLOG assumed to be diagonal, so I basically search over all possible diagonal projectors (projectors over all combinations of the eigenspace of $\sigma$) and see if they satisfy the conditions. This is done in a slightly more efficient manner $\endgroup$
    – Noel
    Jun 29, 2023 at 15:50

2 Answers 2


Let $\sigma$ be represented by a PD matrix $A$ and $\rho$ by $A+B$. Note that $|B|\ge B$ (in the sense of PSD matrices) and has the same $1$-norm. Also $\Pi |B|\Pi\ge \Pi B \Pi$, so to dominate $\Pi B\Pi $ is always easier than to dominate $\Pi|B|\Pi$. Thus, we can replace $B$ by $|B|$ and assume that $B$ is PD as well, so its trace norm is just its trace.

Now let's take $a<1$ and consider the spectral decomposition of $H$ in which we unite all the eigenvalues of $A$ between $a^{k+1}$ and $a^k$, i.e., we write $H=\oplus H_k$ such that $H_k$ is an invariant subspace of $A$ and $a^{k+1}I\le A\le a^k I$ on $H_k$. Let $d_k$ be the dimension of $H_k$ and let $P_k$ be the projector to $H_k$.

Now we will construct our projector $\Pi$ as the sum of $\Pi_k P_k$ where $\Pi_k$ is a projection within $H_k$, i.e., if $H\ni x=\sum_k x_k$ is the orthogonal decomposition of $x$ with $x_k\in H_k$, we'll have $\Pi x=\sum_k \Pi_k x_k$. Notice that then $\Pi A\Pi\le a^{-1}A$ regardless of the choice of $\Pi_k$ and, if you think a bit, you will realize that this is essentially almost all you can do to ensure that inequality.

Now take a single $H_k$ and consider the operator $P_kBP_k$. Let its trace be $\mu_k$ so that $\sum_k\mu_k=\varepsilon$. Take $\lambda>0$ and remove from $H_k$ the eigenvectors of this operator with eigenvalues greater than $\lambda a^{k+1}$. The dimension of the removed space will be $\le \frac{\mu_k}{\lambda a^{k+1}}$.

On the remaining subspace $V_k\subset H_k$, we have $\langle Bx_k,x_k\rangle\le\lambda \langle Ax_k,x_k\rangle$. Let now $x=\sum_k x_k$, $x_k\in V_k$. Then, choosing some integer $K$, we can write $$ \langle Bx,x\rangle\le \sum_{k,m} |\langle Bx_k,x_m\rangle|= \\ \sum_k \langle Bx_k,x_k\rangle +2\sum_{k,m:k-K\le m\le k-1} |\langle Bx_k,x_m\rangle| \\ +2\sum_{k,m:m< k-K} |\langle Bx_k,x_m\rangle| \\ =\Sigma_1+\Sigma_2+\Sigma_3\,. $$ We have $\Sigma_1\le\lambda\langle Ax,x\rangle$. Also by Cauchy-Schwarz and the positive definiteness of $B$, we have $\Sigma_2\le 2K\Sigma_1$. Thus, the sum of the first two terms is at most $(2K+1)\lambda\langle Ax,x\rangle$. The question is, of course, what to do with $\Sigma_3$. And the answer is that we will just kill it entirely by further reducing $x_k$ to the intersection of the kernels of the corresponding $P_mB$ on $H_k$. Since $P_mB$ is an operator of rank $d_m$ at most, that will reduce the dimension of $V_k$ by at most $\sum_{m:m<k-K}d_m$.

Then we shall have $\Pi B\Pi\le (2K+1)\lambda \Pi A\Pi$ and $$ \Pi(A+B)\Pi\le [1+(2K+1)\lambda]\Pi A\Pi\le [1+(2K+1)\lambda]a^{-1}A\,. $$ On the other hand, the codimension of the final $V_k$ in $H_k$ is at most $D_k=\frac{\mu_k}{\lambda a^{k+1}}+\sum_{m:m<k-K}d_m$, so the trace lost is at most $$ \sum_k a^k D_k=\sum_k \frac{\mu_k}{\lambda a}+\sum_{k,m:m<k-K}a^k d_m \\ =\frac{\varepsilon}{\lambda a}+\sum_m d_m a^{m+1}\frac{a^K}{1-a} \\ \le \frac \varepsilon{\lambda a}+\frac{a^K}{1-a} $$ because $\sum_m d_m a^{m+1}\le \operatorname{tr} A=1$.

Now one can just play with the parameters to balance. Suppose we want the domination with the constant $1+C\delta$ and the trace loss at most $C\Delta$ with $C$ being some absolute constant (say, $5$). Then we are forced to take $a=1-\delta$ and $(2K+1)\lambda\le 3\delta$. We also need $\frac{a^K}{1-a}<\Delta$, which calls for $K=\delta^{-1}\log\frac{1}{\delta\Delta}$ and $\lambda=\delta^2 \left(\log\frac{1}{\delta\Delta}\right)^{-1}$, so our $\varepsilon$ should be less that $\Delta\delta^2\left(\log\frac{1}{\delta\Delta}\right)^{-1}$ to make the conditions compatible. If $\delta=\Delta$, then we get them both around $\sqrt[3]{\varepsilon\log\frac 1\varepsilon}$. This is, probably, not optimal, but you requested just some speed of tending to $0$ with $\varepsilon$ and the power bound is not terribly bad, so I'll stop here.

  • 2
    $\begingroup$ Thank you, this is great. This answer is still pretty non-trivial to me and those who work with me. I do remember looking at this vector space decomposition but obviously could not go too far. I have two soft questions: 1. if I use this result in my research, how would you like to be cited (you can dm me). 2. if you do indeed think this is a simple problem, has a similar technique been used before and if so where? $\endgroup$
    – Noel
    Aug 1, 2023 at 15:00
  • 2
    $\begingroup$ @Noel 1) Just cite MO; they need citations more than I do :lol: 2) Yes, this technique of "geometric stairway decomposition" (the name is mine, I'm not sure what it is officially called, if anything) is pretty standard in analysis though I haven't seen it applied in linear algebra much. The key is that the "short support" functions/sequences cannot interact much with the "long support" ones (what that means depends on the context), so you can localize to same size entries, which often makes life simpler. I picked the idea from Bourgain's paper on $\Lambda(p)$-sets, but it is quite ubiquitous. $\endgroup$
    – fedja
    Aug 1, 2023 at 15:24
  • $\begingroup$ Hi again @fedja, what exactly did you have in mind when you said that you can bound $\Sigma_2 \leq 2K \Sigma_1$ because I was writing this out for myself and I can only do something $O(K^2)$ $\endgroup$
    – Noel
    Sep 21, 2023 at 18:10
  • 1
    $\begingroup$ @Noel Each diagonal sum ($m=k-\ell$ with fixed $\ell=1,\dots,K$) is bounded by $\Sigma_1$ by Cauchy-Schwarz: $|\langle Bx_{k-\ell},x_k\rangle|\le \frac 12[\langle Bx_{k-\ell}, x_{k-\ell}\rangle+\langle Bx_k, x_k\rangle]$ ($B$ is positive definite). $\endgroup$
    – fedja
    Sep 21, 2023 at 18:31

Edit : the following argument does not answer the question and actually appears already in the OP's linked note.

Let $H = 1_{[0,\infty)}$. Let $\Pi$ be the projector defined by functional calculus as $\Pi=H((1+\sqrt{\epsilon})\sigma - \rho)$ and $\Pi'=1-\Pi$. Observe that $\mathrm{tr}(\Pi'(\rho- (1+\sqrt{\epsilon})\sigma)) \geq 0$

Now write $$ \epsilon \geq \|\rho-\sigma\|_1 \geq \mathrm{tr} (\Pi'\rho) - \mathrm{tr}(\Pi'\sigma) \geq \sqrt{\epsilon} \ \mathrm{tr} (\Pi' \sigma)$$ so that $\mathrm{tr}(\Pi \sigma) \geq 1- \sqrt{\epsilon}$. By construction, we have $\Pi ((1+ \sqrt{\epsilon})\sigma - \rho) \Pi \geq 0$ and therefore $\Pi \rho \Pi \leq (1+\sqrt{\epsilon})\Pi \sigma\Pi$.

  • $\begingroup$ I think your $\Pi$ is not in general a projector, even when $\rho$ and $\sigma$ are diagonal. $\endgroup$ Jun 29, 2023 at 15:25
  • 1
    $\begingroup$ You get $ \Pi (1+\sqrt{\epsilon})\sigma \Pi \geq \Pi \rho \Pi$, how do you transform this to $(1+\sqrt{\epsilon})\sigma \geq \Pi \rho \Pi $? It doesn't seem to me that $\Pi$ and $\sigma$ commute. This seems to me to be the same argument as Theorem 2.2 in my notes (github.com/goforashutosh/CloseStatesImplyNiceProjector/blob/…) $\endgroup$
    – Noel
    Jun 29, 2023 at 15:56
  • $\begingroup$ @Noel oops, you are right (and I should have read your notes better) $\endgroup$ Jun 29, 2023 at 16:14
  • $\begingroup$ @IosifPinelis applying a $\{0,1\}$-valued function to a self-adjoint operator always produces a projector. $\endgroup$ Jun 29, 2023 at 16:18
  • $\begingroup$ @GuillaumeAubrun : Right. Somehow I perceived $H$ as $\max(0,\cdot)$. $\endgroup$ Jun 29, 2023 at 16:25

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

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