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

Schur–Horn theorem — Theorem. Let ${\displaystyle d_{1},\dots ,d_{N}}$ and ${\displaystyle \lambda _{1},\dots ,\lambda _{N}}$ be two sequences of real numbers arranged in a non-increasing order. There is a Hermitian matrix with diagonal values ${\displaystyle d_{1},\dots ,d_{N}}$ (in this order, starting with ${\displaystyle d_{1}}$ at the top-left) and eigenvalues ${\displaystyle \lambda _{1},\dots ,\lambda _{N}}$ if and only if

$${\displaystyle \sum _{i=1}^{n}d_{i}\leq \sum _{i=1}^{n}\lambda _{i}\qquad n=1,\dots ,N-1}$$

and

$${\displaystyle \sum _{i=1}^{N}d_{i}=\sum _{i=1}^{N}\lambda _{i}.}$$

The inequalities above may alternatively be written:

$${\displaystyle {\begin{alignedat}{7}d_{1}&\;\leq \;&&\lambda _{1}\\[0.3ex]d_{2}+d_{1}&\;\leq &&\lambda _{1}+\lambda _{2}\\[0.3ex]\vdots &\;\leq &&\vdots \\[0.3ex]d_{N-1}+\cdots +d_{2}+d_{1}&\;\leq &&\lambda _{1}+\lambda _{2}+\cdots +\lambda _{N-1}\\[0.3ex]d_{N}+d_{N-1}+\cdots +d_{2}+d_{1}&\;=&&\lambda _{1}+\lambda _{2}+\cdots +\lambda _{N-1}+\lambda _{N}.\\[0.3ex]\end{alignedat}}}$$

The Schur–Horn theorem may thus be restated more succinctly and in plain English:

Schur–Horn theorem: Given any non-increasing real sequences of desired diagonal elements ${\displaystyle d_{1}\geq \cdots \geq d_{N}}$ and desired eigenvalues ${\displaystyle \lambda _{1}\geq \cdots \geq \lambda _{N},}$ there exists a Hermitian matrix with these eigenvalues and diagonal elements if and only if these two sequences have the same sum and for every possible integer ${\displaystyle n,}$ the sum of the first ${\displaystyle n}$ desired diagonal elements never exceeds the sum of the first ${\displaystyle n}$ desired eigenvalues.

Reformation allowing unordered diagonals and eigenvalues

Although this theorem requires that ${\displaystyle d_{1}\geq \cdots \geq d_{N}}$ and ${\displaystyle \lambda _{1}\geq \cdots \geq \lambda _{N}}$ be non-increasing, it is possible to reformulate this theorem without these assumptions.

We start with the assumption ${\displaystyle \lambda _{1}\geq \cdots \geq \lambda _{N}.}$ The left hand side of the theorem's characterization (that is, "there exists a Hermitian matrix with these eigenvalues and diagonal elements") depends on the order of the desired diagonal elements ${\displaystyle d_{1},\dots ,d_{N}}$ (because changing their order would change the Hermitian matrix whose existence is in question) but it does not depend on the order of the desired eigenvalues ${\displaystyle \lambda _{1},\dots ,\lambda _{N}.}$

On the right hand right hand side of the characterization, only the values of ${\displaystyle \lambda _{1}+\cdots +\lambda _{n}}$ depend on the assumption ${\displaystyle \lambda _{1}\geq \cdots \geq \lambda _{N}.}$ Notice that this assumption means that the expression ${\displaystyle \lambda _{1}+\cdots +\lambda _{n}}$ is just notation for the sum of the ${\displaystyle n}$ largest desired eigenvalues. Replacing the expression ${\displaystyle \lambda _{1}+\cdots +\lambda _{n}}$ with this written equivalent makes the assumption ${\displaystyle \lambda _{1}\geq \cdots \geq \lambda _{N}}$ completely unnecessary:

Schur–Horn theorem: Given any ${\displaystyle N}$ desired real eigenvalues and a non-increasing real sequence of desired diagonal elements ${\displaystyle d_{1}\geq \cdots \geq d_{N},}$ there exists a Hermitian matrix with these eigenvalues and diagonal elements if and only if these two sequences have the same sum and for every possible integer ${\displaystyle n,}$ the sum of the first ${\displaystyle n}$ desired diagonal elements never exceeds the sum of the ${\displaystyle n}$ largest desired eigenvalues.

Permutation polytope generated by a vector

