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 holds with equality if and only if we have xi = yi for all i ∈ {1, …, n} .

Remarks

<ul> <li>If the convex function f &thinsp; is [non-decreasing](https://bliptext.com/articles/non-decreasing-function), 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 f &thinsp; is [concave](https://bliptext.com/articles/concave-function), since in this case the function −f &thinsp; is convex.</li> </ul>

Example

The finite form of Jensen's inequality is a special case of this result. Consider the real numbers x1, …, xn ∈ I and let 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 for the convex function f , 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. If xi = yi for all i ∈ {1, …, n} , then the inequality 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 and the majorization properties and 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 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 for all i ∈ {1, …, n} . By the majorization property , Ai ≥ Bi for all i ∈ {1, …, n − 1} and by , An = Bn . Hence, which proves Karamata's inequality. To discuss the case of equality in, note that x1 > y1 by 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. Then Ai > Bi . If f   is strictly convex, then there is strict inequality in, meaning that ci+1 < ci . 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 f   is non-decreasing, then cn ≥ 0 . The relaxed condition means that An ≥ Bn , which is enough to conclude that cn(An−Bn) ≥ 0 in the last step of. 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 and equality in cannot hold.