MathLinks Forum LaTeX Help AoPS Classes Books Classroom MathLinks Contest Math Resources

The time now is Sat Nov 21, 2009 12:19 am
All times are UTC + 2		 View posts since last visit
View unanswered posts
The Karamata inequality
View previous topicView next topic
Home » Forum » Olympiad Section » Inequalities » Inequalities Theorems and Formulas
 

Moderators: High School Olympiad Moderators, Arne, blahblahblah, Cezar Lupu, darij grinberg, harazi, Megus, N.T.TUAN, orl, pbornsztein, pvthuan 
41 Posts • Page 1 of 3 • 1, 2, 3 Next
Author Message
darij grinberg
Birch & Swinnerton Dyer
Birch & Swinnerton Dyer


Offline
Joined: 10 Feb 2004
Posts: 5763
Location: Karlsruhe / Munich
To rate posts you must be logged in
#1
The Karamata inequality
Majorization Theory
Since I was asked about it I'm posting it.

We begin with a definition:

1. Let x_1, x_2, ..., x_n, y_1, y_2, ..., y_n be arbitrary real numbers satisfying x_1 \geq x_2 \geq ... \geq x_n and y_1 \geq y_2 \geq ... \geq y_n. Now, if we have all the following conditions fulfilled:

x_1 \geq y_1;
x_1 + x_2 \geq y_1 + y_2;
x_1 + x_2 + x_3 \geq y_1 + y_2 + y_3;
...
generally x_1 + x_2 + ... + x_k \geq y_1 + y_2 + ... + y_k for any natural k with 1 \leq k \leq n - 1;
and x_1 + x_2 + ... + x_n = y_1 + y_2 + ... + y_n

(mind the equality sign in the last condition; it is not a \geq sign!), then we say that the number array \left(x_1;\;x_2;\;...;\;x_n\right) majorizes the number array \left(y_1;\;y_2;\;...;\;y_n\right). We write this in the form \left( x_1;\;x_2;\;...;\;x_n\right) \succ \left( y_1;\;y_2;\;...;\;y_n\right).

Now, if instead of

x_1 \geq y_1;
x_1 + x_2 \geq y_1 + y_2;
x_1 + x_2 + x_3 \geq y_1 + y_2 + y_3;
...
generally x_1 + x_2 + ... + x_k \geq y_1 + y_2 + ... + y_k for any natural k with 1 \leq k \leq n - 1;
and x_1 + x_2 + ... + x_n = y_1 + y_2 + ... + y_n,

we have the conditions

x_1 \leq y_1;
x_1 + x_2 \leq y_1 + y_2;
x_1 + x_2 + x_3 \leq y_1 + y_2 + y_3;
...
generally x_1 + x_2 + ... + x_k \leq y_1 + y_2 + ... + y_k for any natural k with 1 \leq k \leq n - 1;
and x_1 + x_2 + ... + x_n = y_1 + y_2 + ... + y_n

fulfilled (i. e., the same conditions with all \geq's replaced by \leq's), then we say that the number array \left(x_1;\;x_2;\;...;\;x_n\right) minorizes the number array \left(y_1;\;y_2;\;...;\;y_n\right). We write this in the form \left( x_1;\;x_2;\;...;\;x_n\right) \prec \left( y_1;\;y_2;\;...;\;y_n\right). Of course, this is equivalent to \left( y_1;\;y_2;\;...;\;y_n\right) \succ \left( x_1;\;x_2;\;...;\;x_n\right).

2. Thus we have defined the notions "majorizes" and "minorizes" only for non-increasing arrays (i. e. for arrays satisfying x_1 \geq x_2 \geq ... \geq x_n and y_1 \geq y_2 \geq ... \geq y_n). Now, assume that x_1, x_2, ..., x_n, y_1, y_2, ..., y_n are just arbitrary real numbers, without any conditions. Then, let \left(X_1;\;X_2;\;...;\;X_n\right) be the non-increasing permutation of the array \left(x_1;\;x_2;\;...;\;x_n\right), i. e. the permutation of the array \left(x_1;\;x_2;\;...;\;x_n\right) that satisfies X_1 \geq X_2 \geq ... \geq X_n. Similarly, let \left(Y_1;\;Y_2;\;...;\;Y_n\right) be the non-increasing permutation of the array \left(y_1;\;y_2;\;...;\;y_n\right), i. e. the permutation of the array \left(y_1;\;y_2;\;...;\;y_n\right) that satisfies Y_1 \geq Y_2 \geq ... \geq Y_n. The number arrays \left(X_1;\;X_2;\;...;\;X_n\right) and \left(Y_1;\;Y_2;\;...;\;Y_n\right) are both non-increasing, and hence we have defined majorization for such arrays.

