Schur–Horn theorem

In mathematics, particularly linear algebra, the Schur–Horn theorem, named after Issai Schur and Alfred Horn, characterizes the diagonal of a Hermitian matrix with given eigenvalues. It has inspired investigations and substantial generalizations in the setting of symplectic geometry. A few important generalizations are Kostant's convexity theorem, Atiyah–Guillemin–Sternberg convexity theorem, Kirwan convexity theorem.

Statement

Theorem. Let $\mathbf{d}=\{d_i\}_{i=1}^N$ and $\mathbf{\lambda}=\{\lambda_i\}_{i=1}^N$ be vectors in $\mathbb{R}^N$ such that their entries are in non-increasing order. There is a Hermitian matrix with diagonal values $\{d_i\}_{i=1}^N$ and eigenvalues $\{\lambda_i\}_{i=1}^N$ if and only if

$\sum_{i=1}^n d_i \leq \sum_{i=1}^n \lambda_i \qquad n=1,2,\ldots,N$

and

$\sum_{i=1}^N d_i= \sum_{i=1}^N \lambda_i.$

Polyhedral geometry perspective

Permutation polytope generated by a vector

The permutation polytope generated by $\tilde{x} = (x_1, x_2,\ldots, x_n) \in \mathbb{R}^n$ denoted by $\mathcal{K}_{\tilde{x}}$ is defined as the convex hull of the set $\{ (x_{\pi(1)},x_{\pi(2)},\ldots,x_{\pi(n)}) \in \mathbb{R}^n : \pi \in S_n \}$. Here $S_n$ denotes the symmetric group on $\{1, 2, \ldots, n\}$. The following lemma characterizes the permutation polytope of a vector in $\mathbb{R}^n$.

Lemma.^[1][2] If $x_1 \ge x_2 \ge \cdots \ge x_n, y_1 \ge y_2 \ge \cdots \ge y_n$, and $x_1 + x_2 + \cdots + x_n = y_1 + y_2 + \cdots + y_n,$ then the following are equivalent :

(i) $(y_1, y_2, \cdots, y_n)(= \tilde{y}) \in \mathcal{K}_{\tilde{x}}$.

(ii) $y_1 \le x_1, y_1 + y_2 \le x_1 + x_2 , \ldots, y_1 + y_2 + \cdots + y_{n-1} \le x_1 + x_2 + \cdots + x_n$

(iii) There are points $(x_1^{(1)}, x_2 ^{(1)}, \cdots, x_n ^{(1)})(=\tilde{x}_1), \ldots, (x_1^{(n)}, x_2 ^{(n)}, \ldots, x_n^{(n)})(=\tilde{x}_n)$ in $\mathcal{K}_{\tilde{x}}$ such that $\tilde{x}_1=\tilde{x}, \tilde{x}_n=\tilde{y},$ and $\tilde{x}_{k+1} = t \tilde{x}_k + (1-t) \tau(\tilde{x_k})$ for each $k$ in $\{1, 2, \ldots, n-1 \}$, some transposition $\tau$ in $S_n$, and some $t$ in $[0,1]$, depending on $k$.

Reformulation of Schur–Horn theorem

In view of the equivalence of (i) and (ii) in the lemma mentioned above, one may reformulate the theorem in the following manner.

Theorem. Let $\mathbf{d}=\{d_i\}_{i=1}^N$ and $\mathbf{\lambda}=\{\lambda_i\}_{i=1}^N$ be real vectors. There is a Hermitian matrix with diagonal entries $\{d_i\}_{i=1}^N$ and eigenvalues $\{\lambda_i\}_{i=1}^N$ if and only if the vector $(d_1, d_2, \ldots, d_n)$ is in the permutation polytope generated by $(\lambda_1, \lambda_2, \ldots, \lambda_n)$.

Note that in this formulation, one does not need to impose any ordering on the entries of the vectors $\mathbf{d}$ and $\mathbf{\lambda}$.

Proof of the Schur–Horn theorem

