Karamata's inequality


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 be an interval of the real line and let denote a real-valued, convex function defined on. If and are numbers in such that majorizes, then
Here majorization means that and satisfies
and we have the inequalities
and the equality
If   is a strictly convex function, then the inequality holds with equality if and only if we have for all.

Remarks

The finite form of Jensen's inequality is a special case of this result. Consider the real numbers and let
denote their arithmetic mean. Then majorizes the -tuple, since the arithmetic mean of the largest numbers of is at least as large as the arithmetic mean of all the numbers, for every. By Karamata's inequality for the convex function,
Dividing by gives Jensen's inequality. The sign is reversed if   is concave.

Proof of the inequality

We may assume that the numbers are in decreasing order as specified in.
If for all, then the inequality holds with equality, hence we may assume in the following that for at least one.
If for an, then the inequality and the majorization properties and are not affected if we remove and. Hence we may assume that for all.
It is a property of convex functions that for two numbers in the interval the slope
of the secant line through the points and of the graph of   is a monotonically non-decreasing function in for fixed. This implies that
for all. Define and
for all. By the majorization property, for all and by,. Hence,
which proves Karamata's inequality.
To discuss the case of equality in, note that by and our assumption for all. Let be the smallest index such that, which exists due to. Then. If   is strictly convex, then there is strict inequality in, meaning that. Hence there is a strictly positive term in the sum on the right hand side of and equality in cannot hold.
If the convex function   is non-decreasing, then. The relaxed condition means that, which is enough to conclude that in the last step of.
If the function   is strictly convex and non-decreasing, then. It only remains to discuss the case. However, then there is a strictly positive term on the right hand side of and equality in cannot hold.