Karamata's inequality

Let {{math|I}} be an interval of the real line and let {{math|f}} denote a real-valued, convex function defined on {{math|I}}. If {{math|x₁, …, x_n}} and {{math|y₁, …, y_n}} are numbers in {{math|I}} such that {{math|(x₁, …, x_n)}} majorizes {{math|(y₁, …, y_n)}}, then

{{NumBlk|:|$f(x\_1)+\backslash cdots+f(x\_n)\; \backslash ge\; f(y\_1)+\backslash cdots+f(y\_n).$|{{EquationRef|1}}}}

Here majorization means that {{math|x₁, …, x_n}} and {{math|y₁, …, y_n}} satisfies

{{NumBlk|:|$x\_1\backslash ge\; x\_2\backslash ge\backslash cdots\backslash ge\; x\_n$    and    $y\_1\backslash ge\; y\_2\backslash ge\backslash cdots\backslash ge\; y\_n,$|{{EquationRef|2}}}}

and we have the inequalities

{{NumBlk|:|$x\_1+\backslash cdots+x\_i\backslash ge\; y\_1+\backslash cdots+y\_i$     for all {{math|i ∈ {1, …, n − 1}}}.|{{EquationRef|3}}}}

and the equality

{{NumBlk|:|$x\_1+\backslash cdots+x\_n=y\_1+\backslash cdots+y\_n$|{{EquationRef|4}}}}

If {{math|f}}  is a strictly convex function, then the inequality ({{EquationNote|1}}) holds with equality if and only if we have {{math|1=x_i = y_i}} for all {{math|i ∈ {1, …, n}}}.

$x\; \backslash preceq\_w\; y$ if and only if $\backslash sum\; g\backslash left(x\_i\backslash right)\; \backslash leq\; \backslash sum\; g\backslash left(y\_i\backslash right)$ for any continuous increasing convex function $g:\; \backslash R\; \backslash to\; \backslash R$.{{Citation |last=Marshall |first=Albert W. |title=Introduction |date=2010 |work=Inequalities: Theory of Majorization and Its Applications |pages=3–28 |url=http://link.springer.com/10.1007/978-0-387-68276-1_1 |access-date=2025-01-29 |place=New York, NY |publisher=Springer New York |doi=10.1007/978-0-387-68276-1_1 |isbn=978-0-387-40087-7 |last2=Olkin |first2=Ingram |last3=Arnold |first3=Barry C.|url-access=subscription }}

• If the convex function {{math|f}}  is non-decreasing, then the proof of ({{EquationNote|1}}) below and the discussion of equality in case of strict convexity shows that the equality ({{EquationNote|4}}) can be relaxed to

  {{NumBlk|:|$x\_1+\backslash cdots+x\_n\backslash ge\; y\_1+\backslash cdots+y\_n.$|{{EquationRef|5}}}}

• The inequality ({{EquationNote|1}}) is reversed if {{math|f}}  is concave, since in this case the function {{math|−f}}  is convex.

The finite form of Jensen's inequality is a special case of this result. Consider the real numbers {{math|x₁, …, x_n ∈ I}} and let

:$a\; :=\; \backslash frac\{x\_1+x\_2+\backslash cdots+x\_n\}\{n\}$

denote their arithmetic mean. Then {{math|(x₁, …, x_n)}} majorizes the {{math|n}}-tuple {{math|(a, a, …, a)}}, since the arithmetic mean of the {{math|i}} largest numbers of {{math|(x₁, …, x_n)}} is at least as large as the arithmetic mean {{math|a}} of all the {{math|n}} numbers, for every {{math|i ∈ {1, …, n − 1}}}. By Karamata's inequality ({{EquationNote|1}}) for the convex function {{math|f}},

:$f(x\_1)+f(x\_2)+\; \backslash cdots\; +f(x\_n)\; \backslash ge\; f(a)+f(a)+\backslash cdots+f(a)\; =\; nf(a).$

Dividing by {{math|n}} gives Jensen's inequality. The sign is reversed if {{math|f}}  is concave.

We may assume that the numbers are in decreasing order as specified in ({{EquationNote|2}}).

If {{math|1=x_i = y_i}} for all {{math|i ∈ {1, …, n}}}, then the inequality ({{EquationNote|1}}) holds with equality, hence we may assume in the following that {{math|x_i ≠ y_i}} for at least one {{math|i}}.

If {{math|1=x_i = y_i}} for an {{math|i ∈ {1, …, n}}}, then the inequality ({{EquationNote|1}}) and the majorization properties ({{EquationNote|3}}) and ({{EquationNote|4}}) are not affected if we remove {{math|x_i}} and {{math|y_i}}. Hence we may assume that {{math|x_i ≠ y_i}} for all {{math|i ∈ {1, …, n}}}.

It is a property of convex functions that for two numbers {{math|x ≠ y}} in the interval {{math|I}} the slope

:$\backslash frac\{f(x)-f(y)\}\{x-y\}$

of the secant line through the points {{math|(x, f (x))}} and {{math|(y, f (y))}} of the graph of {{math|f}}  is a monotonically non-decreasing function in {{math|x}} for {{math|y}} fixed (and vice versa). This implies that

{{NumBlk|:|$c\_\{i+1\}:=\backslash frac\{f(x\_\{i+1\})-f(y\_\{i+1\})\}\{x\_\{i+1\}-y\_\{i+1\}\}\backslash le\backslash frac\{f(x\_i)-f(y\_i)\}\{x\_i-y\_i\}=:c\_i$|{{EquationRef|6}}}}

for all {{math|i ∈ {1, …, n − 1}}}. Define {{math|1=A₀ = B₀ = 0}} and

:$A\_i=x\_1+\backslash cdots+x\_i,\backslash qquad\; B\_i=y\_1+\backslash cdots+y\_i$

for all {{math|i ∈ {1, …, n}}}. By the majorization property ({{EquationNote|3}}), {{math|A_i ≥ B_i}} for all {{math|i ∈ {1, …, n − 1}}} and by ({{EquationNote|4}}), {{math|1=A_n = B_n}}. Hence,

{{NumBlk|:|$\backslash begin\{align\}$

\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}}_{\ge\,0})(\underbrace{A_i - B_i}_{\ge\,0}) - c_1(\underbrace{A_0-B_0}_{=\,0})\\

&\ge0,

\end{align}|{{EquationRef|7}}}}