Let $A(=a_{jk})$ be a $n \times n$ Hermitian matrix with eigenvalues $\{ \lambda_i \}_{i=1}^{n}$, counted with multiplicity. Denote the diagonal of $A$ by $\tilde{a}$, thought of as a vector in $\mathbb{R}^n$, and the vector $(\lambda_1, \lambda_2, \ldots, \lambda_n)$ by $\tilde{\lambda}$. Let $\Lambda$ be the diagonal matrix having $\lambda_1, \lambda_2, \ldots, \lambda_n$ on its diagonal.

($\Rightarrow$) $A$ may be written in the form $U\Lambda U^{-1}$, where $U$ is a unitary matrix. Then

$a_{ii} = \sum_{j=1}^n \lambda_j |u_{ij}|^2, \; i = 1, 2, \ldots, n$

Let $S = (s_{ij})$ be the matrix defined by $s_{ij} = |u_{ij}|^2$. Since $U$ is a unitary matrix, $S$ is a doubly stochastic matrix and we have $\tilde{a} = S\tilde{\lambda}$. By the Birkhoff–von Neumann theorem, $S$ can be written as a convex combination of permutation matrices. Thus $\tilde{a}$ is in the permutation polytope generated by $\tilde{\lambda}$. This proves Schur's theorem.

($\Leftarrow$) If $\tilde{a}$ occurs as the diagonal of a Hermitian matrix with eigenvalues $\{ \lambda_i \}_{i=1}^n$, then $t\tilde{a} + (1-t)\tau(\tilde{a})$ also occurs as the diagonal of some Hermitian matrix with the same set of eigenvalues, for any transposition $\tau$ in $S_n$. One may prove that in the following manner.

Let $\xi$ be a complex number of modulus $1$ such that $\overline{\xi a_{jk}} = - \xi a_{jk}$ and $U$ be a unitary matrix with $\xi \sqrt{t}, \sqrt{t}$ in the $j,j$ and $k,k$ entries, respectively, $-\sqrt{1-t^2}, \xi \sqrt{1-t^2}$ at the $j,k$ and $k,j$ entries, respectively, $1$ at all diagonal entries other than $j,j$ and $k,k$, and $0$ at all other entries. Then $UAU^{-1}$ has $ta_{jj} + (1-t)a_{kk}$ at the $j,j$ entry, $(1-t)a_{jj} + ta_{kk}$ at the $k,k$ entry, and $a_{ll}$ at the $l,l$ entry where $l \ne j,k$. Let $\tau$ be the transposition of $\{1, 2, \ldots, n\}$ that interchanges $j$ and $k$.

Then the diagonal of $UAU^{-1}$ is $t\tilde{a} + (1-t)\tau(\tilde{a})$.

$\Lambda$ is a Hermitian matrix with eigenvalues $\{ \lambda_i \}_{i=1}^n$. Using the equivalence of (i) and (iii) in the lemma mentioned above, we see that any vector in the permutation polytope generated by $(\lambda_1, \lambda_2, \ldots, \lambda_n)$, occurs as the diagonal of a Hermitian matrix with the prescribed eigenvalues. This proves Horn's theorem.

Symplectic geometry perspective

The Schur–Horn theorem may be viewed as a corollary of the Atiyah–Guillemin–Sternberg convexity theorem in the following manner. Let $\mathcal{U}(n)$ denote the group of $n \times n$ unitary matrices. Its Lie algebra, denoted by $\mathfrak{u}(n)$, is the set of skew-Hermitian matrices. One may identify the dual space $\mathfrak{u}(n)^*$ with the set of Hermitian matrices $\mathcal{H}(n)$ via the linear isomorphism $\Psi : \mathcal{H}(n) \rightarrow \mathfrak{u}(n)^*$ defined by $\Psi(A)(B) = \mathrm{tr}(iAB)$ for $A \in \mathcal{H}(n), B \in \mathfrak{u}(n)$. The unitary group $\mathcal{U}(n)$ acts on $\mathcal{H}(n)$ by conjugation and acts on $\mathfrak{u}(n)^*$ by the coadjoint action. Under these actions, $\Psi$ is an $\mathcal{U}(n)$-equivariant map i.e. for every $U \in \mathcal{U}(n)$ the following diagram commutes,

