Schur–Horn theorem

Remarks

Schur proved that the condition is necessary, and Horn proved that it is sufficient. For necessity, write $A = U \Lambda U^*$ with $U$ unitary and $\Lambda$ diagonal; then $d_i = \sum_j \abs{u_{ij}}^2 \lambda_j$. The matrix $(\abs{u_{ij}}^2)$ is doubly stochastic, so $d \prec \lambda$ by the Hardy–Littlewood–Pólya characterisation of majorization. The converse is proved by constructing the matrix, for example by induction on $n$. Example: $\lambda = (2, 0)$ and $d = (1, 1)$ satisfy $d \prec \lambda$, and $\begin{pmatrix} 1 & 1 \\ 1 & 1 \end{pmatrix}$ has eigenvalues $2, 0$ and diagonal $1, 1$. The diagonal $(3, -1)$ is impossible for the eigenvalues $(2, 0)$, since $3 > 2$. The same statement holds with real symmetric matrices in place of Hermitian matrices.

Going deeper

For a student

The case $k = 1$ of the majorization gives $\max_i d_i \le \max_j \lambda_j$, a special case of the Rayleigh quotient bound. The theorem identifies the set of diagonals of the matrices $U \Lambda U^*$, $U$ unitary, with the permutohedron, the convex hull of the permutations of $\lambda$. In this form it is a special case of Kostant's convexity theorem and of the convexity theorem of Atiyah and of Guillemin and Sternberg for moment maps. In frame theory it is used to build frames with prescribed norms and frame operator.