
Let s_{1}
≥ s_{2}
≥ ... ≥ s_{n}
≥ 0 and
t_{1}
≥ t_{2}
≥ ... ≥ t_{n}
≥ 0 and
the sum from i=1 to n of s_{i} equals the sum from i=1 to n of t_{i},
and
for all k < n, the sum from i=1 to k of s_{i} is less than the sum from
i=1 to k of t_{i}.
Let s_{1} ≥ s_{2} ≥ ... ≥ s_{n} ≥ 0, and  
t_{1} ≥ t_{2} ≥ ... ≥ t_{n} ≥ 0, and  


Then for all nonnegative numbers x_{1}, x_{2}, ..., x_{n},  


where the sums run over all the permutations σ of {1, 2, 3, ..., n} 
Andre Rzym's Muirhead's Inequality introduces background terminology to simplify the expression of the inequality.
In a nutshell, a sequence, (a), of reals (a_{1}, a_{2}, ..., a_{n}) "majorizes" another sequence, (a'), of reals (a_{1}', a_{2}', ..., a_{n}') if
(a) majorizes (a') is written (a) (a')
Examples
because 3+0+0 = 2+1+0, 3 ≥ 2, and 3+0 ≥ 2+1
since the number of elements is different
since terms cannot be negative
since the sums of the two sequences are different
since the partial sum 4+1 is smaller than 3+3
The "symmetric mean", [a] of nonnegative reals x_{1}, x_{2}, ..., x_{n} 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) (a'), then [a] ≥ [a'], with equality iff (a) = (a') or all the x_{i} are equal.
Muirhead's Inequality is, in a sense, a sweeping generalization of the AMGM 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 onesum sequence in between them.
So an approach to proving Muirhead's Inequality begins by with the weighted twovariable AMGM 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) (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) (a') (a")
This sets us up nicely for the induction step, which shows that whenever (a) (a'), and the two sequences share an element, Muirhead's Inequality boils down to a similar inequality with one fewer elements.
Statement of the two variable case: Let (n,m) (p,q). Then for arbitrary positive reals x and y, x^{n}y^{m}+x^{m}y^{n} ≥ x^{p}y^{q}+x^{q}y^{p}, with equality iff n=p or x=y.
Let w=(nq)/(nm). Because n ≥ p ≥ q ≥ m, we see that w is between 0 and 1 (inclusive), and so is (1w). Then w and (1w) are two weights, both nonnegative, whose sum is 1.
Note that wn+(1w)m = wnwm+m = w(nm)+m = nq+m = p, and
wm+(1w)n = wmwn+n = nw(nm) = n(nq) = q.
Let x and y be arbitrary positive reals. By rewriting x^{n}y^{m}+x^{m}y^{n} as the sum of two weighted averages (with the weights switched), and then by applying the weighted AMGM inequality (wa+(1w)b ≥ a^{w}b^{1w}) twice, we see:
x^{n}y^{m}+x^{m}y^{n} = wx^{n}y^{m}+(1w)x^{m}y^{n}+(1w)x^{n}y^{m}+wx^{m}y^{n}
≥ x^{wn}y^{wm}x^{(1w)m}y^{(1w)n}
+ x^{(1w)n}y^{(1w)m}x^{wm}y^{wn}
= x^{wn+(1w)m}y^{wm+(1w)n} + x^{(1w)n+wm}y^{(1w)m+wn}
= x^{p}y^{q}+x^{q}y^{p}.
Let (a) and (a") be sequences of three or more elements, arranged in descending order, such that (a) (a"). For convenience, we will define
(a) = (a_{1}, a_{2}, ..., a_{n})
(a") = (a_{1}", a_{2}", ..., a_{n}")
I start by looking at the "gap", or difference, between elements of (a) and (a"). Because (a) (a"), a_{1}≥a_{1}", and a_{n}≤a_{n}", so an i exists such that a_{i+1}≤a_{i+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:
a_{k}≥a_{k}", by our choice of k,
a_{k}"≥a_{k+1}", because (a") is arranged in descending order, and
a_{k+1}"≥a_{k+1}, by our choice of k.
Now I will define (a') by picking all of the elements from (a) except a_{k} and a_{k+1}, one of the elements of (a")  either a_{k}" or a_{k+1}"  and then adjusting a_{k+1}' or a_{k}' 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 a_{k}≥a_{k}" and a_{k+1}≤a_{k+1}" so I look for the smaller (in absolute value) of a_{k}a_{k}" and a_{k+1}a_{k+1}". If the "k" gap is smaller, I set a_{k}'=a_{k}". Otherwise, I set a_{k+1}'=a_{k+1}". Here it is again, algebraically, just to make it official:
All of a_{i}' = a_{i}, except a_{k}' and a_{k+1}'.
If a_{k}a_{k}" < a_{k+1}"a_{k+1 }then a_{k}'=a_{k}", and a_{k+1}'=a_{k}+a_{k+1}a_{k}"
If a_{k}a_{k}" ≥ a_{k+1}"a_{k+1 }then a_{k+1}'=a_{k+1}", and a_{k}'=a_{k}+a_{k+1}a_{k+1}"Note that a_{k}' is set to the larger of a_{k}" and a_{k}+a_{k+1}a_{k+1}", both of which are no larger than a_{k},
while a_{k+1}' is set to the smaller of a_{k+1}" and a_{k}+a_{k+1}a_{k}", both of which are at least as large as a_{k+1}.
(From this we see that a_{k} ≥a_{k}' ≥a_{k}", which will be important later. We also see that a_{k+1}≤a_{k+1}'≤a_{k+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) (a'), and that (a') (a").
Descending Order
If k>1, then a_{k1}'=a_{k1}≥a_{k}≥a_{k}'≥a_{k}"≥a_{k+1}"≥a_{k+1}'≥a_{k+1}. If k=1 then the first inequality isn't meaningful, but the rest still apply.
(a) (a')
(a') is the same as (a) except for a_{k}' and a_{k+1}', which, though different from their counterparts in (a) have the property that a_{k}'+a_{k+1}'=a_{k}+a_{k+1}. So the only partial sum of (a') that differs from that of (a) is the one whose last terms is a_{k}'. And since a_{k} ≥a_{k}', this partial sum of (a') is no larger than that of (a), so (a) (a').
(a') (a")
(a) (a"), and the partial sums of (a') differ from those of (a) only once, to wit when the last term is a_{k}'. And since a_{k}'≥a_{k}", this partial sum of (a') is at least as large as that of (a"), so (a') (a").
Statement of this step: If (a) and (a') have n≥3 elements, including one element in common (a_{k}=a_{k}' for some k) and (a) (a'), then [a] ≥ [a'].
As this is the induction step, we assume Muirhead's Inequality is true for n1 elements. In particular, where (b)=(a)\{a_{k}}, and (b')=(a')\{a_{k}'}, we assume that [b] ≥ [b'].
Recall that [a] is the symmetric mean of n arbitrary positive reals x_{1},x_{2},...,x_{n}. In the following sum, we will assume [b] refers to the symmetric mean of all but one of those reals, that one being x_{i}:
[a] = (1/n)x_{i}^{a}k[b]
≥ (1/n)x_{i}^{a}k[b'], by Muirhead's Inequality for n1 elements
= [a']
Example 1: Prove 2(x^{5}+y^{5}) ≥ (x^{2}+y^{2})(x^{3}+y^{3})
Begin by multiplying out the RHS, and subtracting x^{5}+y^{5} from both sides.
Then note that we are being asked to prove that x^{5}+y^{5} ≥ x^{3}y^{2}+x^{2}y^{3}.
(5,0) (3,2), so by Muirhead's Inequality, (1/2!)(x^{5}+y^{5}) ≥ (1/2!)(x^{3}y^{2}+x^{2}y^{3}), and the result follows.
Example 2 (BMO1 2002 Round 1 Q3): Prove for positive reals x,y,z such that x^{2}+y^{2}+z^{2}=1, prove that x^{2}yz+xy^{2}z+xyz^{2} ≤ 1/3
(4,0,0) (2,1,1) and (2,2,0) (2,1,1), so
Eq 1... (1/3!)(2x^{4}+2y^{4}+2z^{4}) ≥ (1/3!)(2x^{2}yz+2xy^{2}z+2xyz^{2}), and
Eq 2... (1/3!)(2x^{2}y^{2}+2x^{2}z^{2}+2y^{2}z^{2}) ≥ (1/3!)(2x^{2}yz+2xy^{2}z+2xyz^{2})Combine one part Eq 1 with two parts Eq 2, and divide through by common factors, to get
x^{4}+2x^{2}y^{2}+y^{4}+2y^{2}z^{2}+z^{4}+2x^{2}z^{2} ≥ 3(2x^{2}yz+2xy^{2}z+2xyz^{2})
Factor the LHS, and then replace the sum x^{2}+y^{2}+z^{2} 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(a^{3}+b^{3}) ≥ (a+b)^{3}, and
9(a^{3}+b^{3}+c^{3}) ≥ (a+b+c)^{3}
(3,0) (2,1), so a^{3}+b^{3} ≥ a^{2}b+ab^{2}. Multiply both sides by 3, then add a^{3}+b^{3} to both sides to get the first part of the exercise.
(3,0,0) (2,1,0), so 3(2a^{3} + 2b^{3} + 2c^{3}) ≥ 3(a^{2}b + a^{2}c + b^{2}a + b^{2}c + c^{2}a + c^{2}b)
(3,0,0) (1,1,1), so 2a^{3} + 2b^{3} + 2c^{3} ≥ 6abc, and, of course
(3,0,0) = (3,0,0), so a^{3} + b^{3} + c^{3} = a^{3} + b^{3} + c^{3}, 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(a^{3}+b^{3}+c^{3}+d^{3}) ≥ (a+b+c+d)^{3}, so
(3,0,0,0) (2,1,0,0), so (3/2)(6)(a^{3}+b^{3}+c^{3}+d^{3}) ≥ (3/2)(2)(a^{2}b+a^{2}c+a^{2}d+b^{2}a+b^{2}c+b^{2}d+c^{2}a+c^{2}b+c^{2}d+d^{2}a+d^{2}b+d^{2}c)
(3,0,0,0) (1,1,1,0), so (6)(a^{3}+b^{3}+c^{3}+d^{3}) ≥ (6)(abc+abd+acd+bcd)
(3,0,0,0) = (3,0,0,0), so a^{3} + b^{3} + c^{3} + d^{3} = a^{3} + b^{3} + c^{3} + d^{3},
so, indeed, this extension is true.Generalizing further, if n is the number of variables, we have n^{2}(a^{3}+b^{3}+c^{3}+...) ≥ (a+b+c+...)^{3}. Is this true?
(3,0,0,...) (2,1,0,...), so (3/(n2)!)(n1)!(a^{3}+b^{3}+c^{3}+...) ≥ (3/(n2)!)(n2)!(a^{2}b+a^{2}c+...)
(3,0,0,...) (1,1,1,...), so (1/(n3)!)(n1)!(a^{3}+b^{3}+c^{3}+...) ≥ (1/(n3)!)(6)(n3)!(abc+abd+...)
(3,0,0,...) = (3,0,0,...), so a^{3} + b^{3} + c^{3} + ... = a^{3} + b^{3} + c^{3} + ...,
so if (3/(n2)!)(n1)! + (1/(n3)!)(n1)! + 1 = n^{2}, this extension is true.
Indeed, (3/(n2)!)(n1)! + (1/(n3)!)(n1)! + 1 = 3(n1) + (n1)(n2) + 1 = n^{2}.
Example 4: RMS ≥ AM ≥ GM ≥ HM
For nonnegative 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((x^{2}+y^{2}+z^{2})/3) ≥ (x+y+z)/3 ≥ (xyz)^{1/3} ≥ 3/(1/x+1/y+1/z)
RMS ≥ AM
(2,0,0) (1,1,0), so 2(x^{2}+y^{2}+z^{2}) ≥ 2(xy+xz+yz). Adding x^{2}+y^{2}+z^{2} to both sides gives you
3(x^{2}+y^{2}+z^{2}) ≥ (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) (1/3,1/3,1/3)
GM ≥ HM
(4/3,4/3,1/3) (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
Andre Rzym: Muirhead's Inequality is a wonderfully wellwritten 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 "amean", [a], of x_{1}, x_{2}, ..., x_{n}, 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 supergeneralization of all kinds of inequalities involving different kinds of mean.
The AMGM 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 webmaster and author of this Math Help site is Graeme McRae.