which proves Karamata's inequality ({{EquationNote|1}}).

To discuss the case of equality in ({{EquationNote|1}}), note that {{math|x₁ > y₁}} by ({{EquationNote|3}}) and our assumption {{math|x_i ≠ y_i}} for all {{math|i ∈ {1, …, n − 1}}}. Let {{math|i}} be the smallest index such that {{math|(x_i, y_i) ≠ (x_i+1, y_i+1)}}, which exists due to ({{EquationNote|4}}). Then {{math|A_i > B_i}}. If {{math|f}}  is strictly convex, then there is strict inequality in ({{EquationNote|6}}), meaning that {{math|c_i+1 < c_i}}. Hence there is a strictly positive term in the sum on the right hand side of ({{EquationNote|7}}) and equality in ({{EquationNote|1}}) cannot hold.

If the convex function {{math|f}}  is non-decreasing, then {{math|c_n ≥ 0}}. The relaxed condition ({{EquationNote|5}}) means that {{math|A_n ≥ B_n}}, which is enough to conclude that {{math|c_n(A_n−B_n) ≥ 0}} in the last step of ({{EquationNote|7}}).

If the function {{math|f}}  is strictly convex and non-decreasing, then {{math|c_n > 0}}. It only remains to discuss the case {{math|A_n > B_n}}. However, then there is a strictly positive term on the right hand side of ({{EquationNote|7}}) and equality in ({{EquationNote|1}}) cannot hold.

{{reflist}}

An explanation of Karamata's inequality and majorization theory can be found [https://artofproblemsolving.com/community/c6h14975 here].

Category:Inequalities (mathematics)

Category:Convex analysis

Category:Articles containing proofs