Let $\tilde{\lambda} = (\lambda_1, \lambda_2, \ldots, \lambda_n) \in \mathbb{R}^n$ and $\Lambda \in \mathcal{H}(n)$ denote the diagonal matrix with entries given by $\tilde{\lambda}$. Let $\mathcal{O}_{\tilde{\lambda}}$ denote the orbit of $\Lambda$ under the $\mathcal{U}(n)$-action i.e. conjugation. Under the $\mathcal{U}(n)$-equivariant isomorphism $\Psi$, the symplectic structure on the corresponding coadjoint orbit may be brought onto $\mathcal{O}_{\tilde{\lambda}}$. Thus $\mathcal{O}_{\tilde{\lambda}}$ is a Hamiltonian $\mathcal{U}(n)$-manifold.

Let $\mathbb{T}$ denote the Cartan subgroup of $\mathcal{U}(n)$ which consists of diagonal complex matrices with diagonal entries of modulus $1$. The Lie algebra $\mathfrak{t}$ of $\mathbb{T}$ consists of diagonal skew-Hermitian matrices and the dual space $\mathfrak{t}^*$ consists of diagonal Hermitian matrices, under the isomorphism $\Psi$. In other words, $\mathfrak{t}$ consists of diagonal matrices with purely imaginary entries and $\mathfrak{t}^*$ consists of diagonal matrices with real entries. The inclusion map $\mathfrak{t} \hookrightarrow \mathfrak{u}(n)$ induces a map $\Phi : \mathcal{H}(n) \cong \mathfrak{u}(n)^* \rightarrow \mathfrak{t}^*$, which projects a matrix $A$ to the diagonal matrix with the same diagonal entries as $A$. The set $\mathcal{O}_{\tilde{\lambda}}$ is a Hamiltonian $\mathbb{T}$-manifold, and the restriction of $\Phi$ to this set is a moment map for this action.

By the Atiyah–Guillemin–Sternberg theorem, $\Phi(\mathcal{O}_{\tilde{\lambda}})$ is a convex polytope. A matrix $A \in \mathcal{H}(n)$ is fixed under conjugation by every element of $\mathbb{T}$ if and only if $A$ is diagonal. The only diagonal matrices in $\mathcal{O}_{\tilde{\lambda}}$ are the ones with diagonal entries $\lambda_1, \lambda_2, \ldots, \lambda_n$ in some order. Thus, these matrices generate the convex polytope $\Phi(\mathcal{O}_{\tilde{\lambda}})$. This is exactly the statement of the Schur–Horn theorem.

Notes

1. Kadison, R. V., Lemma 5, The Pythagorean Theorem: I. The finite case, Proc. Natl. Acad. Sci. USA, vol. 99 no. 7 (2002):4178–4184 (electronic)
2. Kadison, R. V.; Pedersen, G. K., Lemma 13, Means and Convex Combinations of Unitary Operators, Math. Scand. 57 (1985),249–266

References

• Schur, Issai, Über eine Klasse von Mittelbildungen mit Anwendungen auf die Determinantentheorie, Sitzungsber. Berl. Math. Ges. 22 (1923), 9–20.
• Horn, Alfred, Doubly stochastic matrices and the diagonal of a rotation matrix, American Journal of Mathematics 76 (1954), 620–630.
• Kadison, R. V.; Pedersen, G. K., Means and Convex Combinations of Unitary Operators, Math. Scand. 57 (1985),249–266.
• Kadison, R. V., The Pythagorean Theorem: I. The finite case, Proc. Natl. Acad. Sci. USA, vol. 99 no. 7 (2002):4178–4184 (electronic)

External links

• MathWorld