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

Question

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?

Answer 1

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}

Answer 2

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.

Answer 3

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