Then, we say that the number array \left(x_1;\;x_2;\;...;\;x_n\right) majorizes the number array \left(y_1;\;y_2;\;...;\;y_n\right) if and only if the number array \left(X_1;\;X_2;\;...;\;X_n\right) majorizes the number array \left(Y_1;\;Y_2;\;...;\;Y_n\right). In this case, we write \left( x_1;\;x_2;\;...;\;x_n\right) \succ \left( y_1;\;y_2;\;...;\;y_n\right).

Similarly, we say that the number array \left(x_1;\;x_2;\;...;\;x_n\right) minorizes the number array \left(y_1;\;y_2;\;...;\;y_n\right) if and only if the number array \left(X_1;\;X_2;\;...;\;X_n\right) minorizes the number array \left(Y_1;\;Y_2;\;...;\;Y_n\right). In this case, we write \left( x_1;\;x_2;\;...;\;x_n\right) \prec \left( y_1;\;y_2;\;...;\;y_n\right). Again this is equivalent to \left( y_1;\;y_2;\;...;\;y_n\right) \succ \left( x_1;\;x_2;\;...;\;x_n\right).

3. So we have defined the terms "majorize" and "minorize" for any two number arrays. It should be noted that majorization is a partial order on the set of number arrays, not a total order - i. e., not for every pair of two number arrays \left(x_1;\;x_2;\;...;\;x_n\right) and \left(y_1;\;y_2;\;...;\;y_n\right) one can say that either the first one majorizes the second one, or the second one majorizes the first one. It often happens that none of the arrays majorizes or minorizes the other one. But sometimes when you have some special arrays, you can prove that one of them majorizes the other one.

4. Now, the Karamata inequality, also called the Majorization Inequality or the Hardy-Littlewood inequality, states that if x_1, x_2, ..., x_n, y_1, y_2, ..., y_n are 2n reals from an interval I\subseteq\mathbb{R} such that the number array \left(x_1;\;x_2;\;...;\;x_n\right) majorizes the number array \left(y_1;\;y_2;\;...;\;y_n\right), and f: I\to\mathbb{R} is any convex function, then

f\left( x_1\right) + f\left( x_2\right) + ... + f\left( x_n\right) \geq f\left( y_1\right) + f\left( y_2\right) + ... + f\lef....

If f: I\to\mathbb{R} is a concave function instead, then we instead have

f\left( x_1\right) + f\left( x_2\right) + ... + f\left( x_n\right) \leq f\left( y_1\right) + f\left( y_2\right) + ... + f\lef....

If the number array \left(x_1;\;x_2;\;...;\;x_n\right) minorizes the number array \left(y_1;\;y_2;\;...;\;y_n\right) instead of majorizing it, then both inequalities are reversed.

5. The Jensen inequality for real numbers is a special case of the Karamata inequality. In fact, if m = \frac {x_1 + x_2 + ... + x_n}{n} is the arithmetic mean of the numbers x_1, x_2, ..., x_n, then it is easy to show that the number array \left(x_1;\;x_2;\;...;\;x_n\right) majorizes the number array \left(m;\;m;\;...;\;m\right). Hence, the Karamata inequality yields:

If f(x) is any convex function, then

f\left( x_1\right) + f\left( x_2\right) + ... + f\left( x_n\right) \geq n f\left( m\right),

i. e.

\frac {f\left( x_1\right) + f\left( x_2\right) + ... + f\left( x_n\right)}{n} \geq f\left( m\right).

If f(x) is a concave function instead, then we instead have

f\left( x_1\right) + f\left( x_2\right) + ... + f\left( x_n\right) \leq n f\left( m\right),

i. e.

\frac {f\left( x_1\right) + f\left( x_2\right) + ... + f\left( x_n\right)}{n} \leq f\left( m\right).

Of course, this is exactly the Jensen inequality for n reals.

6. The definition of majorizing and minorizing number arrays given above is somewhat unsatisfying from an intuitive point of view, since it does not help one to imagine how an array majorizing another array looks like. Unfortunately, this is partly inherent to the notion of majorization, which indeed is quite unintuitive. For a - rather facile - visualization of the notion, you can imagine that a number array \left(x_1;\;x_2;\;...;\;x_n\right) majorizes a number array \left(y_1;\;y_2;\;...;\;y_n\right) if the two arrays have the same sum of numbers, but the numbers of the first array are set wider apart than those of the second array, while those of the second array lie closer together. From this intuitive viewpoint, it is clear why the number array \left(x_1;\;x_2;\;...;\;x_n\right) majorizes the number array \left(m;\;m;\;...;\;m\right), where m = \frac {x_1 + x_2 + ... + x_n}{n} is the arithmetic mean of the numbers x_1, x_2, ..., x_n: In fact, the two number arrays have the same sum of elements, but the elements of the second number array lie nearer to each other (they are all equal). Alas, this viewpoint does not help one to really understand what majorization is about.

