Muirhead's Inequality
   

   

 Math Help -> Procedures -> Inequality -> Muirhead's Inequality 

Muirhead's Inequality

Let s1 ≥ s2 ≥ ... ≥ sn ≥ 0 and
t1 ≥ t2 ≥ ... ≥ tn ≥ 0 and
the sum from i=1 to n of si equals the sum from i=1 to n of ti, and
for all k < n, the sum from i=1 to k of si is less than the sum from i=1 to k of ti.

Let s1 ≥ s2 ≥ ... ≥ sn ≥ 0, and
t1 ≥ t2 ≥ ... ≥ tn ≥ 0, and
\[\sum_{i=1}^{n}\] si  =  \[\sum_{i=1}^{n}\] ti  and for all k < n,  \[\sum_{i=1}^{k}\] si  ≥  \[\sum_{i=1}^{k}\] ti   
Then for all nonnegative numbers x1, x2, ..., xn,
\[\sum_{\sigma}\] x1sσ(1) x2sσ(2) ... xnsσ(n)  ≥  \[\sum_{\sigma}\] x1tσ(1) x2tσ(2) ... xntσ(n)  

where the sums run over all the permutations σ of {1, 2, 3, ..., n}

The "majorize" approach

Andre Rzym's Muirhead's Inequality introduces background terminology to simplify the expression of the inequality.

