View source for NGC 7052

In [[mathematics]], '''Karamata's inequality''',<ref>{{Citation
  | last = Kadelburg
  | first = Zoran
  | last2 = Đukić
  | first2 = Dušan
  | last3 = Lukić
  | first3 = Milivoje
  | last4 = Matić
  | first4 = Ivan
  | title = Inequalities of Karamata, Schur and Muirhead, and some applications
  | journal = The Teaching of Mathematics
  | issn = 1451-4966
  | volume = 8
  | issue = 1
  | pages = 31–45
  | year = 2005
  | url = http://elib.mi.sanu.ac.rs/files/journals/tm/14/tm813.pdf
}}</ref> named after [[Jovan Karamata]],<ref>{{Citation
  | last = Karamata
  | first = Jovan
  | author-link = Jovan Karamata
  | title = Sur une inégalité rélative aux fonctions convexes
  | journal = Publ. Math. Univ. Belgrade
  | volume = 1
  | pages = 145–148
  | year = 1932
  | language = French
  | url = http://elib.mi.sanu.ac.rs/files/journals/publ/1/11.pdf
  | zbl = 0005.20101
}}</ref> 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 {{math|''I''}} be an [[interval (mathematics)|interval]] of the [[real line]] and let {{math|''f''}} denote a real-valued, [[convex function]] defined on {{math|''I''}}. If {{math|''x''<sub>1</sub>, . . . , ''x<sub>n</sub>''}} and {{math|''y''<sub>1</sub>, . . . , ''y<sub>n</sub>''}} are numbers in {{math|''I''}} such that {{math|(''x''<sub>1</sub>, . . . , ''x<sub>n</sub>'')}} [[majorization|majorizes]] {{math|(''y''<sub>1</sub>, . . . , ''y<sub>n</sub>'')}}, then

{{NumBlk|:|<math>f(x_1)+\cdots+f(x_n) \ge f(y_1)+\cdots+f(y_n).</math>|{{EquationRef|1}}}}

Here majorization means that

{{NumBlk|:|<math>x_1+\cdots+x_n=y_1+\cdots+y_n</math>|{{EquationRef|2}}}}

and, after relabeling the numbers {{math|''x''<sub>1</sub>, . . . , ''x<sub>n</sub>''}} and {{math|''y''<sub>1</sub>, . . . , ''y<sub>n</sub>''}}, respectively, in decreasing order, i.e.,

{{NumBlk|:|<math>x_1\ge x_2\ge\cdots\ge x_n</math>&nbsp;&nbsp;&nbsp;&nbsp;and&nbsp;&nbsp;&nbsp;&nbsp;<math>y_1\ge y_2\ge\cdots\ge y_n,</math>|{{EquationRef|3}}}}

we have 

{{NumBlk|:|<math>x_1+\cdots+x_i\ge y_1+\cdots+y_i</math>&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;for all {{math|''i'' ∈ {1, . . . , ''n'' − 1}}}.|{{EquationRef|4}}}}

If {{math|''f''}}&thinsp; is a [[strictly convex function]], then the inequality ({{EquationNote|1}}) holds with equality if and only if, after relabeling according to ({{EquationNote|3}}), we have {{math|''x<sub>i</sub>'' {{=}} ''y<sub>i</sub>''}} for all {{math|''i'' ∈ {1, . . . , ''n''}}}.

==Remarks==
* If the convex function {{math|''f''}}&thinsp; is [[non-decreasing function|non-decreasing]], then the proof of ({{EquationNote|1}}) below and the discussion of equality in case of strict convexity shows that the equality ({{EquationNote|2}}) can be relaxed to
{{NumBlk|::|<math>x_1+\cdots+x_n\ge y_1+\cdots+y_n.</math>|{{EquationRef|5}}}}

* The inequality ({{EquationNote|1}}) is reversed if {{math|''f''}}&thinsp; is [[concave function|concave]], since in this case the function {{math|−''f''}}&thinsp; is convex.

==Example==
The finite form of [[Jensen's inequality]] is a special case of this result. Consider the real numbers {{math|''x''<sub>1</sub>, . . . , ''x<sub>n</sub>'' ∈ ''I''}} and let 

:<math>a := \frac{x_1+x_2+\cdots+x_n}{n}</math>

denote their [[arithmetic mean]]. Then {{math|(''x''<sub>1</sub>, . . . , ''x<sub>n</sub>'')}} majorizes the {{math|''n''}}-tuple {{math|(''a'', ''a'', . . . , ''a'')}}, since the arithmetic mean of the {{math|''i''}} largest numbers of {{math|(''x''<sub>1</sub>, . . . , ''x<sub>n</sub>'')}} 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''}},

:<math>f(x_1)+f(x_2)+ \cdots +f(x_n) \ge f(a)+f(a)+\cdots+f(a) = nf(a).</math> 

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

