Difference between revisions of "Muirhead's Inequality"
m ($c_n$ was written as $cn$.) |
Franklin.vp (talk | contribs) (→Example: The proof below is incorrect. Expanding the example to motivate the upcoming correction to the proof.) |
||
| Line 5: | Line 5: | ||
The inequality is easier to understand given an example. Since the sequence <math>(5,1)</math> majorizes <math>(4,2)</math> (as <math>5>4, 5+1=4+2</math>), Muirhead's inequality states that for any positive <math>x,y</math>, | The inequality is easier to understand given an example. Since the sequence <math>(5,1)</math> majorizes <math>(4,2)</math> (as <math>5>4, 5+1=4+2</math>), Muirhead's inequality states that for any positive <math>x,y</math>, | ||
| − | < | + | <cmath>x^5y^1+y^5x^1\geq x^4y^2+y^4x^2</cmath> |
| + | |||
| + | To understand the proof further below, let's also prove this inequality from the (weighted) AM-GM inequality. | ||
| + | |||
| + | <cmath> | ||
| + | \begin{align*} | ||
| + | x^5y^1+y^5x^1&=\frac{3}{4}\left(x^5y^1+y^5x^1\right)+\frac{1}{4}\left(x^5y^1+y^5x^1\right)\\ | ||
| + | &=\left(\frac{3}{4}x^5y^1+\frac{1}{4}x^1y^5\right)+\left(\frac{3}{4}y^5x^1+\frac{1}{4}y^1x^5\right)\\ | ||
| + | &\geq \left(x^{\frac{3}{4}5+\frac{1}{4}1}y^{\frac{3}{4}1+\frac{1}{4}5}\right)^{3/4+1/4} + \left(y^{\frac{3}{4}5+\frac{1}{4}1}x^{\frac{3}{4}1+\frac{1}{4}5}\right)^{3/4+1/4}\\ | ||
| + | &=x^4y^2+y^2x^4 | ||
| + | \end{align*} | ||
| + | </cmath> | ||
| + | |||
| + | where the step with the inequality consists in applying the weighted AM-GM inequality to each expression in parentheses. | ||
| + | |||
| + | The coefficients <math>3/4</math> and <math>1/4</math> and the use grouping of terms according to the permutations <math>(5,1)</math> and <math>(1,5)</math> come from the following arithmetic facts. | ||
| + | |||
| + | Note that <math>\begin{pmatrix}4\\2\end{pmatrix}=T\begin{pmatrix}5\\1\end{pmatrix}</math>, where the matrix <math>T=\begin{pmatrix}3/4&1/4\\1/4&3/4\end{pmatrix}</math>. This matrix has non-negative entries and all its rows and columns add up to <math>1</math>. Such matrices are called ''doubly stochastic matrices''. We can write <math>T=\frac{3}{4}\begin{pmatrix}1&0\\0&1\end{pmatrix}+\frac{1}{4}\begin{pmatrix}0&1\\1&0\end{pmatrix}</math>. Matrices like <math>P_1=\begin{pmatrix}1&0\\0&1\end{pmatrix}</math> and <math>P_2=\begin{pmatrix}0&1\\1&0\end{pmatrix}</math>, with exactly one <math>1</math> in each row and each column and <math>0</math> everywhere else, are called ''permutation matrices''. Observe how <math>P_1\begin{pmatrix}5\\1\end{pmatrix}=\begin{pmatrix}5\\1\end{pmatrix}</math> and <math>P_2\begin{pmatrix}5\\1\end{pmatrix}=\begin{pmatrix}1\\5\end{pmatrix}</math> gives us all permutations of <math>\begin{pmatrix}5\\1\end{pmatrix}</math>. | ||
| + | |||
| + | So, we can write | ||
| + | |||
| + | <cmath> | ||
| + | \begin{align*} | ||
| + | \begin{pmatrix}4\\2\end{pmatrix}&=T\begin{pmatrix}5\\1\end{pmatrix}\\ | ||
| + | &=\left(\frac{3}{4}\begin{pmatrix}1&0\\0&1\end{pmatrix}+\frac{1}{4}\begin{pmatrix}0&1\\1&0\end{pmatrix}\right)\begin{pmatrix}5\\1\end{pmatrix}\\ | ||
| + | &=\frac{3}{4}\begin{pmatrix}5\\1\end{pmatrix}+\frac{1}{4}\begin{pmatrix}1\\5\end{pmatrix} | ||
| + | \end{align*} | ||
| + | </cmath> | ||
==Proof== | ==Proof== | ||
Revision as of 21:33, 5 July 2023
Muirhead's Inequality states that if a sequence 
majorizes a sequence 
, then given a set of positive reals 
:
![\[\sum_{\text{sym}} {x_1}^{a_1}{x_2}^{a_2}\cdots {x_n}^{a_n}\geq \sum_{\text{sym}} {x_1}^{b_1}{x_2}^{b_2}\cdots {x_n}^{b_n}\]](http://latex.artofproblemsolving.com/5/e/1/5e157632ec46b7ba3c372c33c125ca41760fff43.png)
Example
The inequality is easier to understand given an example. Since the sequence 
majorizes 
(as 
), Muirhead's inequality states that for any positive 
,
![\[x^5y^1+y^5x^1\geq x^4y^2+y^4x^2\]](http://latex.artofproblemsolving.com/c/7/8/c78cdfc8e62ead8d61817d31950523ca284d5fe6.png)
To understand the proof further below, let's also prove this inequality from the (weighted) AM-GM inequality.
where the step with the inequality consists in applying the weighted AM-GM inequality to each expression in parentheses.
The coefficients 
and 
and the use grouping of terms according to the permutations and 
come from the following arithmetic facts.
Note that 
, where the matrix 
. This matrix has non-negative entries and all its rows and columns add up to 
. Such matrices are called doubly stochastic matrices. We can write 
. Matrices like 
and 
, with exactly one in each row and each column and 
everywhere else, are called permutation matrices. Observe how 
and 
gives us all permutations of 
.
So, we can write
Proof
We will first prove an important fact. If we have a sequence 
such that 
, then the following result holds:
![\[\sum_{\text{sym}}{x_1}^{c_1}{x_2}^{c_2}\cdots {x_n}^{c_n}\geq n!\]](http://latex.artofproblemsolving.com/7/8/3/7833656d89e24d05055642e042c85cb3964b426a.png)
for any positive reals 
.
Proof: By AM-GM, we know:
![\[\frac{\sum_{\text{sym}}{x_1}^{c_1}{x_2}^{c_2}\cdots {x_n}^{c_n}}{n!}\geq \sqrt[n!]{\prod_{\text{sym}}{x_1}^{c_1}{x_2}^{c_2}\cdots {x_n}^{c_n}}\]](http://latex.artofproblemsolving.com/6/2/a/62a35e07e7f24da5a49482ffb7ca9d80eec06ae8.png)
However, expanding the right hand side, we see
![\[\sqrt[n!]{\prod_{\text{sym}}{x_1}^{c_1}{x_2}^{c_2}\cdots {x_n}^{c_n}}=\sqrt[n!]{\prod_{i=1}^{n} x_i^{(n-1)!\left(c_1+c_2+\cdots +c_n\right)}}=1\]](http://latex.artofproblemsolving.com/f/9/6/f96dba94a5dc871a061ea6a71aa49b3d03c0f5e5.png)
or
![\[\frac{\sum_{\text{sym}}{x_1}^{c_1}{x_2}^{c_2}\cdots {x_n}^{c_n}}{n!}\geq 1 \Rightarrow \sum_{\text{sym}}{x_1}^{c_1}{x_2}^{c_2}\cdots {x_n}^{c_n}\geq n!\]](http://latex.artofproblemsolving.com/2/7/0/27001a962dc9e3af764949c144482ecd9761c881.png)
We define our sequence such that
![\[c_i=a_i-b_i \hspace{1cm} \forall \hspace{2mm}1\leq i\leq n\]](http://latex.artofproblemsolving.com/a/3/9/a391e17dc907a60ddf9d7e34f4009957930c912f.png)
Note that
![\[\sum_{i=1}^{n} c_i = \sum_{i=1}^{n} a_i-b_i=\sum_{i=1}^{n} a_i - \sum_{i=1}^{n} b_i=0\]](http://latex.artofproblemsolving.com/4/f/5/4f55d4b0c9f3627651213eba3cfcbbe7a5f25eff.png)
Therefore, we get that
![\[\sum_{\text{sym}}\left({x_1}^{c_1}{x_2}^{c_2}\cdots {x_n}^{c_n}\right) -n!\geq 0\]](http://latex.artofproblemsolving.com/f/5/3/f537cad10b41524aaeb983069dcbe1c9e0d88043.png)
We multiply this by 
to get:
![\[\left(\sum_{\text{sym}} \prod_{i=1}^{n}x_i^{b_i}\right)\left(\sum_{\text{sym}}\left({x_1}^{c_1}{x_2}^{c_2}\cdots {x_n}^{c_n}-1\right)\right)=\sum_{\text{sym}} \prod_{i=1}^{n} x_i^{b_i+c_i}-\prod_{i=1}^{n} x_i^{b_i}\geq 0\]](http://latex.artofproblemsolving.com/d/6/1/d61992e8fae6e6c65e1aec90f55b7c80ea828e01.png)
Since 
, we get
![\[\sum_{\text{sym}} \prod_{i=1}^{n} x_i^{a_i}-\prod_{i=1}^{n} x_i^{b_i}\geq 0\]](http://latex.artofproblemsolving.com/7/2/9/7297038fa99841a84812cfdb5a4f1f56f5c4e3b7.png)
or
Usage on Olympiad Problems
A common bruteforce technique with inequalities is to clear denominators, multiply everything out, and apply Muirhead's or Schur's. However, 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; one should use an application of AM-GM instead. Thus, it is suggested that Muirhead be used only to verify that an inequality can be proved with AM-GM before demonstrating the full AM-GM proof.
As an example, the above inequality can be proved using AM-GM as follows:
![$\frac{x^4+x^4+x^4+y^4}{4}\geq\sqrt[4]{x^{12}y^4}=x^3y$](http://latex.artofproblemsolving.com/4/3/e/43e7046bb7e98924c632961732191380a0c2e9c6.png)
![$\frac{x^4+y^4+y^4+y^4}{4}\geq\sqrt[4]{x^4y^{12}}=xy^3$](http://latex.artofproblemsolving.com/3/d/a/3da9a78e244a01a097b79713a99fce41ba63026f.png)
Adding these,
.
Multiplying both sides by 
(as both 
and 
are positive),
as desired.
