In mathematics, Karamata's inequality, named after Jovan Karamata, also known as the majorization inequality, is a theorem in elementary algebra for convex and concave real-valued functions, defined on an interval of the real line. It generalizes the discrete form of Jensen's inequality, and generalizes in turn to the concept of Schur-convex functions.
Statement of the inequality Let I be an interval of the real line and let f denote a real-valued, convex function defined on I. If x1, …, xn and y1, …, yn are numbers in I such that (x1, …, xn) majorizes (y1, …, yn), then
Here majorization means that x1, …, xn and y1, …, yn satisfies
and we have the inequalities
and the equality
If f is a strictly convex function, then the inequality (1) holds with equality if and only if y is a permutation of x.
Weak majorization case
x ⪯ w y {\displaystyle x\preceq _{w}y} if and only if ∑ g ( x i ) ≤ ∑ g ( y i ) {\displaystyle \sum g\left(x_{i}\right)\leq \sum g\left(y_{i}\right)} for any continuous increasing convex function g : R → R {\displaystyle g:\mathbb {R} \to \mathbb {R} } .
Remarks
If the convex function f is non-decreasing, then the proof of (1) below and the discussion of equality in case of strict convexity shows that the equality (4) can be relaxed to
The inequality (1) is reversed if f is concave, since in this case the function −f is convex.
Example The finite form of Jensen's inequality is a special case of this result. Consider the real numbers x1, …, xn ∈ I and let
a := x 1 + x 2 + ⋯ + x n n {\displaystyle a:={\frac {x_{1}+x_{2}+\cdots +x_{n}}{n}}}
denote their arithmetic mean. Then (x1, …, xn) majorizes the n-tuple (a, a, …, a), since the arithmetic mean of the i largest numbers of (x1, …, xn) is at least as large as the arithmetic mean a of all the n numbers, for every i ∈ {1, …, n − 1}. By Karamata's inequality (1) for the convex function f,
f ( x 1 ) + f ( x 2 ) + ⋯ + f ( x n ) ≥ f ( a ) + f ( a ) + ⋯ + f ( a ) = n f ( a ) . {\displaystyle f(x_{1})+f(x_{2})+\cdots +f(x_{n})\geq f(a)+f(a)+\cdots +f(a)=nf(a).}
Dividing by n gives Jensen's inequality. The sign is reversed if f is concave.
Proof of the inequality We may assume that the numbers are in decreasing order as specified in (2). If xi = yi for all i ∈ {1, …, n}, then the inequality (1) holds with equality, hence we may assume in the following that xi ≠ yi for at least one i. If xi = yi for an i ∈ {1, …, n}, then the inequality (1) and the majorization properties (3) and (4) are not affected if we remove xi and yi. Hence we may assume that xi ≠ yi for all i ∈ {1, …, n}. It is a property of convex functions that for two numbers x ≠ y in the interval I the slope
f ( x ) − f ( y ) x − y {\displaystyle {\frac {f(x)-f(y)}{x-y}}}
of the secant line through the points (x, f (x)) and (y, f (y)) of the graph of f is a monotonically non-decreasing function in x for y fixed (and vice versa). This implies that
for all i ∈ {1, …, n − 1}. Define A0 = B0 = 0 and
A i = x 1 + ⋯ + x i , B i = y 1 + ⋯ + y i {\displaystyle A_{i}=x_{1}+\cdots +x_{i},\qquad B_{i}=y_{1}+\cdots +y_{i}}
for all i ∈ {1, …, n}. By the majorization property (3), Ai ≥ Bi for all i ∈ {1, …, n − 1} and by (4), An = Bn. Hence,
which proves Karamata's inequality (1). To discuss the case of equality in (1), note that x1 > y1 by (3) and our assumption xi ≠ yi for all i ∈ {1, …, n − 1}. Let i be the smallest index such that (xi, yi) ≠ (xi+1, yi+1), which exists due to (4). Then Ai > Bi. If f is strictly convex, then there is strict inequality in (6), meaning that ci+1 < ci. Hence there is a strictly positive term in the sum on the right hand side of (7) and equality in (1) cannot hold. If the convex function f is non-decreasing, then cn ≥ 0. The relaxed condition (5) means that An ≥ Bn, which is enough to conclude that cn(An−Bn) ≥ 0 in the last step of (7). If the function f is strictly convex and non-decreasing, then cn > 0. It only remains to discuss the case An > Bn. However, then there is a strictly positive term on the right hand side of (7) and equality in (1) cannot hold.
References
External links An explanation of Karamata's inequality and majorization theory can be found here.