# Karamata's inequality

(diff) ← Older revision | Latest revision (diff) | Newer revision → (diff)

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.

## 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 x1, . . . , xn and y1, . . . , yn, respectively, in decreasing order, i.e.,

we have

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

## Example

The finite form of Jensen's inequality is a special case of this result. Consider the real numbers x1, . . . , xnI and let

${\displaystyle a:={\frac {x_{1}+x_{2}+\cdots +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 (Template:EquationNote) 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 (Template:EquationNote).

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

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

for all i ∈ {1, . . . , n − 1}. Define A0 = B0 = 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 (Template:EquationNote), AiBi for all i ∈ {1, . . . , n − 1} and by (Template:EquationNote), An = Bn. Hence,

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

To discuss the case of equality in (Template:EquationNote), note that x1 > y1 by (Template:EquationNote) 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 (Template:EquationNote). Then Ai > Bi. If f  is strictly convex, then there is strict inequality in (Template:EquationNote), meaning that ci+1 < ci. 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 f  is non-decreasing, then cn ≥ 0. The relaxed condition (Template:EquationNote) means that AnBn, which is enough to conclude that cn(AnBn) ≥ 0 in the last step of (Template:EquationNote).

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 (Template:EquationNote) and equality in (Template:EquationNote) cannot hold.

## References

1. {{#invoke:citation/CS1|citation |CitationClass=citation }}
2. {{#invoke:citation/CS1|citation |CitationClass=citation }}