HANOI PEDAGOGICAL UNIVERSITY 2
DEPARTMENT OF MATHEMATICS
————oOo————

PHAM HUY HIEU

HERMITIAN MATRIX AND THE SCHUR HORN THEOREM

DRAFT GRADUATION THESIS

HANOI, 05/2019


HANOI PEDAGOGICAL UNIVERSITY 2
DEPARTMENT OF MATHEMATICS
————oOo————

DRAFT GRADUATION THESIS

HERMITIAN MATRIX AND THE SCHUR HORN THEOREM

Supervisor : PHD NGUYEN CHU GIA VUONG
Student

:

PHAM HUY HIEU

Class

: K41CLC

HANOI, 05/2019


Acknowledgment
Before presenting the main content of the thesis, I would like to express my gratitude to the math teachers, Hanoi 2 Pedagogical University,
the teachers in the algebra group as well as the participating teachers.
Teaching has dedicated to convey valuable knowledge and create favorable conditions for me to successfully complete the course and thesis.
In particular, I would like to express my deep respect and gratitude
to PDH Nguyen Chu Gia Vuong, who directly instructed, just told to
help me so that I could complete this thesis.
Due to limited time, capacity and conditions, the discourse cannot
avoid errors. Therefore, I look forward to receiving valuable comments
from teachers and friends.
Student

Pham Huy Hieu


Preface
In mathematics, especially linear algebra, we only attent to matrices
with real coefficients that rarely attent to complex matrices. In fact,
complex matrices are very important and in particular there is a matrix
type with complex coefficients hermitian matrix. The individual values
and the coefficients of their main diagonals are of special relevance. The
Schur -Horn theorem will tell us the relationship. It has inspired investigations and substantial generalizations in the setting of symplectic
geometry.


Contents


1 PRELIMINARIES

2

1.1

Eigenvalues and eigenvectors . . . . . . . . . . . . . . . .

2

1.2

Permutation matrix . . . . . . . . . . . . . . . . . . . . .

3

1.3

Hermitian matrix . . . . . . . . . . . . . . . . . . . . . .

5

1.4

Unitary matrix . . . . . . . . . . . . . . . . . . . . . . .

6

1.5


Bistochastic matrix and Majorization . . . . . . . . . . .

7

1.6

Convex hull . . . . . . . . . . . . . . . . . . . . . . . . .

10

1.7

Birkhoff polytope . . . . . . . . . . . . . . . . . . . . . .

10

2 THE SCHUR-HORN THEOREM

12

2.1

Schur - Horn theorem . . . . . . . . . . . . . . . . . . . .

12

2.2

Proof of the Schur - Horn theorem


12

. . . . . . . . . . . .

3 Application

24

3.1

The Pythagorean Theorem in Finite Dimension . . . . .

24

3.2

The Schur-Horn Theorem in the Finite Dimensional Case

28

References

31

1


Chapter 1
PRELIMINARIES

1.1

Eigenvalues and eigenvectors

Definition 1.1.1. In linear algebra, an eigenvector or characreristic vector of a linear transformation is a non-zero vector that changes by only
a scalar factor when that linear transformation is applied to it. More
formally, if T is a linear transformation from a vector space V over a
field F into itself and v is a vector in V that is not the zero vector, then
v is an eigenvectors of T if T (v) is a scalar multiple of v. This condition
can be written as the equation
T (v) = λv
where λ is a scalar in the field F , known as the eigenvalues, characteristic
values, or characteristic root associated with the eigenvectors v
If the vector space V is finite-dimensional, then the linear transformation T can be represented as a square matrix A, and the vector v
by a column vector, rendering the above mapping as a matrix multiplication on the left-hand side and a scaling of the column vector on the
right-hand side in the equation
Av = λv
2


Schur- Horn theorem

PHAM HUY HIEU

