Page 69 - Matrices theory and applications

3. Matrices with Real or Complex Entries
52
we denote by s k (a)the number





a j | card J = k
min
.


j∈J
Definition 3.4.1 Let a =(a 1 ,... ,a n ) and b =(b 1 ,... ,b n ) be two se-
quences of n real numbers. One says that b majorizes a,and onewrites
a ≺ b,if
s k (a) ≤ s k (b), ∀1 ≤ k ≤ n, s n (a)= s n (b).
The functions s k are symmetric:
s k (a)= s k (a σ(1) ,... ,a σ(n) )
for every permutation σ. One thus may always restrict attention to the
case of nondecreasing sequences a 1 ≤ ··· ≤ a n . One has then s k (a)=
a 1 + ··· + a k .The relation a ≺ b for nondecreasing sequences, can now be
written as
≤ b 1 + ··· + b k , k =1,... ,n − 1,
a 1 + ··· + a k
= b 1 + ··· + b n .
a 1 + ··· + a n
The latter equality plays a crucial role in the analysis below. The relation
≺ is a partial ordering.
n
Proposition 3.4.1 Let x, y ∈ IR .Then x ≺ y if and only if for every
real number t,
n n

|x j − t|≥ |y j − t|. (3.3)
j=1 j=1
Proof
We may assume that x and y are nondecreasing. If the inequality (3.3)
holds, we write it first for t outside the interval I containing the x j ’s and
the y j ’s. This gives s n (x)= s n (y). Then we write it for t = x k .Using
s n (x)= s n (y), we obtain
k n

|x j − x k | = (x k − y j )+ (y j − x k )+2(s k (y) − s k (x))
j 1 k+1

≤ |y j − x k | +2(s k (y) − s k (x)),
j
which with (3.3) gives s k (x) ≤ s k (y).
Conversely, let us assume that x ≺ y. Let us define φ(t):= |x j −
j

t|− |y j − t|. This is a piecewise linear function, zero outside I.Its
j
derivative, integer-valued, is piecewise constant. It increases at the points
x j ’s and decreases at the points y j ’s only. If min{φ(t); t ∈ IR} < 0, this

minimum will thus be reached at some x k ,with φ (x k −0) ≤ 0 ≤ φ (x k +0),