# Karamata's inequality

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$_1$, …, x$_n$ and y$_1$, …, y$_n$ are numbers in I such that (x$_1$, …, x$_n$) majorizes (y$_1$, …, y$_n$), then
Here majorization means that x$_1$, …, x$_n$ and y$_1$, …, y$_n$ satisfies
and we have the inequalities
and the equality
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}.

### Weak majorization case

$x\preceq _{w}y$ iff $\sum g\left(x_{i}\right)\leq \sum g\left(y_{i}\right)$ for any continuous increasing convex function $g:\mathbb {R} \to \mathbb {R}$.

## 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}\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$_1$, …, x$_n$ ∈ I and let
    $a:={\frac {x_{1}+x_{2}+\cdots +x_{n}}{n}}$
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$_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})\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
    ${\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 A$_0$ = B$_0$ = 0 and
    $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,
which proves Karamata's inequality (1).
To discuss the case of equality in (1), note that x$_1$ > y$_1$ 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.