There is a direct correspondence between n − by − n square matrices
and linear transformations from an n-dimensional vector space to itself,
given any basis of the vector space. For this reason, it is equivalent to
define eigenvalues and eigenvectors using either the language of matrices
or the language of linear transformations.
Geometrically, an eigenvector, corresponding to a real non-zero eigenvalue points in a direction that is stretched by the transformation and

the eigenvalues is the factor by which it is stretched. If the eigenvalue is
negative, the direction is reversed.

1.2

Permutation matrix

Definition 1.2.1. Given a permutation π of m elements,

π : {1, . . . , m} → {1, . . . , m}π : {1, . . . , m} → {1, . . . , m}
represented in two-line form by






1
2 ···
m
1
2 ···
m

,

π(1) π(2) · · · π(m)
π(1) π(2) · · · π(m)
,
There are two natural ways to associate the permutation with a permutation matrix; namely, starting with the m × m indentity matrix, Im ,

either permute the columns or permute the rows, according to π. Both
methods of defining permutation matrices appear in the literature and
the properties expressed in one representation.
The m × m permutation matrix Pπ = (pij ) obtained by permuting the
columns of the identity matrix Im , that is, for each i, pij = 1 if j = π(i)
3


Schur- Horn theorem

PHAM HUY HIEU

and 0 otherwise, will be referred to as the column representation in this
article. Since the entries in row i are all 0 except that a 1 appears in
column π(i), we may write




e
 π(1) 


 eπ(2) 

Pπ = 
 .. ,
 . 



eπ(m)
, where ej , a standard basis vector, denotes a row vector of length m
with 1 in the jth position and 0 in every other position.
For example, the permutation matrix Pπ corresponding to the permutation :



1 2 3 4 5
,
π=
1 4 2 5 3

is

   
e
e1
1
 π(1)    

   
eπ(2)  e4  0

   

   
Pπ = eπ(3)  = e2  = 0

   


   
eπ(4)  e5  0

   
eπ(5)
e3
0

0 0 0
0 0 1
1 0 0
0 0 0
0 1 0


0


0


0.


1

0

. Observe that the j th column of the I5 identity matrix now appears as
the π(j th ) column of Pπ .

The other representation, obtained by permuting the rows of the identity matrix Im , that is, for each j, pij = 1 if i = π(j) and 0 otherwise,
will be referred to as the row representation.

4


Schur- Horn theorem

1.3

PHAM HUY HIEU

Hermitian matrix

Definition 1.3.1. In mathematics, a Hermitian matrix (or self-adjoint
matrix) is a complex square matrix that is equal to its own conjugate
transpose—that is, the element in the ith row and jth column is equal to
the complex conjugate of the element in the jth row and ith column, for
all indices i and j:
Hermitian ⇐⇒ aij = aji
or in matrix form:
Hermitian ⇐⇒ A = AT
Hermitian matrices can be understood as the complex extension of real
symmetric matrices.
Example:




2 2+i 4





A = 2 − i 3
i  is a Hermitian matrix


4
−i 1

Proposition 1.3.1. Eigenvalues of an Hermitian matrix are real.
Proof 1.3.1. Let 0 = v ∈ Cn be an eigenvector of A with eigenvalue λ
(A hermitian).
Then
v T Av = λv T v = λ v

2

Taking the conjugate transpose of the previous equation shows that
v T A∗ v = λ v

2

⇒λ=λ

⇒ λ is a real number.
Proposition 1.3.2. Eigenvectors v1 , v2 of an hermitian matrix A corresponding to different eigenvalues λ1 , λ2 are orthogonal (i.e v2 , v1 = 0).
5



Schur- Horn theorem

PHAM HUY HIEU

Proof 1.3.2. We have:
v1 T A∗ v2 = λ2 v2 , v1
and also
v1 T Av2 = v1 T A∗ v2 = λ1 v2 , v1 .
Hence, (λ1 − λ2 ) v2 , v1 = 0.
But λ1 = λ2 , so that v2 , v1 = 0
Therefore, v2 , v1 = v2 , v1 = 0, as claimed.

