1
Article
Majorization and Karamata Inequality
MathLinks - www.mathlinks.ro
Pham Kim Hung, Stanford University, US
www.VNMATH.com
2
Note
This is an excerpt from the second volume of ”Secrets In Inequalities”, by Pham
Kim Hung. The author thanks sincerely Darij Grinberg for some of his materials
about Symmetric Majorization Theorem, posted on Mathlinks Forum. Please don’t
use this excerpt for any commercial purpose.
The Author always appriciates every Contribution to this content- Majorization and
Karamata Inequality.
Best Regard,
Pham Kim Hung
www.VNMATH.com
Chapter 1
Theory of Majorization
The theory of majorization and convex functions is an important and difficult part
of inequalities, with many nice and powerful applications. will discuss in this article
is Karamata inequality; however, it’s necessary to review first some basic properties
of majorization.
Definition 1. Given two sequences (a)=(a
1
,a
2
, , a
n
) and (b)=(b
1

n
= b
1
+ b
2
+ + b
n
;
a
1
+ a
2
+ + a
k
≥ b
1
+ b
2
+ + b
k
∀k ∈{1, 2, n − 1} .
Definition 2. For an arbitrary sequence (a)=(a
1
,a
2
, , a
n
), we denote (a
∗
),

1
,a
2
, , a
n
be real numbers and a =
1
n
(a
1
+ a
2
+ + a
n
), then
(a
1
,a
2
, , a
n
)
∗
 (a, a, , a).
Proposition 2. Suppose that a
1
≥ a
2
≥ ≥ a
n

) and (b)=(b
1
,b
2
, , b
n
) be two sequences of
real numbers. We have that (a
∗
) majorizes (b) if the following conditions are fulfilled
b
1
≥ b
2
≥ ≥ b
n
;
a
1
+ a
2
+ + a
n
= b
1
+ b
2
+ + b
n
;

