Convexity, Schur convexity, and majorization theory - Signal Processing and Optimization for Transceiver Systems - page 707

When y majorizes x , this is denoted as

y x

or equivalently x ≺ y . ♦

Other equivalent statements are (a) the sequence y k majorizes x k ,and(b) x is
majorized by y . The statement

y x on S

means that x and y both belong to a subset of real vectors (e.g., subset with

non-negative elements), and that y majorizes x in that subset. A closely related
concept is the idea of multiplicative majorization, mentioned briefly in Sec. 21.6.

S

Relation to convex functions

There is a simple relation between the concept of majorization and the concept
of convex functions. (Convex functions are reviewed in Sec. 21.2.) The following
relation was observed by Hardy, Littlewood, and Polya [1952]:

Theorem 21.2. Convex functions and majorization. Given two vectors x
and y ,wehave y x if and only if

♠

P− 1 P− 1

g ( y k ) ≥ g ( x k )

k =0 k =0

for all continuous convex functions g ( x ). ♦

A proof of this beautiful result can be found on p. 108 of Marshall and Olkin
[1979].

Example 21.2: Majorization

We can readily verify that [4 2 1] [322 . More nontrivially, consider

the vectors

x =[ P P ... P ] T and z =[1 0 ... 0] T ,
where P is the number of elements in each vector. Then x i = z i =1 .
Furthermore it is obvious that
n

n

z [ k ] ≥ x [ k ] , 0 ≤ n ≤ P − 2 .

k =0 k =0

y P− 1 ] T

So z x . Given any vector y =[ y 0 y 1 ... such that y k ≥ 0

and k y k =1 , we will in fact show that

z y x . (21 . 28)