1.4

Unitary matrix

Definition 1.4.1. (Unitary Matrix)
In mathematics, a complex square matrix U is unitary if its conjugate
transpose U ∗ is also its inverse—that is, if
U ∗ U = U U ∗ = In ,
, where In is the identity matrix.
Example:


cosα −isinα
 is an unitary matrix.
U1 = 
isinα cosα
Properties 1.4.1. For any unitary matrix U of finite size, the following

hold:
1) Given two complex vectors x and y, multiplication by U preserves
their inner product; that is, Ux , Uy = x, y .
2) U is normal.
U is diagonalizable; that is,U is unitarily similar to a diagonal matrix,
as a consequence of the spectral theorem. Thus,U has a decomposition
6


Schur- Horn theorem

PHAM HUY HIEU

of the form 3) U = V DV ∗ , where V is unitary, andD is diagonal and
unitary.
4) |det(U )| = 1.
5) Its eigenspaces are orthogonal.
6) U can be written as U = eiH, where e indicates matrix exponential,
i is the imaginary unit, and H is a Hermitian matrix.

1.5

Bistochastic matrix and Majorization

Definition 1.5.1. (Bistochastic Matrix)
In mathematics, we call an n × n matrix A = aij bistochastic if A has
nonnegative real entries, and, in addition,

n
i=1 ai,j


= 1 for all 1 ≤ j ≤ n

n
j=1 ai,j

= 1 for all 1 ≤ i ≤ n.


1
1
0 2
2



Example 1.5.1 A = 0 1 0 is a bistochastic matrix.


1
1
2 0 2
and

Definition 1.5.2. (Majorization)
Let x = (x1 , ..., xn )andy = (y1 , ..., yn ) are decreasing vectors in Rn . We
say x is majorized by y, denoted by x ≺ y,If

k



x ≤ ki=1 yi , 1 ≤ k ≤ n

 i=1 i





n
i=1 xi

=

n
i=1 yi

Example 1.5.2:
If xi ∈ [0, 1], and

n
i=1 xi

= 1, then we have

1
1
, ...,
n
n


≺ (x1 , ..., xn ) ≺ (1, 0, ..., 0)

Theorem 1.5.1. A matrix A ∈ Mn (R) is bistochastic if and only if
Ax ≺ x, for all x ∈ Rn .
7


Schur- Horn theorem

PHAM HUY HIEU

Proof: For the implication (⇐), assume Ax ≺ x for all vector x. Then
n

n

Ax =
i=1

x.
i=1

From the definition of majorization. is we choose x to be ej , where ej is
the vector ej = (0, ..., 0, 1, 0, ..., 0), 1 ≤ j ≤ n, then

     
a ... a1n
0
a

0
 11
    1,j   
 ..
   .   
.. 
 .
.  1 =  ..  ≺ 1

     
an1 ... ann 0
anj
0
then min {a1j , ..., anj } = min {1, 0} = 0 so akj ≥ 0for all k. Also this
implies, as j was arbitrary, that the sum over each column is 1. To show
the sum over the rows is also 1 we use the vector e =
  
  
n
1
a
1
   j=1 1,j   
 ..  
  .. 
..
. = 
 ≺ . .
.
  

  
n
1
1
j=1 an,j
Then

n
j=1 aij

( since max

n
j=1 ej ;

we get

= 1 for all i.
n
j=1 aij ; j

≤ 1 and min

n
j=1 aij

: j ≥ 1)

For the other direction (⇒), let A be bistochastic, and let y = Ax.
To prove y ≺ x, we first show that we can assume X and y have their

entries in non-increasing order; this because x = P x and y = Qy for
some permutation matrices P and Q, so
Qy = AP x
⇔ y = Q−1 AP x
⇔ y = Bx
where Q−1 AP = B is bistochastic, since the permutation matrices are
bistochastic, and the product of bistochastic matrices is bistochastic.
8


Schur- Horn theorem

