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

## 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*_{1}, . . . , *x _{n}* and

*y*

_{1}, . . . ,

*y*are numbers in

_{n}*I*such that (

*x*

_{1}, . . . ,

*x*) majorizes (

_{n}*y*

_{1}, . . . ,

*y*), then

_{n}Here majorization means that

and, after relabeling the numbers *x*_{1}, . . . , *x _{n}* and

*y*

_{1}, . . . ,

*y*, respectively, in decreasing order, i.e.,

_{n}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 *x _{i}* =

*y*for all

_{i}*i*∈ {1, . . . ,

*n*}.

## Remarks

- If the convex function
*f*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

- The inequality (Template:EquationNote) 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*_{1}, . . . , *x _{n}* ∈

*I*and let

denote their arithmetic mean. Then (*x*_{1}, . . . , *x _{n}*) majorizes the

*n*-tuple (

*a*,

*a*, . . . ,

*a*), since the arithmetic mean of the

*i*largest numbers of (

*x*

_{1}, . . . ,

*x*) is at least as large as the arithmetic mean

_{n}*a*of all the

*n*numbers, for every

*i*∈ {1, . . . ,

*n*− 1}. By Karamata's inequality (Template:EquationNote) for the convex function

*f*,

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 *x _{i}* =

*y*for all

_{i}*i*∈ {1, . . . ,

*n*}, then the inequality (Template:EquationNote) holds with equality, hence we may assume in the following that

*x*≠

_{i}*y*for at least one

_{i}*i*.

If *x _{i}* =

*y*for an

_{i}*i*∈ {1, . . . ,

*n*− 1}, then the inequality (Template:EquationNote) and the majorization properties (Template:EquationNote), (Template:EquationNote) are not affected if we remove

*x*and

_{i}*y*. Hence we may assume that

_{i}*x*≠

_{i}*y*for all

_{i}*i*∈ {1, . . . ,

*n*− 1}.

It is a property of convex functions that for two numbers *x* ≠ *y* 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

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

for all *i* ∈ {1, . . . , *n*}. By the majorization property (Template:EquationNote), *A _{i}* ≥

*B*for all

_{i}*i*∈ {1, . . . ,

*n*− 1} and by (Template:EquationNote),

*A*=

_{n}*B*. Hence,

_{n}which proves Karamata's inequality (Template:EquationNote).

To discuss the case of equality in (Template:EquationNote), note that *x*_{1} > *y*_{1} by (Template:EquationNote) and our assumption *x _{i}* ≠

*y*for all

_{i}*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 (Template:EquationNote). Then

*A*>

_{i}*B*. If

_{i}*f*is strictly convex, then there is strict inequality in (Template:EquationNote), meaning that

*c*

_{i+1}<

*c*. 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.

_{i}If the convex function *f* is non-decreasing, then *c _{n}* ≥ 0. The relaxed condition (Template:EquationNote) means that

*A*≥

_{n}*B*, which is enough to conclude that

_{n}*c*(

_{n}*A*−

_{n}*B*) ≥ 0 in the last step of (Template:EquationNote).

_{n}If the function *f* is strictly convex and non-decreasing, then *c _{n}* > 0. It only remains to discuss the case

*A*>

_{n}*B*. However, then there is a strictly positive term on the right hand side of (Template:EquationNote) and equality in (Template:EquationNote) cannot hold.

_{n}## References

## External links

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