In a nutshell, a sequence, (a), of reals (a1, a2, ..., an) "majorizes" another sequence, (a'), of reals (a1', a2', ..., an') if

  1. All the elements of both sequences are nonnegative,
  2. They have the same number of elements,
  3. The two sequences have the same sum, and
  4. When arranged in descending order, no partial sum of (a) is less than the corresponding sum of (a')
    (That is, a1 ≥ a1', a1+a2 ≥ a1'+a2', etc.)

(a) majorizes (a') is written (a) \[\succ\] (a')

Examples

\[(0,3,0)\succ\(1,0,2)\]  because 3+0+0 = 2+1+0, 3 ≥ 2, and 3+0 ≥ 2+1
\[(4,0,0,0) \nsucc (2,0,2) \] since the number of elements is different
\[(5,0,-1) \nsucc (2,2,0) \] since terms cannot be negative
\[(2,1,1,1) \nsucc (1,1,1,1) \] since the sums of the two sequences are different
\[(4,1,1,1) \nsucc (3,3,1,0) \] since the partial sum 4+1 is smaller than 3+3

The "symmetric mean", [a] of nonnegative reals x1, x2, ..., xn is 1/n! times the sum over all the permutations of sequence (a) of the product of the x's raised to the exponents from a.  Note: these exponents need not be integers.

Muirhead's Inequality, then, is simply: If (a) \[\succ\] (a'), then [a] ≥ [a'], with equality iff (a) = (a') or all the xi are equal.

Proof of Muirhead's Inequality

Muirhead's Inequality is, in a sense, a sweeping generalization of the AM-GM inequality of n variables, with the symmetric mean [(1,0,...)] representing AM, and [(1/n,1/n,...)] representing GM.  Note that (1,0,...) majorizes every other sequence that sums to one, and (1/n,1/n,...) is majorized by every other sequence that sums to one.  So AM and GM are the "extreme means", if you'll pardon that expression, with means represented by every other finite one-sum sequence in between them.

So an approach to proving Muirhead's Inequality begins by with the weighted two-variable AM-GM inequality, and showing this is equivalent to Muirhead's Inequality using symmetric means of two variables.  The next part of the proof observes that for any pair of sequences of three or more elements where (a) \[\succ\] (a"), a sequence "in between" (a) and (a") can be found, which I will call (a'), such that

(a) and (a') share an element,
(a') and (a") share an element, and
(a) \[\succ\] (a') \[\succ\] (a")

This sets us up nicely for the induction step, which shows that whenever (a) \[\succ\] (a'), and the two sequences share an element, Muirhead's Inequality boils down to a similar inequality with one fewer elements.

Muirhead's Inequality Proof, Part 1: The Two Variable Case

Statement of the two variable case: Let (n,m) \[\succ\] (p,q).  Then for arbitrary positive reals x and y, xnym+xmyn ≥ xpyq+xqyp, with equality iff n=p or x=y.

Let w=(n-q)/(n-m).  Because n ≥ p ≥ q ≥ m, we see that w is between 0 and 1 (inclusive), and so is (1-w).  Then w and (1-w) are two weights, both nonnegative, whose sum is 1.

Note that wn+(1-w)m = wn-wm+m = w(n-m)+m = n-q+m = p, and
wm+(1-w)n = wm-wn+n = n-w(n-m) = n-(n-q) = q.

Let x and y be arbitrary positive reals.  By rewriting xnym+xmyn as the sum of two weighted averages (with the weights switched), and then by applying the weighted AM-GM inequality (wa+(1-w)b ≥ awb1-w) twice, we see:

xnym+xmyn = wxnym+(1-w)xmyn+(1-w)xnym+wxmyn 
  ≥ xwnywmx(1-w)my(1-w)n + x(1-w)ny(1-w)mxwmywn   
  = xwn+(1-w)mywm+(1-w)n + x(1-w)n+wmy(1-w)m+wn 
  = xpyq+xqyp.

Muirhead's Inequality Proof, Part 2: If (a) \[\succ\] (a"), then (a') exists "between" them, sharing an element of each

Let (a) and (a") be sequences of three or more elements, arranged in descending order, such that (a) \[\succ\] (a").  For convenience, we will define

(a) = (a1, a2, ..., an)
(a") = (a1", a2", ..., an")

I start by looking at the "gap", or difference, between elements of (a) and (a").  Because (a) \[\succ\] (a"), a1≥a1", and an≤an", so an i exists such that ai+1≤ai+1.  Pick the smallest such i, and call it k.  Between k and k+1 the gap changes sign (or one of the gaps is zero).  Now we have these inequalities:

ak≥ak", by our choice of k,
ak"≥ak+1", because (a") is arranged in descending order, and
ak+1"≥ak+1, by our choice of k.

Now I will define (a') by picking all of the elements from (a) except ak and ak+1, one of the elements of (a") -- either ak" or ak+1" -- and then adjusting ak+1' or ak' so that the sum comes out the same as that of (a) and (a").  I start by looking at the gaps between our two sequences.  I know ak≥ak" and ak+1≤ak+1" so I look for the smaller (in absolute value) of ak-ak" and ak+1-ak+1".  If the "k" gap is smaller, I set ak'=ak".  Otherwise, I set ak+1'=ak+1".  Here it is again, algebraically, just to make it official:

All of ai' = ai, except ak' and ak+1'.
If ak-ak" < ak+1"-ak+1 then ak'=ak", and ak+1'=ak+ak+1-ak" 
If ak-ak" ≥ ak+1"-ak+1 then ak+1'=ak+1", and ak'=ak+ak+1-ak+1" 

Note that ak' is set to the larger of ak" and ak+ak+1-ak+1", both of which are no larger than ak,
while ak+1' is set to the smaller of ak+1" and ak+ak+1-ak", both of which are at least as large as ak+1. 
(From this we see that ak ≥ak' ≥ak", which will be important later.  We also see that ak+1≤ak+1'≤ak+1", which will be equally important.)

With this definition, I showed that (a') exists sharing an element with (a) and sharing an element with (a").  To complete this part of the proof, I also need to show that (a') is arranged in descending order, that (a) \[\succ\] (a'), and that (a') \[\succ\] (a").

Descending Order

If k>1, then ak-1'=ak-1≥ak≥ak'≥ak"≥ak+1"≥ak+1'≥ak+1.  If k=1 then the first inequality isn't meaningful, but the rest still apply.

(a) \[\succ\] (a')

(a') is the same as (a) except for ak' and ak+1', which, though different from their counterparts in (a) have the property that ak'+ak+1'=ak+ak+1.  So the only partial sum of (a') that differs from that of (a) is the one whose last terms is ak'.  And since ak ≥ak', this partial sum of (a') is no larger than that of (a), so (a) \[\succ\] (a').

(a') \[\succ\] (a")

(a) \[\succ\] (a"), and the partial sums of (a') differ from those of (a) only once, to wit when the last term is ak'.  And since ak'≥ak", this partial sum of (a') is at least as large as that of (a"), so (a') \[\succ\] (a").

Muirhead's Inequality Proof, Part 3: The Induction Step

Statement of this step: If (a) and (a') have n≥3 elements, including one element in common (ak=ak' for some k) and (a) \[\succ\] (a'), then [a] ≥ [a'].

As this is the induction step, we assume Muirhead's Inequality is true for n-1 elements.  In particular, where (b)=(a)\{ak}, and (b')=(a')\{ak'}, we assume that [b] ≥ [b'].

Recall that [a] is the symmetric mean of n arbitrary positive reals x1,x2,...,xn.  In the following sum, we will assume [b] refers to the symmetric mean of all but one of those reals, that one being xi:

[a] = (1/n)\[\sum_{i=1}^{n}\]xiak[b]

   ≥ (1/n)\[\sum_{i=1}^{n}\]xiak[b'], by Muirhead's Inequality for n-1 elements

   = [a']

Uses of Muirhead's Inequality

Example 1: Prove 2(x5+y5) ≥ (x2+y2)(x3+y3)

Begin by multiplying out the RHS, and subtracting x5+y5 from both sides.
Then note that we are being asked to prove that x5+y5 ≥ x3y2+x2y3.
(5,0) \[\succ\] (3,2), so by Muirhead's Inequality, (1/2!)(x5+y5) ≥ (1/2!)(x3y2+x2y3), and the result follows.

Example 2 (BMO1 2002 Round 1 Q3): Prove for positive reals x,y,z such that x2+y2+z2=1, prove that x2yz+xy2z+xyz2 ≤ 1/3

(4,0,0) \[\succ\] (2,1,1) and (2,2,0) \[\succ\] (2,1,1), so
Eq 1...   (1/3!)(2x4+2y4+2z4) ≥ (1/3!)(2x2yz+2xy2z+2xyz2), and
Eq 2...   (1/3!)(2x2y2+2x2z2+2y2z2) ≥ (1/3!)(2x2yz+2xy2z+2xyz2)

Combine one part Eq 1 with two parts Eq 2, and divide through by common factors, to get

x4+2x2y2+y4+2y2z2+z4+2x2z2 ≥ 3(2x2yz+2xy2z+2xyz2)

Factor the LHS, and then replace the sum x2+y2+z2 with 1, to get the result.

Example 3 (BMO1 1996 Round 1 Q5): Prove for positive reals a,b,c, the following are true:
     4(a3+b3) ≥ (a+b)3, and 9(a3+b3+c3) ≥ (a+b+c)3 

(3,0) \[\succ\] (2,1), so a3+b3 ≥ a2b+ab2.  Multiply both sides by 3, then add a3+b3 to both sides to get the first part of the exercise.

(3,0,0)  \[\succ\] (2,1,0), so 3(2a3 + 2b3 + 2c3) ≥ 3(a2b + a2c + b2a + b2c + c2a + c2b)
(3,0,0)  \[\succ\] (1,1,1), so 2a3 + 2b3 + 2c3 ≥ 6abc, and, of course
(3,0,0)  =  (3,0,0), so a3 + b3 + c3 = a3 + b3 + c3, which I mention only so that I can say the second exercise is done just by adding up the LHS and RHS of these three (in)equalities.

This is going a bit beyond the BMO1 question, but I wonder if 16(a3+b3+c3+d3) ≥ (a+b+c+d)3, so

(3,0,0,0)  \[\succ\] (2,1,0,0), so (3/2)(6)(a3+b3+c3+d3) ≥ (3/2)(2)(a2b+a2c+a2d+b2a+b2c+b2d+c2a+c2b+c2d+d2a+d2b+d2c)
(3,0,0,0)  \[\succ\] (1,1,1,0), so (6)(a3+b3+c3+d3) ≥ (6)(abc+abd+acd+bcd)
(3,0,0,0)  =  (3,0,0,0), so a3 + b3 + c3 + d3 = a3 + b3 + c3 + d3, 
so, indeed, this extension is true.

Generalizing further, if n is the number of variables, we have n2(a3+b3+c3+...) ≥ (a+b+c+...)3.  Is this true?

(3,0,0,...)  \[\succ\] (2,1,0,...), so (3/(n-2)!)(n-1)!(a3+b3+c3+...) ≥ (3/(n-2)!)(n-2)!(a2b+a2c+...)
(3,0,0,...)  \[\succ\] (1,1,1,...), so (1/(n-3)!)(n-1)!(a3+b3+c3+...) ≥ (1/(n-3)!)(6)(n-3)!(abc+abd+...)
(3,0,0,...)  =  (3,0,0,...), so a3 + b3 + c3 + ... = a3 + b3 + c3 + ..., 
so if (3/(n-2)!)(n-1)! + (1/(n-3)!)(n-1)! + 1 = n2, this extension is true.
Indeed, (3/(n-2)!)(n-1)! + (1/(n-3)!)(n-1)! + 1 = 3(n-1) + (n-1)(n-2) + 1 = n2.

Example 4: RMS ≥ AM ≥ GM ≥ HM

For non-negative real x,y,z, prove that the RMS Mean is greater than or equal to the Arithmetic Mean, which in turn is greater than or equal to the Geometric Mean, which in turn is greater than or equal to the Harmonic Mean. i.e.,

sqrt((x2+y2+z2)/3) ≥ (x+y+z)/3 ≥ (xyz)1/3 ≥ 3/(1/x+1/y+1/z)

RMS  ≥  AM

(2,0,0)   \[\succ\] (1,1,0), so 2(x2+y2+z2) ≥ 2(xy+xz+yz).  Adding x2+y2+z2 to both sides gives you
3(x2+y2+z2) ≥ (x+y+z)2, and the result follows by dividing both sides by 9, and taking the square root.

AM  ≥  GM comes directly from (1,0,0) \[\succ\] (1/3,1/3,1/3)

GM  ≥  HM

(4/3,4/3,1/3) \[\succ\] (1,1,1), so
(xyz)1/3(xy+xz+yz) ≥ 3(xyz).  Divide both sides by (xy+xz+yz) to get
(xyz)1/3 ≥ 3(xyz)/(xy+xz+yz), which is GM ≥ HM

Internet References

Andre Rzym: Muirhead's Inequality is a wonderfully well-written article giving background terminology and practical examples of how Muirhead's Inequality is used using the "majorize" approach.

The Art of Problem Solving: Math Forum » Olympiad Section » Inequalities » Muirhead's Inequality 

Muirhead's Inequality, PlanetMath.org

Muirhead's inequality, Wikipedia, which also defines the "a-mean", [a], of x1, x2, ..., xn, where a is a vector, as 1/n! times the sum over all the permutations of a of the product of the x's raised to the exponents from a.  The [1,0,...,0] mean is the arithmetic mean; the [1/n,1/n,...,1/n] mean is the geometric mean.  These definitions demonstrate that Muirhead's Inequality is a super-generalization of all kinds of inequalities involving different kinds of mean.

Related pages in this website

The AM-GM Inequality: the Arithmetic Mean of positive numbers is always greater than the Geometric Mean.  This is proved using Jensen's Inequality.

Schur's Inequality can be used in conjunction with Muirhead's inequality to prove certain symmetric polynomial inequalities.

The Cauchy-Schwarz inequality

The Triangle Inequality

Puzzles

The Quadratic Formula

 


The webmaster and author of the Math Help site is Graeme McRae.
     [home]  [email]  [search]  [Links to Math Sites]  [Whiteboard]