PHAM HUY HIEU

For any k ∈ {1, ..., n} we have
k

k

n

yj =
j=1
k
j=1 bji

Let si =

bji xi .
j=1 i=1

n
i=1 si

then 0 ≤ si ≤ 1,
k

= k and

n

yi =
j=1

si x i .
i=1

Then
k

k

n

yj −
j=1

k

si xi −


xi =
j=1

i=1

k

yj −
j=1

n

j=1

from equation (1.5.1),

k

si xi −

xi =

i=1

n

k

si xi −
i=1

k

=

n

si −
n

si x i −

n

xk −

xi +
i=1
k

i=1
k

i=1
k

i=1

n

(1 − si )xi +


(1 − si )xk

n

i=1

(xi − xk )si
i=k+1

≤0

9

si x k −
i=1

i=1

i=k+1

(si − 1)(xi − xk ) +

n

k

(xi − xk )si +

k


si x k

xk −

xi +
i=1

i=k+1

i=1

k

si x i −

si
i=1

k

k

=−

si )xk , sincek =
i=1

i=k+1
n


i=1

n

xi + (k −

si xi +

=

i=1

i=1
n

i=1
k

si )xk

i=1

si xi +

=

n

xi + (


i=1

=

(1.5.1)

i=1
n
i=1 si xk

By adding and subtracting
k

xi

si xk
i=k+1


Schur- Horn theorem
k
j=1 yj

So

≤

PHAM HUY HIEU


k
j=1 xj

for all k. When k = n,

n

n

n

yj =
j=1

bji xj
j=1 i=1
n

=(

n

bi1 )x1 + ... + (
i=1
n

=

bin )xn
i=1


xj
j=1

1.6

Convex hull

Definition 1.6.1. In convex geometry, a convex combination is a linear
combination of points (which can be vectors, scalars, or more generally
points in an affine space) where all coefficients are non-negative and sum
to 1.
More formally, given a finite number of points x1 , x2 , . . . , xn in a real
vector space, a convex combination of these points is a point of the form
n

αi xi = α1 x1 + α2 x2 + · · · + αn xn
i=1

where the real numbers αi αi satisfy αi ≥ 0 and α1 + α2 + · · · + αn = 1.

1.7

Birkhoff polytope

Definition 1.7.1. (Birkhoff polytope)
·Sn group of permutations on {1, ..., n}
·g ∈ Sn ⇒ P (g) corresponding n × n-permutation matrix.

10



Schur- Horn theorem

PHAM HUY HIEU


0


0
e.g : g = (1234) ∈ S4 ⇒ P (g) = 

0

1

1 0 0





0 1 0


0 0 1

0 0 0


·Bn := conv(P (g) : g ∈ Sn ) Birkhoff polytope.
Definition 1.7.2. (Permutation polytopes)
·G ≤ Sn subgroup is permutation group.
·P (G) := conv(P (g) : g ∈ G) is permutation polytope.
Example 1.7.1.
2 . G=

1 . G = Sn ⇒ P (G) = Bn Birkhoff polytope.

1 2 , 3 4 , ..., (2d − 1) 2d

≤ S2d

⇒ P (G) d − cube
3 . G=

1 2 3 ... d + 1

≤ Sd+1

⇒ P (G) d − simplex
Definition 1.7.3. Permutation polytope generated by x
Suppose that n is a positive integer and x is a column vector in Rn .
write Ox for the orbit of x under the action of Πn on Rn , that is, the set
of all points of the form σx for σ ∈ Πn . We call the convex hull of Ox
the permutation polytope generated by x, denoted by Px .

11



Chapter 2
THE SCHUR-HORN THEOREM
2.1

Schur - Horn theorem

Theorem 2.1.1. Let d1 , ..., dn and λ1 , ..., λn be real numbers. There is an
n × n Hermitian matrix with diagonal entries d1 , ..., dn and eigenvalues
λ1 , ..., λn , then the vector (d1 , ..., dn ) lies in the convex hull of the set
of vectors whose coordinates are all possible permutations of (λ1 , ..., λn ).
Conversely,the vector (d1 , ...dn ) lies in the convex hull of the set of vectors
whose coordinates are all possible permutations of (λ1 , ..., λn ), there exists
an n×n Hermitian matrix with diagonal entries d1 , ..., dn and eigenvalues
λ1 , ..., λn .

2.2

Proof of the Schur - Horn theorem

Our proof of the Schur - Horn theorem goes as follows. In 2.2.1,
we show that the vector of diagonal entries of a Hermitian matrix can
be written as the product of a bistochastic matrix with the vector of
eigenvalues, then we finish the proof of this implication of the Schur Horn theorem by applying the Birkhoff-von Neumann theorem, which
characterizes the set of bistochastic matries as the convex hull of the
12


Schur- Horn theorem

PHAM HUY HIEU


set of permutation matrices. In 2.2.2, we turn our attention toward
dealing with the other implication of the Schur - Horn theorem. To
prove the remaining implication we provide an algebraic characterization
of elements of the convex hull of the set of vectors whose coordinates are
all possible permutations of a given vector.
Proof 2.2.1. (All diagonals lie in the permutation polytope)
” Let d1 , ..., dn and λ1 , ..., λn be real numbers. There is an n × n Hermitian matrix with diagonal entries d1 , ..., dn and eigenvalues λ1 , ..., λn ,
then the vector (d1 , ..., dn ) lies in the convex hull of the set of vectors
whose coordinates are all possible permutations of (λ1 , ..., λn ).”
Proof :
Let A ∈ M at(n, C) , A is an n × n Hermitian matrix with λ1 , ..., λn
are eigenvalues, there exist an unita matrix U such that:


λ 0 ...
 1

 0 λ2 ...
−1
U .A.U = Λ = 

 ... ... ...

0 0 ...

 U ∗ = U −1
Since U is an unita matrix then:
U ∗ .U = I


0





0


... 

λn

n

∗

⇒ U .A.U = Λ

u u
 11 12

 u21 u22
Consider U = 

 ... ...

un1 un2
We have:


... u1n





u u

 11 21


u
... u2n 
u
 ⇒ U ∗ =  12 22


 ... ...
... ... 


... unn
u1n u2n

13

... un1






... un2 


... ... 

... unn


Schur- Horn theorem

A = U.Λ.U ∗

u u ...
 11 12

 u21 u22 ...
=

 ... ... ...

un1 un2 ...

λu λu
 1 11 2 12

 λ1 u21 λ2 u22
=


 ...
...

λ1 un1 λ2 un2

h h ...
 11 12

 h21 h22 ...
=

 ... ... ...

hn1 hn2 ...
where : hii =

PHAM HUY HIEU


u1n
λ
 1

u2n   0


...   ...

unn
0




u u
  11 21

λ2 ... 0   u12 u22


... ... ...   ... ...

u1n u2n
0 ... λn


u u ... un1
... λn u1n

  11 21


... λn u2n   u12 u22 ... un2 




...
...   ... ... ... ... 



u1n u2n ... unn
... λn unn

h1n


h2n 


... 

hnn

n
j=1 λj

0 ... 0

... un1





... un2 


... ... 

... unn


|uij |2

Put d = (h11 , ..., hnn ) is diagonal of matrix A
Note: Since u is an unita matrix, then we have:
U ∗ .U = In


u u
 11 12

 u21 u22
⇔

 ... ...

un1 un2

 

u u
  11 21
 
... u2n   u12 u22
.
 
... ...   ... ...
 
u1n u2n
... unn

... u1n

... un1





1
 
 
... un2   0
=
 
... ...  ...
 
... unn
0

0 ... 0





1 ... 0 


... ... ...


0 ... 1

Now, we attend to diagonal entries of U ∗ .U and easy to see that:




2
n
j=1 |uij |

= 1, for i = 1, n



2
n
i=1 |uij |

= 1, for j = 1, n

14

(2.1)


Schur- Horn theorem




2

PHAM HUY HIEU
2

2



|u | |u12 | ... |u1n |
 11


2
2
2
 |u21 | |u22 | ... |u2n | 

Let B = 


 ...
... ... ... 


2
2
2
|un1 | |un2 | ... |unn |


 
2
2
2
|u | |u12 | ... |u1n |
λ
 11
  1

 
 |u21 |2 |u22 |2 ... |u2n |2   λ2 
 
Moreover, B.λ = 

 
 ...
... ... ...   ... 

 
2
2
2
|un1 | |un2 | ... |unn |
λn

  
λ1 |u11 |2 + λ2 |u12 |2 + ... + λn |u1n |2
h

  1


  
 λ1 |u21 |2 + λ2 |u22 |2 + ... + λn |u2n |2   h2 
= =d
=

  
 · · · · · · · · · · · · · · · · · · · · · · · · · · · · · ·   ... 

  
2
2
2
λ1 |un1 | + λ2 |un2 | + ... + λn |unn |
hn
Since the sum of each row and column of B equal to 1( by definiton of
matrix B ) so B is bistochastic.
Following Birkhoff-von Neumann:” Any n × n bistochastic matrix lies
in the convex hull of the group of permutation matrices Πn ” so B is a
convex combination of permutation matrices. Then by the definition of
the action of Πn on Rn , we can see that Bλ is a convex combination
of elements of the orbit of λ, so bλ lies in the permutation polytope
generated by λ. Since Bλ = d, so d lies in the permutation polytope
generated by λ.

Proof 2.2.2. (All elememnts of the permutation polytope are
diagonals)
We prove this by describing the geometry of the permutation polytope through a few elementary algebraic operations which are much more
15



Schur- Horn theorem

PHAM HUY HIEU

manageable to deal with than the pure geometry. In particular, we show
that we can move from one of the vertices of the permutation polytope
generated by (λ1 , ..., λn ) to any other vector in the permutation polytope
by a finite sequence of algebraic operations. We then show that each of
the vectors we get along the way is the diagonal of some hermitian matrix with eigenvalues λ1 , ..., λn .
We introduce the following terminology which is important in this
key description of the permutation polytope.
Definition 2.2.2.1 We say that (x1 , ..., xn ) ∈ Rn is weakly decreasing if
x1 ≥ x2 ≥ · · · ≥ xn .
Lemma 2.2.2.2: Suppose that x = (x1 , ..., xn ) and y = (y1 , ..., yn ) are
weakly decreasing vectors in Rn and that

n
i=1 xi

=

n
i=1 yi .

Then the

following are equivalent.
a) The vector y is in the permutation polytope Px
b) There are vectors v1 , ...vn such that v1 = x, vn = y, for each 1 ≤ m <