==Proof of the inequality==
We may assume that the numbers are in decreasing order as specified in ({{EquationNote|3}}).

If {{math|''x<sub>i</sub>'' {{=}} ''y<sub>i</sub>''}} for all {{math|''i'' ∈ {1, . . . , ''n''}}}, then the inequality ({{EquationNote|1}}) holds with equality, hence we may assume in the following that {{math|''x<sub>i</sub>'' ≠ ''y<sub>i</sub>''}} for at least one {{math|''i''}}.

If {{math|''x<sub>i</sub>'' {{=}} ''y<sub>i</sub>''}} for an {{math|''i'' ∈ {1, . . . , ''n'' − 1}}}, then the inequality ({{EquationNote|1}}) and the majorization properties ({{EquationNote|2}}), ({{EquationNote|4}}) are not affected if we remove {{math|''x<sub>i</sub>''}} and {{math|''y<sub>i</sub>''}}. Hence we may assume that {{math|''x<sub>i</sub>'' ≠ ''y<sub>i</sub>''}} for all {{math|''i'' ∈ {1, . . . , ''n'' − 1}}}.

It is a [[convex function#Properties|property of convex functions]] that for two numbers {{math|''x'' ≠ ''y''}} in the interval {{math|''I''}} the [[slope]]

:<math>\frac{f(x)-f(y)}{x-y}</math>

of the [[secant line]] through the points {{math|(''x'', ''f''&thinsp;(''x''))}} and {{math|(''y'', ''f''&thinsp;(''y''))}} of the [[graph of a function|graph]] of {{math|''f''}}&thinsp; is a [[monotonically non-decreasing]] function in {{math|''x''}} for {{math|''y''}} fixed (and [[List of Latin phrases: V#vice_versa|vice versa]]). This implies that

{{NumBlk|:|<math>c_{i+1}:=\frac{f(x_{i+1})-f(y_{i+1})}{x_{i+1}-y_{i+1}}\le\frac{f(x_i)-f(y_i)}{x_i-y_i}=:c_i</math>|{{EquationRef|6}}}}

for all {{math|''i'' ∈ {1, . . . , ''n'' − 1}}}. Define {{math|''A''<sub>0</sub> {{=}} ''B''<sub>0</sub> {{=}} 0}} and 

:<math>A_i=x_1+\cdots+x_i,\qquad B_i=y_1+\cdots+y_i</math>

for all {{math|''i'' ∈ {1, . . . , ''n''}}}. By the majorization property ({{EquationNote|4}}), {{math|''A<sub>i</sub>'' ≥ ''B<sub>i</sub>''}} for all {{math|''i'' ∈ {1, . . . , ''n'' − 1}}} and by ({{EquationNote|2}}), {{math|''A<sub>n</sub>'' {{=}} ''B<sub>n</sub>''}}. Hence,

{{NumBlk|:|<math>\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}</math>|{{EquationRef|7}}}}

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

To discuss the case of equality in ({{EquationNote|1}}), note that {{math|''x''<sub>1</sub> > ''y''<sub>1</sub>}} by ({{EquationNote|4}}) and our assumption {{math|''x<sub>i</sub>'' ≠ ''y<sub>i</sub>''}} for all {{math|''i'' ∈ {1, . . . , ''n'' − 1}}}. Let {{math|''i''}} be the smallest index such that {{math|(''x<sub>i</sub>'', ''y<sub>i</sub>'') ≠ (''x''<sub>''i''+1</sub>, ''y''<sub>''i''+1</sub>)}}, which exists due to ({{EquationNote|2}}). Then {{math|''A<sub>i</sub>'' > ''B<sub>i</sub>''}}. If {{math|''f''}}&thinsp; is strictly convex, then there is strict inequality in ({{EquationNote|6}}), meaning that {{math|''c''<sub>''i''+1</sub> < ''c<sub>i</sub>''}}. 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''}}&thinsp; is non-decreasing, then {{math|''c<sub>n</sub>'' ≥ 0}}. The relaxed condition ({{EquationNote|5}}) means that {{math|''A<sub>n</sub>'' ≥ ''B<sub>n</sub>''}}, which is enough to conclude that {{math|''c<sub>n</sub>''(''A<sub>n</sub>''−''B<sub>n</sub>'') ≥ 0}} in the last step of ({{EquationNote|7}}).

If the function {{math|''f''}}&thinsp; is strictly convex and non-decreasing, then {{math|''c<sub>n</sub>'' > 0}}. It only remains to discuss the case {{math|''A<sub>n</sub>'' > ''B<sub>n</sub>''}}. However, then there is a strictly positive term on the right hand side of ({{EquationNote|7}}) and equality in ({{EquationNote|1}}) cannot hold.

==References==
{{reflist}}

==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].

[[Category:Inequalities]]
[[Category:Convex analysis]]
[[Category:Articles containing proofs]]