Why does $\rho'=\sum_i p_i U_i \rho U_i^\dagger$ with $U_i$ unitary imply $\rho'\preceq \rho$?

Let $$\rho$$ be an Hermitian matrix with unit trace (this is the context I've found this result stated in, but I don't know if these restrictions are necessary for the result). Suppose $$p_i\ge0$$ with $$\sum_i p_i=1$$, and let $$U_i$$ be unitaries. Consider $$\rho'= \sum_i p_i \, U_i \rho U_i^\dagger.$$ Then $$\rho'\preceq \rho$$, by which I mean that the vector of eigenvalues of $$\rho'$$ is majorized by that of $$\rho$$. I think this is shown in the reference "A. Uhlmann, Wiss. Z. Karl-Marx-Univ. Leipzig 20, 633 (1971)" but I could not find an English version of it.

For $$p_i=\delta_{i0}$$ the result is clear, as $$U\rho U^\dagger$$ has the same eigenvalues of $$\rho$$. How do you prove the general case?

This is a consequence of the following result: for a size $$n$$ Hermitian matrix $$A$$, let $$\lambda_1(A) \geq \lambda_2(A) \geq\cdots \geq \lambda_n(A)$$ denote the eigenvalues of $$A$$. For symmetric matrices $$A_1,\dots, A_m$$, we have $$\sum_{j=1}^k \lambda_j\left(\sum_{p=1}^m A_p \right) \leq \sum_{j=1}^k \sum_{p=1}^m \lambda_j(A_p).$$ This in turn can be seen as a consequence of the fact that $$\sum_{j=1}^k \lambda_j(A) = \max_{U \in \Bbb C^{n\times k}, U^\dagger U = I} \operatorname{tr}(U^\dagger A U).$$

Explanation of the inequality: note that \begin{align} \sum_{j=1}^k \lambda_j\left(\sum_{p=1}^m A_p \right) &= \max\left\{\operatorname{tr}\left[U\left(\sum_{p=1}^m A_p \right)U^\dagger \right]: U \in \Bbb C^{n\times k}, U^\dagger U = I\right\} \\ & = \max\left\{\sum_{p=1}^m \operatorname{tr}\left[UA_pU^\dagger\right] : U \in \Bbb C^{n\times k}, U^\dagger U = I\right\} \\ & \leq \max\left\{\sum_{p=1}^m \operatorname{tr}\left[U_pA_pU_p^\dagger\right] : U_p \in \Bbb C^{n\times k}, U_p^\dagger U_p = I \text{ for } p = 1,\dots,m \right\} \end{align}

• thanks. About the last relation, aren't you effectively just computing $\max_P \operatorname{tr}(AP)$ maximising over trace-$k$ projections $P$ (with the relation following from some variation of the minmax theorem I guess)? Is there a reason to write it as a maximisation over unitaries this way? – glS Jul 14 '20 at 11:53
• you are also using I think, to go from the third to the second equation, the relation $\lambda_j(UA_p U^\dagger)\le \lambda_j(A_p)$ with $U^\dagger U=I$. Where does this come from? – glS Jul 14 '20 at 12:05
• @glS Yes it's equivalent; note that $$\operatorname{tr}(U^\dagger AU) = \operatorname{tr}(A[UU^\dagger]).$$ There is no particular reason to write it one way or the other, but this is the form I learned first. – Ben Grossmann Jul 14 '20 at 12:11
• @glS Your second comment is not correct. See my latest edit for clarification. – Ben Grossmann Jul 14 '20 at 12:13
• thank you for the clarification. Are you possibly missing a few traces in the last equation? Shoud be $\max$ of $\operatorname{tr}$ – glS Jul 14 '20 at 14:27

For any Hermitian matrix $$A$$, let $$c>0$$ be any sufficiently large number. Then $$A+cI$$ is positive semidefinite and $$\sum_{i=1}^k\lambda^\downarrow_i(A) =\sum_{i=1}^k\lambda^\downarrow_i(A+cI)-kc =\|A+cI\|_k-kc,$$ where $$\|\cdot\|_k$$ here denotes the Ky Fan $$k$$-norm (the sum of the largest $$k$$ singular values) of a matrix. The inequality $$\rho'\preceq\rho$$ now follows directly from the triangle inequality for Ky Fan $$k$$-norm.

Remark. Ky Fan was an ethnic Chinese mathematician whose first name was Ky and whose last name is Fan. As it is customary to use only the surname when we name something after a mathematician, the norm is more appropriately called Fan $$k$$-norm rather than Ky Fan $$k$$-norm. However, what has become convention is hard to change. I will keep using the term "Ky Fan $$k$$-norm" in future.

This is a reformulation of the information provided by the other great answers.

The question relates to the eigenvalues of $$\rho'\equiv \sum_{k=1}^m p_k U_k \rho U_k^\dagger$$. Consider the matrices $$A_k=p_k U_k \rho U_k^\dagger$$. Being $$U_k$$ unitary, $$\rho$$ Hermitian, and $$p_k\ge0$$, it follows that $$A_k$$ are hermitian.

Denote with $$\lambda_k^\downarrow(A)$$ the $$k$$-th largest eigenvalue of $$A$$. The relation $$\rho'\preceq\rho$$ means, explicitly, that $$\sum_{j=1}^k \lambda_j^\downarrow\bigg(\underbrace{\sum_{p=1}^m A_p}_{\equiv\rho'} \bigg)\le \sum_{j=1}^k\lambda_j^\downarrow(\rho),\qquad k=1,..,m.$$

It is a general result that, given Hermitian matrices $$A_p$$, and denoting with $$\|A\|_k$$ the sum of the $$k$$ largest eigenvalues of $$A$$ (this is also referred to as the Ky Fan norm of $$A$$), we have $$\|\sum_p A_p\|_k\le \sum_p \|A_p\|_k$$. This is shown e.g. in this answer.

In our specific case, we thus have $$\|\rho'\|_k = \bigg\|\sum_{\ell=1}^m A_\ell\bigg\|_k \le \sum_{\ell=1}^m \|A_\ell\|_k = \sum_{j=1}^k \sum_{\ell=1}^m \lambda_j^\downarrow(A_\ell).$$

From the definition of $$A_p$$, we also have that $$\lambda_j^\downarrow(A_\ell)=p_\ell \lambda_j^\downarrow(\rho)$$, and thus, because $$\sum_\ell p_\ell=1$$, $$\|\rho'\|_k \le \sum_{j=1}^k\lambda_j^\downarrow(\rho) = \|\rho\|_k.$$