n, there is a transposition matrix τm ∈ πn and real number tm ∈ [0, 1]
such that
vm+1 = tm vm + (1 − tm )τm vm ,
and for m > 1 the first m coordinates of vm+1 agree with the first m
coordinates of y.
The proof of Lemma 2.2.2.2 is more technical than one would hope,
so we leave it for the appendix, but describe the main ideas of the proof
here.
Lemma 2.2.2.3 Suppose that d = (d1 , ..., dn ) occurs as the diagonal of
an n × n Hermitian matrix H with eigenvalues λ1 , ..., λn . Then for any
real number t ∈ [0, 1] and any transposition matrix τ ∈ Πn , there exists a
16


Schur- Horn theorem

PHAM HUY HIEU

Hermitian matrix with eigenvalues λ1 , ..., λn and diagonal td + (1 − t)τ d.
Proof

In the case that n = 1 this is trivial, so suppose that n > 1.

Write H = (hij ) and suppose that τ ∈ πn transposes the k th and lth
coordinates. The idea behind this proof is to construct a unitary matrix
U so that U HU ∗ has td + (1 − t)τ d as a diagonal. This matrix will have
the same eigenvalues as H because we are simply changing basis. We
find this matrix U by reducing to the case where n = 2.
When n > 2, by conjugating H by an appropriate matrix P , without
loss of generality, we can assume that k = 1 and l = 2. Thus we

