Muirhead's Inequality

Before Muirhead's Inequality can be defined, it is first necessary to define another term.

Given two sequences of real numbers $\displaystyle A=a_1,a_2,\cdots,a_n$ and $\displaystyle B=b_1,b_2,\cdots,b_n$ , $A$ is said to majorize $B$ if and only if all of the following are true:

$\displaystyle a_1\geq b_1$

$\displaystyle a_1+a_2\geq b_1+b_2$

$\displaystyle \vdots$

$\displaystyle a_1+a_2+\cdots+a_{n-1}\geq b_1+b_2+\cdots+b_{n-1}$

$\displaystyle a_1+a_2+\cdots+a_n=b_1+b_2+\cdots+b_n$

With this out of the way, it is now possible to define Muirhead's Inequality.

Let $\displaystyle x_1,x_2,\cdots,x_n$ be a set of positive integers, and let $\displaystyle A=a_1,a_2,\cdots,a_n$ , and $\displaystyle B=b_1,b_2,\cdots,b_n$ be sets of positive real numbers (note that they all contain the same number of terms) such that $\displaystyle A$ majorizes $\displaystyle B$ . Then, using sigma notation, it is possible to say that

$\displaystyle \sum_{sym} {x_1}^{a_1}{x_2}^{a_2}\cdots {x_n}^{a_n}\geq \sum_{sym} {x_1}^{b_1}{x_2}^{b_2}\cdots {x_n}^{b_n}$

A concrete example will probably help to understand the inequality. Since the sequence $\displaystyle 5,1$ majorizes $\displaystyle 4,2$ , Muirhead's inequality tells us that, for any positive $\displaystyle x,y$ , we have

$\displaystyle x^5y^1+y^5x^1\geq x^4y^2+y^4x^2$

It is worth noting that any inequality that can be proved directly with Muirhead can also be proved using the Arithmetic Mean-Geometric Mean inequality. In fact, IMO gold medalist Thomas Mildorf says it is unwise to use Muirhead in an Olympiad solution; you should use an application of AM-GM instead.

As an example, here's how the above inequality can be proved using AM-GM:

$\displaystyle \frac{x^4+x^4+x^4+y^4}{4}\geq\sqrt[4]{x^{12}y^4}=x^3y$