Well, I know there is more to say. For instance, the Karamata inequality has a kind of converse, but I am not sure how it is formulated, so I leave this to the other MathLinkers more used to inequalities.

Darij
_________________
Now the die is cast, the first step taken, a glimmer of hope lights up our lives
Visions of the past, dreams forsaken forming right under our eyes
We are alive...

PostPosted: Thu Aug 05, 2004 5:51 pm
Last edited by darij grinberg on Sun Mar 29, 2009 2:10 am; edited 5 times in total
ADMann94
New Member
New Member

Offline
Joined: 20 Jul 2004
Posts: 15
United States
To rate posts you must be logged in
#2
Where can I find a proof of this?

Alex
_________________
Ross 2003

PostPosted: Sat Aug 28, 2004 11:48 pm
fuzzylogic
Yang-Mills Theory
Yang-Mills Theory

Offline
Joined: 24 Mar 2004
Posts: 719
To rate posts you must be logged in
#3
ADMann94 wrote:
Where can I find a proof of this?

Alex


Probably in this book.

PostPosted: Sun Aug 29, 2004 1:33 am
ADMann94
New Member
New Member

Offline
Joined: 20 Jul 2004
Posts: 15
United States
To rate posts you must be logged in
#4
Thanks!

Alex
_________________
Ross 2003

PostPosted: Tue Sep 07, 2004 12:53 am
Megus
Navier-Stokes Equations
Navier-Stokes Equations

Offline
Joined: 23 Aug 2004
Posts: 1211
Location: Paris
PolandFrance
To rate posts you must be logged in
#5
I heard that Karamata inequality is indeed Littlewood-Hardy inequality so which name is correct or maybe both [the question is: which name shall I pull out during the contest ]?

PostPosted: Tue Oct 05, 2004 8:40 pm
darij grinberg
Birch & Swinnerton Dyer
Birch & Swinnerton Dyer


Offline
Joined: 10 Feb 2004
Posts: 5763
Location: Karlsruhe / Munich
To rate posts you must be logged in
#6
Best refer to it as "Karamata Majorization Inequality". As for Littlewood and Hardy, it's true that they have discovered it independently from Karamata, but I personally have never seen anybody naming it for Littlewood and Hardy.

Darij
_________________
Now the die is cast, the first step taken, a glimmer of hope lights up our lives
Visions of the past, dreams forsaken forming right under our eyes
We are alive...

PostPosted: Tue Oct 05, 2004 8:48 pm
Megus
Navier-Stokes Equations
Navier-Stokes Equations

Offline
Joined: 23 Aug 2004
Posts: 1211
Location: Paris
PolandFrance
To rate posts you must be logged in
#7
Ok - I asked beacuse of guys who laughed at me when had heard Karamata Mr. Green

PostPosted: Wed Oct 06, 2004 4:36 pm
flip2004
Yang-Mills Theory
Yang-Mills Theory

Offline
Joined: 19 Jul 2004
Posts: 917
Location: Sibiu
Romania
To rate posts you must be logged in
#8
A=double stochastic matrix and y^T=Ax^T , then y =<x ??
Let {\mathbf x}=(x_1,x_2,...,x_n) , {\mathbf y}=(y_1,y_2,...,y_n)
and {\mathbf A}=||a_{i,j}|| a n\times n matrix having properties:
1) all a_{i,j} \ge 0 ,
2) \sum\limits_{i=1}^na_{i,j}= \sum\limits_{j=1}^{n}a_{i,j}=1 for i,j=1,2,...,n.

If {\mathbf x} is given in {\mathbf R}^n and {\mathbf y}^T=A{\mathbf x}^T ( where {\mathbf x}^T denotes the transpose of {\mathbf x}) , what we can say about {\mathbf y} ?

PostPosted: Fri Oct 15, 2004 2:14 pm
darij grinberg
Birch & Swinnerton Dyer
Birch & Swinnerton Dyer