1
+ x
2
+ + x
n
= y
1
+ y
2
+ + y
n
and
x
i
x
j
≥
y
i
y
j
∀i<j, then
(x
1
,x
2
, , x
n
)  (y
1

+ + y
n
y
1
⇒ x
1
≥ y
1
.
Consider two sequences (x
1
+ x
2
,x
3
, , x
n
) and (y
1
+ y
2
,y
3
, , y
n
). By the inductive
hypothesis, we get
(x
1
+ x

2
, , b
n
) are two sequences of real numbers; then
(a
∗
)  (b
∗
) if and only if for all real numbers x we have
|a
1
− x| + |a
2
− x| + + |a
n
− x|≥|b
1
− x|+ |b
2
− x| + + |b
n
− x|.
Proof. To prove this theorem, we need to prove the following.
(i). Necessary condition. Suppose that (a
∗
)  (b
∗
), then we need to prove that
for all real numbers x
|a

1
or x ≤ b
n
, because in these cases, we have
RHS = |b
1
+ b
2
+ + b
n
− nx| = |a
1
+ a
2
+ + a
n
− nx|≤LHS.
Consider the case when there exists an integer k ∈{1, 2, , n −1} for which b
k
≥ x ≥
b
k+1
. In this case, we can remove the absolute value signs of the right-hand expression
of ()
|b
1
− x| + |b
2
− x| + + |b
k

a
i
,
and similarly,
n

i=k+1
|a
i
− x| =
n

i=k+1
|x − a
i
|≥(n −k)x −
n

i=k+1
a
i
.
Combining the two results and noticing that
k

i=1
a
i
≥
k


i=k+1
a
i
=2
k

i=1
a
i
−
n

i=1
a
i
+(n − 2k)x ≥ 2
k

i=1
b
i
−
n

i=1
b
i
+(n − 2k)x =
n

n
and b
1
≥ b
2
≥
≥ b
n
. Because () is true for all x ∈ R, if we choose x ≥ max{a
i
,b
i
}
n
i=1
then
n

i=1
|a
i
− x| = nx −
n

i=1
a
i
;
n


n
i=1
, then
n

i=1
|a
i
− x| = −nx +
n

i=1
a
i
;
n

i=1
|b
i
− x| = −nx +
n

i=1
b
i
;
⇒ a
1
+ a

2
+ +a
k
≥ b
1
+b
2
+ +b
k
.
Indeed, we can eliminate the absolute value signs on the left-hand expression of ()
as follows
|a
1
− x| + |a
2
− x| + + |a
k
− x| = a
1
+ a
2
+ + a
k
− kx ;
|a
k+1
− x| + |a
k+2
− x|+ + |a

i=1
|b
i
− x| =
k

i=1
|b
i
− x| +
n

i=k+1
|x − b
i
|
≥−kx +
k

i=1
b
i
+(n − k)x −
n

i=k+1
|b
i
| =(n − 2k)x +2
k

|−
n

i=1
|b
i
|
⇒ a
1
+ a
2
+ + a
k
≥ b
1
+ b
2
+ + b
k
,
which is exactly the desired result. The proof is completed.
∇
The Symmetric Majorization Criterion asserts that when we examine the ma-
jorization of two sequences, it’s enough to examine only one conditional inequality
which includes a real variable x. This is important because if we use the normal
method, there may too many cases to check.
The essential importance of majorization lies in the Karamata inequality, which
will be discussed right now.
www.VNMATH.com
Chapter 2

Proof. WLOG, assume that a
1
≥ a
2
≥ ≥ a
n
and b
1
≥ b
2
≥ ≥ b
n
. The inductive
hypothesis yields (a)=(a
∗
)  (b
∗
)=(b). Notice that f is a twice differentiable
function on I (that means f

(x) ≥ 0), so by Mean Value theorem, we claim that
f(x) −f(y) ≥ (x −y)f

(y) ∀x, y ∈ I.
From this result, we also have f(a
i
)−f(b
i
) ≥ (a
i

(a
i
− b
i
)f

(b
i
)
=(a
1
− b
1
)(f

(b
1
) −f

(b
2
)) + (a
1
+ a
2
− b
1
− b
2
)(f

)) +

n

i=1
a
i
−
n

i=1
b
i

f

(b
n
) ≥ 0
because for all k ∈{1, 2, ,n} we have f

(b
k
) ≥ f

(b
k+1
) and
k


i
≥
n

i=1
b
i
.
2. A similar result for concave functions is that
 If (a)  (b) are number arrays and f is a concave function twice differentiable
then
f(a
1
)+f(a
2
)+ + f(a
n
) ≤ f(b
1
)+f(b
2
)+ + f(b
n
).
3. If f is convex (that means αf(a)+βf (b) ≥ f(αa + βb) ∀α, β ≥ 0,α+ β =1)
but not twice differentiable (f

(x) does not exist), Karamata inequality is still true.
A detailed proof can be seen in the book Inequalities written by G.H Hardy, J.E
Littewood and G.Polya.

(x)=(a, a, a, b, t, t, t, b, b, c, c, c); (y)=(α,α,α,α,β,β,β,β,γ,γ,γ,γ);
where
t =
a + b + c
3
,α=
a + b
2
,β=
a + c
2
,γ=
b + c
2
.
Clearly, we have that (y) is a monotonic sequence. Moreover
a ≥ α, 3a + b ≥ 4α, 3a + b + t ≥ 4α + β, 3a + b +3t ≥ 4α +3β,
3a +2b +3t ≥ 4α +4β,3a +3b +3t ≥ 4α +4β + γ,
3a +3b +3t + c ≥ 4α +4β +2γ, 3a +3b +3t +3c ≥ 4α +4β +4γ.
Thus (x
∗
)  (y) and therefore (x
∗
)  (y
∗
). By Karamata inequality, we conclude
3(f(x)+f(y)+f(z)+f(t)) ≥ 4(f(α)+f(β)+f(γ)) ,
which is exactly the desired result. We are done.
∇
Example 2.2 (Jensen Inequality). If f is a convex function then

, , a
n
)  (a, a, , a) with a =
1
n
(a
1
+ a
2
+ + a
n
). Our problem is
directly deduced from Karamata inequality for these two sequences.
∇
Example 2.3. Let a, b, c, x, y, z be six real numbers in I satisfying
a + b + c = x + y + z, max(a, b, c) ≥ max(x, y, z), min(a, b, c) ≤ min(x, y, z),
then for every convex function f on I, we have
f(a)+f(b)+f(c) ≥ f(x)+f(y)+f(z).
Solution. Assume that x ≥ y ≥ z. The assumption implies (a, b, c)
∗
 (x, y, z) and
