In mathematics, Karamata's inequality,[1] named after Jovan Karamata,[2] 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

edit

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

  (1)

Here majorization means that x1, …, xn and y1, …, yn satisfies

     and      (2)

and we have the inequalities

      for all i ∈ {1, …, n − 1}. (3)

and the equality

  (4)

If f  is a strictly convex function, then the inequality (1) holds with equality if and only if we have xi = yi for all i ∈ {1, …, n}.

Remarks

edit
  • 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 (4) can be relaxed to
      (5)
  • The inequality (1) is reversed if f  is concave, since in this case the function f  is convex.

Example

edit

The finite form of Jensen's inequality is a special case of this result. Consider the real numbers x1, …, xnI 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 (1) for the convex function f,

 

Dividing by n gives Jensen's inequality. The sign is reversed if f  is concave.

Proof of the inequality

edit

We may assume that the numbers are in decreasing order as specified in (2).

If xi = yi for all i ∈ {1, …, n}, then the inequality (1) holds with equality, hence we may assume in the following that xiyi for at least one i.

If xi = yi for an i ∈ {1, …, n}, then the inequality (1) and the majorization properties (3) and (4) are not affected if we remove xi and yi. Hence we may assume that xiyi for all i ∈ {1, …, n}.

It is a property of convex functions that for two numbers xy 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

  (6)

for all i ∈ {1, …, n − 1}. Define A0 = B0 = 0 and

 

for all i ∈ {1, …, n}. By the majorization property (3), AiBi for all i ∈ {1, …, n − 1} and by (4), An = Bn. Hence,

  (7)

which proves Karamata's inequality (1).

To discuss the case of equality in (1), note that x1 > y1 by (3) and our assumption xiyi for all i ∈ {1, …, n − 1}. Let i be the smallest index such that (xi, yi) ≠ (xi+1, yi+1), which exists due to (4). 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 AnBn, which is enough to conclude that cn(AnBn) ≥ 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

edit
  1. ^ Kadelburg, Zoran; Đukić, Dušan; Lukić, Milivoje; Matić, Ivan (2005), "Inequalities of Karamata, Schur and Muirhead, and some applications" (PDF), The Teaching of Mathematics, 8 (1): 31–45, ISSN 1451-4966
  2. ^ Karamata, Jovan (1932), "Sur une inégalité relative aux fonctions convexes" (PDF), Publ. Math. Univ. Belgrade (in French), 1: 145–148, Zbl 0005.20101
edit

An explanation of Karamata's inequality and majorization theory can be found here.