The permutation polytope generated by ${\displaystyle {\tilde {x}}=(x_{1},x_{2},\ldots ,x_{n})\in \mathbb {R} ^{n}}$ denoted by ${\displaystyle {\mathcal {K}}_{\tilde {x}}}$ is defined as the convex hull of the set ${\displaystyle \{(x_{\pi (1)},x_{\pi (2)},\ldots ,x_{\pi (n)})\in \mathbb {R} ^{n}:\pi \in S_{n}\}.}$ Here ${\displaystyle S_{n}}$ denotes the symmetric group on ${\displaystyle \{1,2,\ldots ,n\}.}$ In other words, the permutation polytope generated by ${\displaystyle (x_{1},\dots ,x_{n})}$ is the convex hull of the set of all points in ${\displaystyle \mathbb {R} ^{n}}$ that can be obtained by rearranging the coordinates of ${\displaystyle (x_{1},\dots ,x_{n}).}$ The permutation polytope of ${\displaystyle (1,1,2),}$ for instance, is the convex hull of the set ${\displaystyle \{(1,1,2),(1,2,1),(2,1,1)\},}$ which in this case is the solid (filled) triangle whose vertices are the three points in this set. Notice, in particular, that rearranging the coordinates of ${\displaystyle (x_{1},\dots ,x_{n})}$ does not change the resulting permutation polytope; in other words, if a point ${\displaystyle {\tilde {y}}}$ can be obtained from ${\displaystyle {\tilde {x}}=(x_{1},\dots ,x_{n})}$ by rearranging its coordinates, then ${\displaystyle {\mathcal {K}}_{\tilde {y}}={\mathcal {K}}_{\tilde {x}}.}$

The following lemma characterizes the permutation polytope of a vector in ${\displaystyle \mathbb {R} ^{n}.}$

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 ${\displaystyle d_{1},\dots ,d_{N}}$ and ${\displaystyle \lambda _{1},\dots ,\lambda _{N}}$ be real numbers. There is a Hermitian matrix with diagonal entries ${\displaystyle d_{1},\dots ,d_{N}}$ and eigenvalues ${\displaystyle \lambda _{1},\dots ,\lambda _{N}}$ if and only if the vector ${\displaystyle (d_{1},\ldots ,d_{n})}$ is in the permutation polytope generated by ${\displaystyle (\lambda _{1},\ldots ,\lambda _{n}).}$

Note that in this formulation, one does not need to impose any ordering on the entries of the vectors ${\displaystyle d_{1},\dots ,d_{N}}$ and ${\displaystyle \lambda _{1},\dots ,\lambda _{N}.}$

Proof of the Schur–Horn theorem

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

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

$${\displaystyle a_{ii}=\sum _{j=1}^{n}\lambda _{j}|u_{ij}|^{2},\;i=1,2,\ldots ,n.}$$

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

(${\displaystyle \Leftarrow }$) If ${\displaystyle {\tilde {a}}}$ occurs as the diagonal of a Hermitian matrix with eigenvalues ${\displaystyle \{\lambda _{i}\}_{i=1}^{n},}$ then ${\displaystyle 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 ${\displaystyle \tau }$ in ${\displaystyle S_{n}.}$ One may prove that in the following manner.

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

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

${\displaystyle \Lambda }$ is a Hermitian matrix with eigenvalues ${\displaystyle \{\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 ${\displaystyle (\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 ${\displaystyle {\mathcal {U}}(n)}$ denote the group of ${\displaystyle n\times n}$ unitary matrices. Its Lie algebra, denoted by ${\displaystyle {\mathfrak {u}}(n),}$ is the set of skew-Hermitian matrices. One may identify the dual space ${\displaystyle {\mathfrak {u}}(n)^{*}}$ with the set of Hermitian matrices ${\displaystyle {\mathcal {H}}(n)}$ via the linear isomorphism ${\displaystyle \Psi :{\mathcal {H}}(n)\rightarrow {\mathfrak {u}}(n)^{*}}$ defined by ${\displaystyle \Psi (A)(B)=\mathrm {tr} (iAB)}$ for ${\displaystyle A\in {\mathcal {H}}(n),B\in {\mathfrak {u}}(n).}$ The unitary group ${\displaystyle {\mathcal {U}}(n)}$ acts on ${\displaystyle {\mathcal {H}}(n)}$ by conjugation and acts on ${\displaystyle {\mathfrak {u}}(n)^{*}}$ by the coadjoint action. Under these actions, ${\displaystyle \Psi }$ is an ${\displaystyle {\mathcal {U}}(n)}$-equivariant map i.e. for every ${\displaystyle U\in {\mathcal {U}}(n)}$ the following diagram commutes,

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

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

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

Notes

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
• Terry Tao: 254A, Notes 3a: Eigenvalues and sums of Hermitian matrices
• Sheela Devadas, Peter J. Haine, Keaton Stubis: The Schur-Horn Theorem