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.
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 .
if and only if for any continuous increasing convex function .
<ul> <li>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 </li>
<li> The inequality () is reversed if   is concave, since in this case the function   is convex.</li> </ul>
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.
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 ). 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.
An explanation of Karamata's inequality and majorization theory can be found here.