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 is a permutation of .
Weak majorization case if and only if for any continuous increasing convex function .
Remarks If the convex function is non-decreasing, then the proof of () below and the discussion of equality in case of strict convexity shows that the equality () can be relaxed to
The inequality () is reversed if is concave, since in this case the function is convex.
Example 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 (and vice versa). 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.
References
External links An explanation of Karamata's inequality and majorization theory can be found here.