Karamata's inequality

Short description: Algebra theorem about convex functions

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 x₁, …, x_n and y₁, …, y_n are numbers in I such that (x₁, …, x_n) majorizes (y₁, …, y_n), then

$f(x_1)+\cdots +f(x_n)\ge f(y_1)+\cdots +f(y_n).$

(1)

Here majorization means that x₁, …, x_n and y₁, …, y_n satisfies

$x_1\ge x_2\ge \cdots \ge x_n$    and    $y_1\ge y_2\ge \cdots \ge y_n,$

(2)

and we have the inequalities

$x_1+\cdots +x_i\ge y_1+\cdots +y_i$     for all i ∈ {1, …, n − 1}.

(3)

and the equality

$x_1+\cdots +x_n=y_1+\cdots +y_n$

(4)

If f  is a strictly convex function, then the inequality (1) holds with equality if and only if 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 (4) can be relaxed to

  $x_1+\cdots +x_n\ge y_1+\cdots +y_n.$

  (5)

• 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 x₁, …, x_n ∈ I and let

$a:=\frac{x_1+x_2+\cdots +x_n}{n}$

denote their arithmetic mean. Then (x₁, …, x_n) majorizes the n-tuple (a, a, …, a), since the arithmetic mean of the i largest numbers of (x₁, …, x_n) 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)+\cdots +f(x_n)\ge f(a)+f(a)+\cdots +f(a)=nf(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 (2).

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

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

It is a property of convex functions that for two numbers x ≠ y in the interval I the slope

$\frac{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

$c_{i+1}:=\frac{f(x_{i+1})-f(y_{i+1})}{x_{i+1}-y_{i+1}}\le \frac{f(x_i)-f(y_i)}{x_i-y_i}=:c_i$

(6)

for all i ∈ {1, …, n − 1}. Define A₀ = B₀ = 0 and

$A_i=x_1+\cdots +x_i,B_i=y_1+\cdots +y_i$

for all i ∈ {1, …, n}. By the majorization property (3), A_i ≥ B_i for all i ∈ {1, …, n − 1} and by (4), A_n = B_n. Hence,

$\begin{array}{rl}\sum _{i=1}^n(f(x_i)-f(y_i))& =\sum _{i=1}^n{c}_i(x_i-y_i)\\ & =\sum _{i=1}^n{c}_i(\underset{=x_i}{\underbrace{A_i-A_{i-1}}}-(\underset{=y_i}{\underbrace{B_i-B_{i-1}}}))\\ & =\sum _{i=1}^n{c}_i(A_i-B_i)-\sum _{i=1}^n{c}_i(A_{i-1}-B_{i-1})\\ & =c_n(\underset{=0}{\underbrace{A_n-B_n}})+\sum _{i=1}^{n-1}(\underset{\ge 0}{\underbrace{c_i-c_{i+1}}})(\underset{\ge 0}{\underbrace{A_i-B_i}})-c_1(\underset{=0}{\underbrace{A_0-B_0}})\\ & \ge 0,\end{array}$

(7)

which proves Karamata's inequality (1).

To discuss the case of equality in (1), note that x₁ > y₁ by (3) and our assumption x_i ≠ y_i for all i ∈ {1, …, n − 1}. Let i be the smallest index such that (x_i, y_i) ≠ (x_i+1, y_i+1), which exists due to (4). Then A_i > B_i. If f  is strictly convex, then there is strict inequality in (6), meaning that c_i+1 < c_i. 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 c_n ≥ 0. The relaxed condition (5) means that A_n ≥ B_n, which is enough to conclude that c_n(A_n−B_n) ≥ 0 in the last step of (7).

If the function f  is strictly convex and non-decreasing, then c_n > 0. It only remains to discuss the case A_n > B_n. However, then there is a strictly positive term on the right hand side of (7) and equality in (1) cannot hold.

External links

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