Karamata's inequality

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

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

${\displaystyle f(x_{1})+\cdots +f(x_{n})\geq f(y_{1})+\cdots +f(y_{n}).}$

(1)

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

${\displaystyle x_{1}\geq x_{2}\geq \cdots \geq x_{n}}$    and    ${\displaystyle y_{1}\geq y_{2}\geq \cdots \geq y_{n},}$

(2)

and we have the inequalities

${\displaystyle x_{1}+\cdots +x_{i}\geq y_{1}+\cdots +y_{i}}$     for all i ∈ {1, …, n − 1}.

(3)

and the equality

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

  ${\displaystyle x_{1}+\cdots +x_{n}\geq 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

${\displaystyle 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,

${\displaystyle f(x_{1})+f(x_{2})+\cdots +f(x_{n})\geq 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

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

${\displaystyle c_{i+1}:={\frac {f(x_{i+1})-f(y_{i+1})}{x_{i+1}-y_{i+1}}}\leq {\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

${\displaystyle A_{i}=x_{1}+\cdots +x_{i},\qquad 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,

${\displaystyle {\begin{aligned}\sum _{i=1}^{n}{\bigl (}f(x_{i})-f(y_{i}){\bigr )}&=\sum _{i=1}^{n}c_{i}(x_{i}-y_{i})\\&=\sum _{i=1}^{n}c_{i}{\bigl (}\underbrace {A_{i}-A_{i-1}} _{=\,x_{i}}{}-(\underbrace {B_{i}-B_{i-1}} _{=\,y_{i}}){\bigr )}\\&=\sum _{i=1}^{n}c_{i}(A_{i}-B_{i})-\sum _{i=1}^{n}c_{i}(A_{i-1}-B_{i-1})\\&=c_{n}(\underbrace {A_{n}-B_{n}} _{=\,0})+\sum _{i=1}^{n-1}(\underbrace {c_{i}-c_{i+1}} _{\geq \,0})(\underbrace {A_{i}-B_{i}} _{\geq \,0})-c_{1}(\underbrace {A_{0}-B_{0}} _{=\,0})\\&\geq 0,\end{aligned}}}$

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

References

External links

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