Schur–Horn theorem

Short description: Characterizes the diagonal of a Hermitian matrix with given eigenvalues

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 $d_1,\dots ,d_N$ and ${\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 $d_1,\dots ,d_N$ (in this order, starting with $d_1$ at the top-left) and eigenvalues ${\lambda }_1,\dots ,{\lambda }_N$ if and only if $$\sum _{i=1}^n{d}_i\le \sum _{i=1}^n{\lambda }_{i}n=1,\dots ,N-1$$ and $$\sum _{i=1}^N{d}_i=\sum _{i=1}^N{\lambda }_i.$$

The inequalities above may alternatively be written: $$\begin{array}{rlrl}{d}_1& \le & & {\lambda }_1\\ d_2+d_1& \le & & {\lambda }_1+{\lambda }_2\\ ⋮& \le & & ⋮\\ d_{N-1}+\cdots +d_2+d_1& \le & & {\lambda }_1+{\lambda }_2+\cdots +{\lambda }_{N-1}\\ d_N+d_{N-1}+\cdots +d_2+d_1& =& & {\lambda }_1+{\lambda }_2+\cdots +{\lambda }_{N-1}+{\lambda }_N.\\ \end{array}$$

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 $d_1\ge \cdots \ge d_N$ and desired eigenvalues ${\lambda }_1\ge \cdots \ge {\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 $n,$ the sum of the first $n$ desired diagonal elements never exceeds the sum of the first $n$ desired eigenvalues.

Reformation allowing unordered diagonals and eigenvalues

Although this theorem requires that $d_1\ge \cdots \ge d_N$ and ${\lambda }_1\ge \cdots \ge {\lambda }_N$ be non-increasing, it is possible to reformulate this theorem without these assumptions.

We start with the assumption ${\lambda }_1\ge \cdots \ge {\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 $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 ${\lambda }_1,\dots ,{\lambda }_N.$

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

Schur–Horn theorem: Given any $N$ desired real eigenvalues and a non-increasing real sequence of desired diagonal elements $d_1\ge \cdots \ge 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 $n,$ the sum of the first $n$ desired diagonal elements never exceeds the sum of the $n$ largest desired eigenvalues.

Permutation polytope generated by a vector

The permutation polytope generated by $\tilde{x}=(x_1,x_2,\dots ,x_n)\in {\mathbb{ℝ}}^n$ denoted by ${{𝒦}}_{\tilde{x}}$ is defined as the convex hull of the set $\{(x_{\pi (1)},x_{\pi (2)},\dots ,x_{\pi (n)})\in {\mathbb{ℝ}}^n:\pi \in S_n\}.$ Here $S_n$ denotes the symmetric group on $\{1,2,\dots ,n\}.$ In other words, the permutation polytope generated by $(x_1,\dots ,x_n)$ is the convex hull of the set of all points in ${\mathbb{ℝ}}^n$ that can be obtained by rearranging the coordinates of $(x_1,\dots ,x_n).$ The permutation polytope of $(1,1,2),$ for instance, is the convex hull of the set $\{(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 $(x_1,\dots ,x_n)$ does not change the resulting permutation polytope; in other words, if a point $\tilde{y}$ can be obtained from $\tilde{x}=(x_1,\dots ,x_n)$ by rearranging its coordinates, then ${{𝒦}}_{\tilde{y}}={{𝒦}}_{\tilde{x}}.$

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

Lemma — If $x_1\ge \cdots \ge x_n,$ and $y_1\ge \cdots \ge y_n,$ have the same sum $x_1+\cdots +x_n=y_1+\cdots +y_n,$ then the following statements are equivalent:

1. $\tilde{y}:=(y_1,\cdots ,y_n)\in {{𝒦}}_{\tilde{x}}.$
2. $y_1\le x_1,$ and $y_1+y_2\le x_1+x_2,$ and $\dots ,$ and $y_1+y_2+\cdots +y_{n-1}\le x_1+x_2+\cdots +x_{n-1}$
3. There exist a sequence of points ${\tilde{x}}_1,\dots ,{\tilde{x}}_n$ in ${{𝒦}}_{\tilde{x}},$ starting with ${\tilde{x}}_1=\tilde{x}$ and ending with ${\tilde{x}}_n=\tilde{y}$ such that ${\tilde{x}}_{k+1}=t{\tilde{x}}_k+(1-t)\tau (\widetilde{x_k})$ for each $k$ in $\{1,2,\dots ,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 $d_1,\dots ,d_N$ and ${\lambda }_1,\dots ,{\lambda }_N$ be real numbers. There is a Hermitian matrix with diagonal entries $d_1,\dots ,d_N$ and eigenvalues ${\lambda }_1,\dots ,{\lambda }_N$ if and only if the vector $(d_1,\dots ,d_n)$ is in the permutation polytope generated by $({\lambda }_1,\dots ,{\lambda }_n).$

Note that in this formulation, one does not need to impose any ordering on the entries of the vectors $d_1,\dots ,d_N$ and ${\lambda }_1,\dots ,{\lambda }_N.$

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{ℝ}}^n,$ and the vector $({\lambda }_1,{\lambda }_2,\dots ,{\lambda }_n)$ by $\tilde{\lambda }.$ Let $\mathrm{\Lambda }$ be the diagonal matrix having ${\lambda }_1,{\lambda }_2,\dots ,{\lambda }_n$ on its diagonal.

($\Rightarrow$) $A$ may be written in the form $U\mathrm{\Lambda }{U}^{-1},$ where $U$ is a unitary matrix. Then $$a_{ii}=\sum _{j=1}^n{\lambda }_j|u_{ij}{|}^2,i=1,2,\dots ,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},\xi \sqrt{1-t}$ 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 $UA{U}^{-1}$ has $t{a}_{jj}+(1-t)a_{kk}$ at the $j,j$ entry, $(1-t)a_{jj}+t{a}_{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,\dots ,n\}$ that interchanges $j$ and $k.$

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

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

Let $\tilde{\lambda }=({\lambda }_1,{\lambda }_2,\dots ,{\lambda }_n)\in {\mathbb{ℝ}}^n$ and $\mathrm{\Lambda }\in {\mathscr{H}}(n)$ denote the diagonal matrix with entries given by $\tilde{\lambda }.$ Let ${{𝒪}}_{\tilde{\lambda }}$ denote the orbit of $\mathrm{\Lambda }$ under the ${𝒰}(n)$-action i.e. conjugation. Under the ${𝒰}(n)$-equivariant isomorphism $\mathrm{\Psi },$ the symplectic structure on the corresponding coadjoint orbit may be brought onto ${{𝒪}}_{\tilde{\lambda }}.$ Thus ${{𝒪}}_{\tilde{\lambda }}$ is a Hamiltonian ${𝒰}(n)$-manifold.

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

By the Atiyah–Guillemin–Sternberg theorem, $\mathrm{\Phi }({{𝒪}}_{\tilde{\lambda }})$ is a convex polytope. A matrix $A\in {\mathscr{H}}(n)$ is fixed under conjugation by every element of $\mathbb{𝕋}$ if and only if $A$ is diagonal. The only diagonal matrices in ${{𝒪}}_{\tilde{\lambda }}$ are the ones with diagonal entries ${\lambda }_1,{\lambda }_2,\dots ,{\lambda }_n$ in some order. Thus, these matrices generate the convex polytope $\mathrm{\Phi }({{𝒪}}_{\tilde{\lambda }}).$ This is exactly the statement of the Schur–Horn theorem.

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