the conclusion follows from Karamata inequality.
∇
Example 2.4. Let a
1
,a
2
, , a
n
be positive real numbers. Prove that


.
Solution. Our inequality is equivalent to
ln(1+a
1
)+ln(1+a
2
)+ +ln(1+a
n
) ≤ ln

1+
a
2
1
a
2

+ln

1+
a
2
2
a
3

+ +ln

1+

, , k
n
) is a permutation of (1, 2, ,n). Therefore the number
sequence (c) = (2 ln a
1
−ln a
2
, 2lna
2
−ln a
3
, , 2lna
n
−ln a
1
) can be rearranged into
a new one as
(c

) = (2 ln a
k
1
− ln a
k
1
+1
, 2lna
k
2
− ln a

2
)+ + f(c
n
) ≥ f(b
1
)+f(b
2
)+ + f(b
n
),
where c
i
=2lna
k
i
− ln a
k
i
+1
and b
i
=lna
k
i
for all i ∈{1, 2, , n}. Choosing f(x)=
ln(1 + e
x
), we have the desired result.
Comment. 1. A different choice of f(x) can make a different problem. For example,
with the convex function f(x)=

3
+ +

1+
a
2
n
a
1
.
www.VNMATH.com
10
2. By Cauchy-Schwarz inequality, we can solve this problem according to the fol-
lowing estimation

1+
a
2
1
a
2

(1 + a
2
) ≥ (1 + a
1
)
2
.
∇

2
+ + a
n
+ +
a
n
a
1
+ + a
n−1
.
Solution. For each i ∈{1, 2, ,n}, we denote
y
i
=
a
i
a
1
+ a
2
+ + a
n
,x
i
=
a
2
i
a


i=1
y
i
1 − y
i
.
WLOG, assume that a
1
≥ a
2
≥ ≥ a
n
, then certainly x
1
≥ x
2
≥ ≥ x
n
and
y
1
≥ y
2
≥ ≥ y
n
. Moreover, for all i ≥ j, we also have
x
i
x