Offline
Joined: 10 Feb 2004
Posts: 5763
Location: Karlsruhe / Munich
To rate posts you must be logged in
#9
Re: A=double stochastic matrix and y^T=Ax^T , then y =<x
Well, we can say that \left\{ \mathbf{x}\right\} \succ \left\{ \mathbf{y}\right\}. And conversely, if we have two vectors \left\{ \mathbf{x}\right\} and \left\{ \mathbf{y}\right\} such that \left\{ \mathbf{x}\right\} \succ \left\{ \mathbf{y}\right\}, then we can find a matrix \mathbf{A} with the properties 1) and 2) such that {\mathbf y}^T=\mathbf{A}{\mathbf x}^T. This is a result found by Karamata.

Darij
_________________
Now the die is cast, the first step taken, a glimmer of hope lights up our lives
Visions of the past, dreams forsaken forming right under our eyes
We are alive...

PostPosted: Fri Oct 15, 2004 2:32 pm
Last edited by darij grinberg on Sun Oct 17, 2004 8:42 pm; edited 1 time in total
Myth
Birch & Swinnerton Dyer
Birch & Swinnerton Dyer


Offline
Joined: 03 Sep 2003
Posts: 4485
Location: Chelyabinsk, Russia
Russian Federation
To rate posts you must be logged in
#10
Actually, true Jensen inequality is
a_1f(x_1)+a_2f(x_2)+\dots+a_nf(x_n)\geq f(a_1x_1+\dots+a_nx_n),
where f is convex function, a_i\in[0,1] and a_1+\dots+a_n=1.
a_i=\frac{1}{n} is a particular case only.
_________________
Myth is out of here

PostPosted: Fri Oct 15, 2004 2:44 pm
flip2004
Yang-Mills Theory
Yang-Mills Theory

Offline
Joined: 19 Jul 2004
Posts: 917
Location: Sibiu
Romania
To rate posts you must be logged in
#11
Some references
Hi all,
here is a very interesting paper related to discussed subject:

[*] A. OSTROWSKI , Sur quelques applications des fonctions convexes et concaves au sens de I. Schur, J.Math.Pures.Appl., (9) 31 (1952) 253-292.

Other possible references :

[1] G.H.Hardy , J.E.Littlewood, G.P\'olya , Some simple inequalities satisfied by convex functions, Messenger Math., 58 (1928/29) 145-152.
[2] J.Karamata , Sur une in\'egalit\'e relative aux fonctions convexes, Publ.Math.Univ. Belgrade 1 (1932) 145-158.
[3] T.Popoviciu , Notes sur les fonctions convexes d'ordre sup\'erieur ,III,Mathematica (Cluj) 16 (1940) 74-86.
[4] T.Popoviciu , Notes sur les fonctions convexes d'ordre sup\'erieur ,IV,Disquisitiones Mathematicae 1(1940) 163-171.
[5] T.Popoviciu , Les fonctions convexes, Actualit\'esci.Ind. No.992,Paris,1945.

PostPosted: Wed Oct 20, 2004 10:02 am
Xixas
Riemann Hypothesis
Riemann Hypothesis


Offline
Joined: 02 Oct 2004
Posts: 298
Location: Bremen
LithuaniaGermany
To rate posts you must be logged in
#12
I have a very simple question, which does not let me understand many things. So, can anyone explain me, what functions are called convex and what functions are called concave?
_________________
Kęstutis Česnavičius

PostPosted: Sat Nov 06, 2004 6:31 pm
Myth
Birch & Swinnerton Dyer
Birch & Swinnerton Dyer


Offline
Joined: 03 Sep 2003
Posts: 4485
Location: Chelyabinsk, Russia
Russian Federation
To rate posts you must be logged in
#13
Let f:[a,b]\to \mathbb{R}. Then f is called convex function iff
k\cdot f(x)+(1-k)\cdot f(y)\geq f(kx+(1-k)y)\quad \forall x,y\in [a,b],\ \forall k\in[0,1].

If function f is differentiable then f is convex iff f''(x)\geq 0 for all x\in[a,b].
_________________
Myth is out of here

PostPosted: Sat Nov 06, 2004 6:36 pm
Xixas
Riemann Hypothesis
Riemann Hypothesis


Offline
Joined: 02 Oct 2004
Posts: 298
Location: Bremen
LithuaniaGermany
To rate posts you must be logged in
#14
Another question: which functions are differentable? Can you give an example of non-differentable function?
_________________
Kęstutis Česnavičius

PostPosted: Sat Nov 06, 2004 6:52 pm
Myth
Birch & Swinnerton Dyer
Birch & Swinnerton Dyer


