Karamata's inequality

In mathematics, Karamata's inequality, also known as the Majorization Inequality, states that if $f(x)$ is a convex function in $x$ and the sequence

:$x\_1,\; x\_2,\; ...,\; x\_n$

majorizes

:$y\_1,\; y\_2,\; ...,\; y\_n$

then

:$f(x\_1)+f(x\_2)+...+f(x\_n)\; ge\; f(y\_1)+f(y\_2)+...+f(y\_n)$.

The inequality is reversed if $f(x)$ is concave.

Jensen's inequality is in fact a special case of this result of Jovan Karamata. Consider a sequence

:$x\_1,\; x\_2,\; ...,\; x\_n$

and let

:$A\; =\; frac\{x\_1+x\_2+...+x\_n\}\{n\}.$

Then the sequence

:$x\_1,\; x\_2,\; ...,\; x\_n$

clearly majorizes the sequence

:$A,\; A,\; ...,\; A$ ($n$ times).

By Karamata's result,

:$f(x\_1)+f(x\_2)+...+f(x\_n)\; ge\; f(A)+f(A)+...+f(A)\; =\; nf(A),$

and dividing by $n$ produces the desired inequality. The sign is reversed if $f(x)$ is concave, as in Jensen's inequality.

External links

An explanation of Karamata's Inequality and majorization theory can be found [http://www.artofproblemsolving.com/Forum/viewtopic.php?highlight=majorization+karamata&t=14975 here] .