n
). Furthermore,
f(x)=
x
1 − x
is a convex function, so by Karamata inequality, the final result follows immediately.
∇
Example 2.6. Suppose that (a
1
,a
2
, , a
2n
) is a permutation of (b
1
,b
2
, , b
2n
) which
satisfies b
1
≥ b
2
≥ ≥ b
2n
≥ 0. Prove that
(1 + a
1
a

i
=lnb
i
. We need to prove that
f(x
1
+ x
2
)+f(x
3
+ x
4
)+ + f(x
2n−1
+ x
2n
)
≤ f(y
1
+ y
2
)+f (y
3
+ y
4
)+ + f(y
2n−1
+ y
2n
).

2
≥ ≥ y
n
,if(x
∗
)=(x
∗
1
,x
∗
2
, , x
∗
n
)
is a permutation of elements of (x) which are rearranged in the decreasing order, then
y
1
+ y
2
+ + y
2k
≥ x
∗
1
+ x
∗
2
+ + x
∗

2
d
2
+ d
2
a
2
+ a
2
c
2
+ b
2
d
2
.
(Turkevici’s inequality)
Solution. To prove this problem, we use the following lemma
 For all real numbers x,y,z,t then
2(|x|+ |y|+ |z|+|t|)+|x+ y +z + t|≥|x +y|+ |y +z|+ |z +t|+|t +x|+ |x+ z|+|y +t|.
We will not give a detailed proof of this lemma now (because the next problem shows
a nice generalization of this one, with a meticulous solution). At this time, we will
clarify that this lemma, in combination with Karamata inequality, can directly give
Turkevici’s inequality. Indeed, let a = e
a
1
,b = e
b
1
,c = e

Because f (x)=e
x
is convex, it suffices to prove that (a
∗
) majorizes (b
∗
) with
(a)=(4a
1
, 4b
1
, 4c
1
, 4d
1
,a
1
+ b
1
+ c
1
+ d
1
,a
1
+ b
1
+ c
1
+ d

2|a
1
+ b
1
+ c
1
+ d
1
− 4x
1
| +

cyc
|4a
1
− 4x
1
|≥

sym
|2a
1
+2b
1
− 4x
1
|.
Letting now x = a
1
−x

1
,a
2
, , a
n
be non-negative real numbers. Prove that
(n − 1)(a
2
1
+ a
2
2
+ + a
2
n
)+n
n

a
2
1
a
2
2
a
2
n
≥ (a
1
+ a

, 2x
2
, , 2x
2
  
n−1
, , 2x
n
, 2x
n
, , 2x
n
  
n−1
, 2x, 2x, , 2x

 
n
);
(b)=(x
1
+ x
1
,x
1
+ x
2
,x
1
+ x

n
). By the Symmetric Majorization Criterion, it suffices
to prove that
(n − 2)
n

i=1
|x
i
| + |
n

i=1
x
i
|≥
n

i=j
|x
i
+ x
j
|.
Denote A = {i


x
i
≥ 0},B = {i

)+

i∈A,j∈B
|x
i
− x
j
|.
Because k + m = n, we can rewrite the inequality above into
(k − 1)

i∈A
x
i
+(m −1)

j∈B
x
j
+ |

i∈A
x
i
−

j∈B
x
j
|≥

| = {i ∈ A|x
j
≤ x
i
} and
s
j
= |B
j
|. Thus the left-hand side expression in () can be rewritten as

i∈A
(k − 2r
i
)x
i
+

j∈B
(m −2s
j
)x
j
.
Therefore () becomes

i∈A
(2r
i
− 1)x

j
− 1)x
j
≥ 0.
www.VNMATH.com
13
Notice that if s
j
≥ 1 for all j ∈{1, 2, ,n} then we have the desired result immedi-
ately. Otherwise, assume that there exists a number s
l
= 0, then
max
i∈A∪B
x
i
∈ B ⇒ r
i
≥ 1 ∀i ∈{1, 2, , m}.
Thus

i∈A
r
i
x
i
+

j∈B
(s

∇
Example 2.9. Let a
1
,a
2
, , a
n
be positive real numbers with product 1. Prove that
a
1
+ a
2
+ + a
n
+ n(n − 2) ≥ (n − 1)

1
n−1
√
a
1
+
1
n−1
√
a
2
+ +
1
n−1

a
j
.
First we will prove the following result (that helps us prove the previous inequality
immediately): if x
1
,x
2
, , x
n
are real numbers then (α
∗
)  (β
∗
) with
(α)=(x
1
,x
2
, , x
n
, x, x, , x);
(β)=(y
1
,y
1
, , y
1
,y
2

n −1
.
Indeed, by the symmetric majorization criterion, we only need to prove that
|x
1
|+ |x
2
| + + |x
n
| +(n −2)|S|≥|S − x
1
| + |S −x
2
|+ + |S − x
n
| ()
where S = x
1
+ x
2
+ + x
n
= nx. In case n = 3, this becomes a well-known result
|x|+ |y| + |z| + |x + y + z|≥|x + y| + |y + z|+ |z + x|.
In the general case, assume that x
1
≥ x
2
≥ ≥ x
n

i=1
(x
i
− S)+
n

i=k+1
(S − x
i
)=
k

i=1
x
i
−
n

i=k+1
x
k+1
+(n − 2k)S,
≤
n

i=1
|x
i
| +(n −2k)|S|≤
n

1
+a
2
+ +a
n
)

a
n−1
1
+ a
n−1
2
+ + a
n−1
n

.
(Suranji’s inequality)
Solution. We will prove first the following result for all real numbers x
1
,x
2
, , x
n
n(n − 1)
n

i=1
|x

i
< 0}. WLOG, we may assume that
A = {1, 2, , k} and B = {k +1,k +2, , n}, then |A| = k, |B| = n − k = m and
z
i
≥ 0 for all i ∈ A ∪B. The inequality above becomes
n(n −1)



i∈A
z
i
+

j∈B
z
j


+ n







i∈A
z

j

|+

i∈A,j∈B

|z
i
−(n−1)z
j
|+|(n−1)z
i
−z
j
|

Because n = k + m, the previous inequality is equivalent to
n(m −1)

i∈A
z
i
+ n(k −1)

j∈B
z
j
+ n



i
− z
j
| ()
For each i ∈ A we denote
B
i
= { j ∈ B


(n −1)z
i
≥ z
j
} ; B

i
= {j ∈ B


z
i
≥ (n − 1)z
j
} ;
www.VNMATH.com
15
For each j ∈ B we denote
A
j


i∈A
(mn − 2|B

i
|−2(n − 1)|B
i
|) z
i
+

j∈B

kn − 2|A

j
|−2(n − 1)|A
j
|

z
j
.
WLOG, we may assume that

i∈A
z
i
≥


|≥1, then the conclusion follows immediately
(because A

j
⊂ A
j
, then |A
j
|≥1 and |A

j
| +(n − 1)|A
j
|−n ≥ 0 ∀j ∈ B). If not,
we may assume that there exists a certain number r ∈ B for which |A

r
| = 0, and
therefore |A
r
| = 0. Because |A
r
| = 0, it follows that (n −1)z
r
≤ z
i
for all i ∈ A. This
implies that |B
i
|≥|B

j
≥ n

i∈A
z
i
− n

j∈B
z
j
≥ 0.
Therefore (1) has been successfully proved and therefore Suranji’s inequality follows
immediately from Karamata inequality and the Symmetric Majorization Criterion.
∇
Example 2.11. Let a
1
,a
2
, , a
n
be positive real numbers such that a
1
≥ a
2
≥ ≥
a
n
. Prove the following inequality
a

4
3
···
a
n
+ a
1
+ a
2
3
.
(V. Adya Asuren)
Solution. By using Karamata inequality for the concave function f(x)=lnx,we
only need to prove that the number sequence (x
∗
) majorizes the number sequence
(y
∗
) in which (x)=(x
1
,x
2
, , x
n
), (y)=(y
1
,y
2
, , y
n


n

i=1
|z
i
+ z
i+1
|

≥ 2

n

i=1
|z
i
+ z
i+1
+ z
i+2
|

()
www.VNMATH.com
16
for all real numbers z
1
≥ z
2

, , z
8
. For each number i ∈{1, 2, , 8}, we denote c
i
= |z
i
|, then c
i
≥ 0. To
prove this problem, we will prove first the most difficult case z
1
≥ z
2
≥ z
3
≥ z
4
≥ 0 ≥
z
5
≥ z
6
≥ z
7
≥ z
8
. Giving up the absolute value signs, the problem becomes
3(c
1
+2c

+|c
3
+c
4
−c
5
|+|c
4
−c
5
−c
6
|+c
5
+2c
6
+2c
7
+c
8
+|c
7
+c
8
−c
1
|+|c
8
−c
1

+ c
4
− c
5
| +2|c
4
− c
5
− c
6
| +2|c
7
+ c
8
− c
1
|+2|c
8
− c
1
− c
2
|
Clearly, this inequality is obtained by adding the following results
2|c
4
− c
5
| +2c
3

≥ 2|c
4
− c
5
− c
6
|
|c
8
− c
1
| + c
8
+ c
1
+2c
2
≥ 2|c
8
− c
1
− c
2
|
For other cases when there exist exactly three (or five); two (or six); only one (or seven)
non-negative numbers in {z
1
,z
2
, , z