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

Statement[]

Theorem. Let ${\displaystyle \mathbf {d} =\{d_{i}\}_{i=1}^{N}}$ and ${\displaystyle \mathbf {\lambda } =\{\lambda _{i}\}_{i=1}^{N}}$ be two sequences of real numbers arranged in a non-increasing order. There is a Hermitian matrix with diagonal values ${\displaystyle \{d_{i}\}_{i=1}^{N}}$ and eigenvalues ${\displaystyle \{\lambda _{i}\}_{i=1}^{N}}$ if and only if

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

and

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

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,\ldots ,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 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.; , 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