Introduction to majorization - Statistical Signal Processing of Complex-Valued Data - page 288

this topic, including proofs and references for all unreferenced results in this chapter,
we refer the reader to the topic by Marshall and Olkin (1979 ).

A3.1 Basic definitions

A3.1.1 Majorization

IR n IR n , written

Definition A3.1. A vector x ∈ is said to be majorized by a vector y ∈

as x ≺ y ,if

r r

x [ i ] ≤ y [ i ] , r = 1 ,..., n − 1 , (A3.1)

i = 1 i = 1

n n

x [ i ] = y [ i ] , (A3.2)

i = 1 i = 1

·

] is a permutation such that x [1] ≥ x [2] ≥···≥ where [ x [ n ] .

That is, the sum of the r largest components of x is less than or equal to the sum of the
r largest components of y , with equality required for the total sum. Intuitively, if x ≺ y ,

the components of x are less spread out or “more equal” than the components of y .

Example A3.1. Under the constraints
n

x i =

,

x i ≥

, = ,..., ,

N 0 i 1 n

i = 1

the vector with the least spread-out components in the sense of majorization is
[ N n ] T , and the vector with the most spread-out components is

/ n , N / n ,..., N /

0] T

[ N , 0 ,..., (or any permutation thereof). Thus, for any vector x ,

1
n [ N

N ] T 0] T , N ,..., ≺ x ≺ [ N , 0 ,..., .

Definition A3.2. If the weaker condition
r r

x [ i ] ≤ y [ i ] , r = 1 ,..., n (A3.3)

i = 1 i = 1

=

holds, without equality for r n, x is said to be weakly majorized by y , written as

≺ w y .
The inequality ( A3.3 ) is sometimes referred to as weak submajorization in order to
distinguish it from another form of weak majorization, which is called weak superma-
jorization. For our purposes, we will not require the concept of weak supermajorization.
Because the components of x and y are reordered in the definitions of majorization and
weak majorization, their original order is irrelevant. Note, however, that majorization is

x