Rahul Sharma (Editor)

Karamata's inequality

Updated on
Edit
Like
Comment
Share on FacebookTweet on TwitterShare on LinkedInShare on Reddit

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.

Contents

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

and, after relabeling the numbers x(1), . . . , x(n) and y(1), . . . , y(n), respectively, in decreasing order, i.e.,

we have

If f  is a strictly convex function, then the inequality (1) holds with equality if and only if, after relabeling according to (3), we have x(i) = y(i) for all i ∈ {1, . . . , n}.

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 (2) 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

    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 ) .

    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 (3).

    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 − 1}, then the inequality (1) and the majorization properties (2), (4) are not affected if we remove xi and yi. Hence we may assume that xi ≠ yi for all i ∈ {1, . . . , n − 1}.

    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

    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

    for all i ∈ {1, . . . , n}. By the majorization property (4), Ai ≥ Bi for all i ∈ {1, . . . , n − 1} and by (2), An = Bn. Hence,

    which proves Karamata's inequality (1).

    To discuss the case of equality in (1), note that x1 > y1 by (4) 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 (2). 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

    Karamata's inequality Wikipedia
    (Text) CC BY-SA