have reduced to the case of finding a Hermitian matrix with diagonal
(td1 + (1 − td2 ), td2 + (1 − t)d1 , d3 , d4 , ..., dn )
Let U be a 2 × 2 unitary matrix and consider the n × n block-diagonal
unitary matrix


U 0

V =
0 In−2

where In−2 denotes the (n−2)×(n−2) indentity matrix. We see that the
diagonal entries of V HV ∗ are exactly the diagonal entries of the matrix


d1 h12
 U∗
U
h21 d2
followed by h33 = d3 , ...hnn = dn . In light of this, the problem of finding
a Hermitian matrix with diagonal (td1 +(1−t)d2 , td2 +(1−t)d1 , d3 , ..., dn )
reduces to the case n = 2.
Thus we may then assume that




d1 h12
,
H=

h21 d2
where h12 = h21 since H is Hermitian.
17


Schur- Horn theorem

PHAM HUY HIEU

Define a complex number ξ by

ih12 / |h12 | , h12 = 0
ξ :=
 1, otherwise.
Then
ξh12 = −ξh12
and |ξ| = 1. Now let


√

√



− 1−t
ξ t

U = √
√

ξ 1−t
t
It is clear by the definitions of the complex number ξ and the entries of
U that U is unnitary. The matrix A = U HU ∗ has the same eigenvalues
as H, and , moreover the diagonal of A is (td1 + (1 − t)d2 , td2 + (1 − t)d1 ),
as desired.
Now, we continue to proof Schur-Horn theorem.
Proposition 2.2.1. Suppose that d = (d1 , ..., dn ) and λ = (λ1 , ..., λn ) are
vectors in Rn . If d lies in the permutation polytope Pλ then there exists
an n × n Hermitian matrix with diagonal d and eigenvalues λ1 , ..., λn .
Proof:
Suppose that d lies in the permutation polytope ganerated by the vectors
λ. As remarked earlier, if d or λ is not weakly decreasing, we say replace
it by a weakly decreasing alement, so, without loss of generality, assume
that both d and λ are weakly decreasing. Then by the equivalence
of (2.2.2.2 b)and (2.2.2.2a) given in lemma 2.2.2.2, there exists vectors
v1 , ..., vn ∈ pλ with v1 = λ, vn = d, and for each integer 1 ≤ m < n,
vm+1 = tm vm + (1 − tm )τm vm
18

