Karamata's inequality

Template:Short description 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 Template:Math be an interval of the real line and let Template:Math denote a real-valued, convex function defined on Template:Math. If Template:Math and Template:Math are numbers in Template:Math such that Template:Math majorizes Template:Math, then

Here majorization means that Template:Math and Template:Math satisfies

and we have the inequalities

and the equality

If Template:Math  is a strictly convex function, then the inequality (Template:EquationNote) holds with equality if and only if we have Template:Math for all Template:Math.

Weak majorization case

$x{⪯}_{w}y$ iff $\sum g\left(x_i\right)\le \sum g\left(y_i\right)$ for any continuous increasing convex function $g:ℝ\to ℝ$.

Remarks

• If the convex function Template:Math  is non-decreasing, then the proof of (Template:EquationNote) below and the discussion of equality in case of strict convexity shows that the equality (Template:EquationNote) can be relaxed to Template:NumBlk
• The inequality (Template:EquationNote) is reversed if Template:Math  is concave, since in this case the function Template:Math  is convex.

Example

The finite form of Jensen's inequality is a special case of this result. Consider the real numbers Template:Math and let

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

denote their arithmetic mean. Then Template:Math majorizes the Template:Math-tuple Template:Math, since the arithmetic mean of the Template:Math largest numbers of Template:Math is at least as large as the arithmetic mean Template:Math of all the Template:Math numbers, for every Template:Math. By Karamata's inequality (Template:EquationNote) for the convex function Template:Math,

$f(x_1)+f(x_2)+\cdots +f(x_n)\ge f(a)+f(a)+\cdots +f(a)=nf(a).$

Dividing by Template:Math gives Jensen's inequality. The sign is reversed if Template:Math  is concave.

Proof of the inequality

We may assume that the numbers are in decreasing order as specified in (Template:EquationNote).

If Template:Math for all Template:Math, then the inequality (Template:EquationNote) holds with equality, hence we may assume in the following that Template:Math for at least one Template:Math.

If Template:Math for an Template:Math, then the inequality (Template:EquationNote) and the majorization properties (Template:EquationNote) and (Template:EquationNote) are not affected if we remove Template:Math and Template:Math. Hence we may assume that Template:Math for all Template:Math.

It is a property of convex functions that for two numbers Template:Math in the interval Template:Math the slope

$\frac{f(x)-f(y)}{x-y}$

of the secant line through the points Template:Math and Template:Math of the graph of Template:Math  is a monotonically non-decreasing function in Template:Math for Template:Math fixed (and vice versa). This implies that

for all Template:Math. Define Template:Math and

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

for all Template:Math. By the majorization property (Template:EquationNote), Template:Math for all Template:Math and by (Template:EquationNote), Template:Math. Hence,

which proves Karamata's inequality (Template:EquationNote).

To discuss the case of equality in (Template:EquationNote), note that Template:Math by (Template:EquationNote) and our assumption Template:Math for all Template:Math. Let Template:Math be the smallest index such that Template:Math, which exists due to (Template:EquationNote). Then Template:Math. If Template:Math  is strictly convex, then there is strict inequality in (Template:EquationNote), meaning that Template:Math. Hence there is a strictly positive term in the sum on the right hand side of (Template:EquationNote) and equality in (Template:EquationNote) cannot hold.

If the convex function Template:Math  is non-decreasing, then Template:Math. The relaxed condition (Template:EquationNote) means that Template:Math, which is enough to conclude that Template:Math in the last step of (Template:EquationNote).

If the function Template:Math  is strictly convex and non-decreasing, then Template:Math. It only remains to discuss the case Template:Math. However, then there is a strictly positive term on the right hand side of (Template:EquationNote) and equality in (Template:EquationNote) cannot hold.

External links

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