Difference between revisions of "Muirhead's Inequality"

 
m (Link to Inequalities article)
Line 44: Line 44:
  
 
as desired.
 
as desired.
 +
 +
Muirhead's inequality is just one of a good many well-known [[Inequalities | inequalities]] that problem-solving students should learn.

Revision as of 19:20, 20 June 2006

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$

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

Adding these, we get

$\displaystyle x^4+y^4\geq x^3y+xy^3$

Multiplying both sides of this by $\displaystyle xy$ (we can do this because both $\displaystyle x$ and $\displaystyle y$ are positive), we get

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

as desired.

Muirhead's inequality is just one of a good many well-known inequalities that problem-solving students should learn.