(∗1)


Schur- Horn theorem

PHAM HUY HIEU

for some tm ∈ [0, 1] and some transposition matrix τm .
Let V1 denote the diagonal matrix with diagonal v1 = λ since V1
is Hermitian and the vectors vk satisfy the relation (*1), by repeated

application of lemma 2.2.2.2 we see that there are Hermitian matrices
V2 , ..., Vn with diaginals v2 , ..., vn respectively. Since vn = d, this shows
that Vn is a Hermitian matrix with diagonal d, which proves the result.
It is worthwhile to note that if the vector d which we started with was
not weakly decreasing, a simple reodering of the basis. i.e, conjugating
vn by a permutation matrix, gives us a matrix whose diagonal is this
(non-weakly decreasing) vector. Moreover, since the property of being
Hermitian is invariant under conjugation by a unitary matrix, and permutation matrices are, in particular, unitary matrices, this new matrix
is Hermitian too.
Appendix: The proof of a technical result
Lemma 2.2.2.2 Suppose that x = (x1 , ..., xn ) and y = (y1 , ..., yn ) are
weakly decreasing vectors in Rn and that

n
i=1 xi

=

n
i=1 yi .

Then the

following are equivalent.
a) The vector y is in the permutation polytope Px
b) There are vectors v1 , ...vn such that v1 = x, vn = y, for each 1 ≤ m <
n, there is a transposition matrix τm ∈ πn and real number tm ∈ [0, 1]
such that
vm+1 = tm vm + (1 − tm )τm vm ,
and for m > 1 the first m coordinates of vm+1 agree with the first m