Offline
Joined: 03 Sep 2003
Posts: 4485
Location: Chelyabinsk, Russia
Russian Federation
To rate posts you must be logged in
#15
Take f(x)=|x|. It is convex non-differentiable function.
To know what is differentiable functions you need any analysis book.
_________________
Myth is out of here

PostPosted: Sat Nov 06, 2004 7:09 pm
perfect_radio
Birch & Swinnerton Dyer
Birch & Swinnerton Dyer


Offline
Joined: 05 Feb 2005
Posts: 2614
Location: Bucharest
Romania
To rate posts you must be logged in
#16
darij wrote:
Well, I know there is more to say. For instance, the Karamata inequality has a kind of converse, but I am not sure how it is formulated, so I leave this to the other MathLinkers more used to inequalities.


anyone know what is this converse?
_________________
"Germany has offered to send troops to the Lebanon border. I bet Israel's breathing a sigh of relief there. Nothing makes Jewish people feel safer and more secure than the German Army marching on their border."

PostPosted: Sun Jul 03, 2005 9:46 pm
Last edited by perfect_radio on Sun Apr 23, 2006 7:11 pm; edited 1 time in total
Bojan Basic
Poincare Conjecture
Poincare Conjecture

Offline
Joined: 08 Mar 2005
Posts: 248
Location: Novi Sad
Serbia
To rate posts you must be logged in
#17
I think it is the following (although I see absolutely no use of it):

If \displaystyle\sum f(x_i)\geqslant\sum f(y_i) for every convex function f then (x)\succ(y).

Could somebody post a counter example or (even better) prove this?

PostPosted: Mon Jul 04, 2005 12:14 am
fleeting_guest
Yang-Mills Theory
Yang-Mills Theory

Offline
Joined: 15 Dec 2004
Posts: 900
To rate posts you must be logged in
#18
The converse is proved by considering the inequality for:
constant functions (conclusion: vectors x and y have equal number of components),
linear functions (conclusion: \Sigma x = \Sigma y), and
functions of the form \max(0,x-a) (conclusion: the majorization conditions).

Any convex f is (on the given finite set of points) equal to a positive linear combination of these 3 types of functions.

PostPosted: Mon Jul 04, 2005 12:41 am
fleeting_guest
Yang-Mills Theory
Yang-Mills Theory

Offline
Joined: 15 Dec 2004
Posts: 900
To rate posts you must be logged in
#19
darij grinberg wrote:
Best refer to it as "Karamata Majorization Inequality". As for Littlewood and Hardy, it's true that they have discovered it independently from Karamata, but I personally have never seen anybody naming it for Littlewood and Hardy.


Karamata published later than Hardy,Littlewood and Polya, and in any case majorization was independently discovered many times before and after all these publications. There is a history in Marshall and Olkin's book on majorization. In the Anglo-Saxon countries it is called "majorization inequality" or "Hardy-Littlewood-Polya" majorization inequality".

PostPosted: Mon Jul 04, 2005 12:47 am
darij grinberg
Birch & Swinnerton Dyer
Birch & Swinnerton Dyer


Offline
Joined: 10 Feb 2004
Posts: 5763
Location: Karlsruhe / Munich
To rate posts you must be logged in
#20
Bojan Basic wrote:
I think it is the following (although I see absolutely no use of it):

If \displaystyle\sum f(x_i)\geqslant\sum f(y_i) for every convex function f then (x)\succ(y).


There is a stonger version of this: If \sum f\left(x_i\right)\geq\sum f\left(y_i\right) holds for every function f of the form f(x) = |x - u| (with u constant), then \left(x\right)\succ\left(y\right). This is actually Lemma 1 in http://www.mathlinks.ro/Forum/viewtopic.php?t=19097 post #11.

darij
_________________
Now the die is cast, the first step taken, a glimmer of hope lights up our lives
Visions of the past, dreams forsaken forming right under our eyes
We are alive...

PostPosted: Tue Jul 05, 2005 1:46 pm
Display posts from previous:   Sort by:   
41 Posts • Page 1 of 3 • 1, 2, 3 Next
Home » Forum » Olympiad Section » Inequalities » Inequalities Theorems and Formulas
 
View previous topicView next topic
Jump to:  


You cannot post new topics in this forum
You cannot reply to topics in this forum
You cannot edit your posts in this forum
You cannot delete your posts in this forum
You cannot vote in polls in this forum
You cannot attach files in this forum
You can download files in this forum
You cannot post calendar events in this forum

Created and Maintained by Valentin Vornicu - (c) AoPS Inc. 2004-2008