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

*y*

_{1}, . . . ,

*y*are numbers in

_{n}*I*such that (

*x*

_{1}, . . . ,

*x*) majorizes (

_{n}*y*

_{1}, . . . ,

*y*), then

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

Here majorization means that *x*_{1}, . . . , *x _{n}* and

*y*

_{1}, . . . ,

*y*satisfies

_{n}\( {\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*for all

_{i}*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_{1}, . . . , x_{n} ∈ I and let

\( {\displaystyle 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*) 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 (

**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*for all

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

*n*}, then the inequality (

**1**) 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 (

**1**) and the majorization properties (

**3**) and (

**4**) 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

\( {\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 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 (**3**), *A _{i}* ≥

*B*for all

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

*n*− 1} and by (

**4**),

*A*=

_{n}*B*. Hence,

_{n}\( {\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*_{1} > *y*_{1} by (**3**) 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 (

**4**). Then

*A*>

_{i}*B*. If

_{i}*f*is strictly convex, then there is strict inequality in (

**6**), meaning that

*c*

_{i+1}<

*c*. Hence there is a strictly positive term in the sum on the right hand side of (

_{i}**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*, which is enough to conclude that

_{n}*c*(

_{n}*A*−

_{n}*B*) ≥ 0 in the last step of (

_{n}**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*. However, then there is a strictly positive term on the right hand side of (

_{n}**7**) and equality in (

**1**) cannot hold.

References

Kadelburg, Zoran; Đukić, Dušan; Lukić, Milivoje; Matić, Ivan (2005), "Inequalities of Karamata, Schur and Muirhead, and some applications" (PDF), The Teaching of Mathematics, 8 (1): 31–45, ISSN 1451-4966

Karamata, Jovan (1932), "Sur une inégalité relative aux fonctions convexes" (PDF), Publ. Math. Univ. Belgrade (in French), 1: 145–148, Zbl 0005.20101

Undergraduate Texts in Mathematics

Graduate Studies in Mathematics

Hellenica World - Scientific Library

Retrieved from "http://en.wikipedia.org/"

All text is available under the terms of the GNU Free Documentation License