coordinates of y.
Proof
We first prove that (a) implies (b), so suppose that (b) holds. first
19


Schur- Horn theorem

PHAM HUY HIEU

notice that by the definition of Px as the convex hull of the orbit Ox of
x, it is clear that for any points z ∈ Px and any permutation σ ∈ Πn ,
the element σz is in Px . Moreover, a convex combination of elements of
Px is in Px . Since x ∈ Px , the obvious induction argument shows that
vi ∈ Px for all integer 1 ≤ i ≤ n. Since vn = y, this shows that y ∈ Px .
Now we prove that (a) implies (b). We set v1 = x, and construct a
vector v2 such that
v2 = t1 v1 + (1 − t)τ1 v1

(A.1.1)

for some t1 ∈ [0, 1] and transposition matrix τ1 ∈ Πn so that the first
coordinate of v2 agrees with the first coordinate of y. Then given vectors
v1 , ..., vn , such that:
(a.1) for all 1 ≤ j < m,
vj+1 = tj vj + (1 − tj )τj vj
for some tj ∈ [0, 1] and transposition τj ∈ Πn ,
(a.2) for all i < j ≤ m, writing vj = (vj,q , ..., vj,n ), we have vj,i = yi show
that the first j − 1 coordinates of vj agree with the first j − 1 coordinate
of y,

(a.3) and

k
i=1 yi

≤

k
i=1 vj,i

for all j ≤ k and k < n and

n
i=1 yi

=

k
i=1 vj,i ,

we construct a vector vm+1 such that
(b.1 )vm+1 = tm vm + (1 − tm )τm vm for some tm ∈ [0, 1] and transposition
τm ∈ Πn ,
(b.2) for all i < m + 1 we have vm+1,i = yi so that the first m coordinates
of vm+1 agree with the first m coordinates of y,
(b.3)

k
i=1 yi


≤

k
i=1 vm+1,i

for all integers k < n and

n
i=1 yi

=

n
i=1 vm+1,i

We begin by making the following observation which is necessary to con20


Schur- Horn theorem

PHAM HUY HIEU

struct v2 from v1 . We want to construct the convex combination (A.1.1)
so that the first coordinate of v2 as a convex combination of the first and
l1th coordinates of v1 for some integer l1 , and then let τ1 be the transposition which interchanges the first and l1th coordinates. It suffices to
find an integer l such that xl ≤ y1 . Since x is weakly decreasing, for any
integer k, with 1≤k≤n, and any permutation σ ∈ Πn ,
k

k


(σx)i ≤

xi .

i=1

i=1

Therefore, if z = (z1 , ...zn ) is a convex combination of elements of the
orbit Ox of x,for any integer k, with 1 ≤ k ≤ n,
k

k

zi ≤
i=1

xi .
i=1

In particular, this is true for y since y ∈ Px . Using this observation we
can show that there exists an integer l, with 2 ≤ l ≤ y1 . To see this,
suppose, for the sake of contradiction, that there exists no such integer.
Then

k

k


yi ≤
i=1

xi ,
i=1

which contradicts the assumption that

k
i=1 yi

=

k
i=1 xi .

Let l1 be the

least greater than 1 such that xl1 ≤ y1 . Now we are ready to construct
v2 . Since xl1 ≤ y1 ≤ x1 , there exists some real number t1 ∈ [0, 1] such
that
y1 = t1 x1 + (1 − t)xl1 .
Let τ ∈ Πn be the transposition matrix which interchanges the first and
(l1 )th coordinates. Set v1 := x and define
v2 := t1 v1 = (1 − t1 )τ1 v1 .
21