Art of Problem Solving
AoPS Online
Math texts, online classes, and more
for students in grades 5-12.
Visit AoPS Online ‚
Books for Grades 5-12 Online Courses
Beast Academy
Engaging math books and online learning
for students ages 6-13.
Visit Beast Academy ‚
Books for Ages 6-13 Beast Academy Online
AoPS Academy
Small live classes for advanced math
and language arts learners in grades 2-12.
Visit AoPS Academy ‚
Find a Physical Campus Visit the Virtual Campus

Difference between revisions of "Muirhead's Inequality"

(Added bruteforce note)
(→‎Example)
(17 intermediate revisions by 10 users not shown)
Line 1: Line 1:
−
Before '''Muirhead's Inequality''' can be defined, it is first necessary to define another term.
+
'''Muirhead's Inequality''' states that if a sequence <math>A</math> [[Majorization|majorizes]] a sequence <math>B</math>, then given a set of positive reals <math>x_1,x_2,\cdots,x_n</math>:
 +
<cmath>\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}</cmath>
  
−
Given two sequences of real numbers <math>\displaystyle A=a_1,a_2,\cdots,a_n</math> and <math>\displaystyle B=b_1,b_2,\cdots,b_n</math>, <math>A</math> is said to [[Majorization | majorize]] <math>B</math> if and only if all of the following are true:
+
== Example ==
 +
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>,
  
−
<math>\displaystyle a_1\geq b_1</math>  
+
<math>x^5y^1+y^5x^1\geq x^4y^2+y^4x^2</math>.
  
−
<math>\displaystyle a_1+a_2\geq b_1+b_2</math>  
+
==Proof==
 +
We will first prove an important fact. If we have a sequence <math>C</math> such that <math>\sum_{i=1}^{n} c_i = 0</math>, then the following result holds:
 +
<cmath>\sum_{\text{sym}}{x_1}^{c_1}{x_2}^{c_2}\cdots {x_n}^{c_n}\geq n!</cmath>
 +
for any positive reals <math>x_1, x_2, ..., x_n</math>.
  
−
<math>\displaystyle \vdots</math>  
+
Proof: By AM-GM, we know:
 +
<cmath>\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}}</cmath>
  
−
<math>\displaystyle a_1+a_2+\cdots+a_{n-1}\geq b_1+b_2+\cdots+b_{n-1}</math>  
+
However, expanding the right hand side, we see
 +
<cmath>\sqrt[n!]{\prod_{\text{sym}}{x_1}^{c_1}{x_2}^{c_2}\cdots {x_n}^{cn}}=\sqrt[n!]{\prod_{i=1}^{n} x_i^{(n-1)!\left(c_1+c_2+\cdots +c_n\right)}}=1</cmath>
 +
or
 +
<cmath>\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!</cmath>
  
−
<math>\displaystyle a_1+a_2+\cdots+a_n=b_1+b_2+\cdots+b_n</math>
+
We define our sequence <math>C</math> such that
 +
<cmath>c_i=a_i-b_i \hspace{1cm} \forall \hspace{2mm}1\leq i\leq n</cmath>
  
 +
Note that
 +
<cmath>\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</cmath>
  
 +
Therefore, we get that
 +
<cmath>\sum_{\text{sym}}\left({x_1}^{c_1}{x_2}^{c_2}\cdots {x_n}^{c_n}\right) -n!\geq 0</cmath>
  
−
With this out of the way, it is now possible to define Muirhead's Inequality.
+
We multiply this by <math>\sum_{\text{sym}} \prod_{i=1}^{n}x_i^{b_i}</math> to get:
 +
<cmath>\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</cmath>
  
−
Let <math>\displaystyle x_1,x_2,\cdots,x_n</math> be a set of positive integers, and let <math>\displaystyle A=a_1,a_2,\cdots,a_n</math>, and <math>\displaystyle B=b_1,b_2,\cdots,b_n</math> be sets of positive real numbers (note that they all contain the same number of terms) such that <math>\displaystyle A</math> majorizes <math>\displaystyle B</math>.  Then, using [[sigma notation]], it is possible to say that
+
Since <math>b_i+c_i=b_i+a_i-b_i=a_i</math>, we get
 +
<cmath>\sum_{\text{sym}} \prod_{i=1}^{n} x_i^{a_i}-\prod_{i=1}^{n} x_i^{b_i}\geq 0</cmath>
 +
or
 +
<cmath>\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}</cmath>
  
−
<math>\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}</math>
+
== Usage on Olympiad Problems ==
 +
A common [[Brute forcing|bruteforce]] technique with inequalities is to clear denominators, multiply everything out, and apply Muirhead's or [[Schur's Inequality|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 | Arithmetic Mean-Geometric Mean]] inequality.  In fact, [[International Mathematics Olympiad | 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.
  
−
A concrete example will probably help to understand the inequality.  Since the sequence <math>\displaystyle 5,1</math> majorizes <math>\displaystyle 4,2</math>, Muirhead's inequality tells us that, for any positive <math>\displaystyle x,y</math>, we have
+
As an example, the above inequality can be proved using AM-GM as follows:
  
−
<math>\displaystyle x^5y^1+y^5x^1\geq x^4y^2+y^4x^2</math>
+
<math>\frac{x^4+x^4+x^4+y^4}{4}\geq\sqrt[4]{x^{12}y^4}=x^3y</math>
  
 +
<math>\frac{x^4+y^4+y^4+y^4}{4}\geq\sqrt[4]{x^4y^{12}}=xy^3</math>
  
 +
Adding these,
  
−
A common [[Brute forcing|bruteforce]] technique with inequalities is to clear denominators, multiply everything out, and apply Muirhead's or [[Schur's Inequality|Shur'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 | Arithmetic Mean-Geometric Mean]] inequality.  In fact, [[International Mathematics Olympiad | 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.
+
<math>x^4+y^4\geq x^3y+xy^3</math>.
  
−
As an example, here's how the above inequality can be proved using AM-GM:
+
Multiplying both sides by <math>xy</math> (as both <math>x</math> and <math>y</math> are positive),
  
−
<math>\displaystyle \frac{x^4+x^4+x^4+y^4}{4}\geq\sqrt[4]{x^{12}y^4}=x^3y</math>
+
<math>x^5y+xy^5\geq x^4y^2+x^2y^4</math>
−
 
 
−
<math>\displaystyle \frac{x^4+y^4+y^4+y^4}{4}\geq\sqrt[4]{x^4y^{12}}=xy^3</math>
 
−
 
 
−
Adding these, we get
 
−
 
 
−
<math>\displaystyle x^4+y^4\geq x^3y+xy^3</math>
 
−
 
 
−
Multiplying both sides of this by <math>\displaystyle xy</math> (we can do this because both <math>\displaystyle x</math> and <math>\displaystyle y</math> are positive), we get
 
−
 
 
−
<math>\displaystyle x^5y+xy^5\geq x^4y^2+x^2y^4</math>
 
  
 
as desired.
 
as desired.
  
−
Muirhead's inequality is just one of a good many well-known [[Inequality | inequalities]] that problem-solving students should learn.
+
[[Category:Inequality]]
 +
[[Category:Theorems]]

Revision as of 01:14, 4 January 2020

Muirhead's Inequality states that if a sequence $A$ majorizes a sequence $B$, then given a set of positive reals $x_1,x_2,\cdots,x_n$: \[\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}\]

Example

The inequality is easier to understand given an example. Since the sequence $(5,1)$ majorizes $(4,2)$ (as $5>4, 5+1=4+2$), Muirhead's inequality states that for any positive $x,y$,

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

Proof

We will first prove an important fact. If we have a sequence $C$ such that $\sum_{i=1}^{n} c_i = 0$, then the following result holds: \[\sum_{\text{sym}}{x_1}^{c_1}{x_2}^{c_2}\cdots {x_n}^{c_n}\geq n!\] for any positive reals $x_1, x_2, ..., x_n$.

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}}\]

However, expanding the right hand side, we see \[\sqrt[n!]{\prod_{\text{sym}}{x_1}^{c_1}{x_2}^{c_2}\cdots {x_n}^{cn}}=\sqrt[n!]{\prod_{i=1}^{n} x_i^{(n-1)!\left(c_1+c_2+\cdots +c_n\right)}}=1\] 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!\]

We define our sequence $C$ such that \[c_i=a_i-b_i \hspace{1cm} \forall \hspace{2mm}1\leq i\leq n\]

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\]

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\]

We multiply this by $\sum_{\text{sym}} \prod_{i=1}^{n}x_i^{b_i}$ 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\]

Since $b_i+c_i=b_i+a_i-b_i=a_i$, we get \[\sum_{\text{sym}} \prod_{i=1}^{n} x_i^{a_i}-\prod_{i=1}^{n} x_i^{b_i}\geq 0\] or \[\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}\]

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$

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

Adding these,

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

Multiplying both sides by $xy$ (as both $x$ and $y$ are positive),

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

as desired.

Retrieved from "https://artofproblemsolving.com/wiki/index.php?title=Muirhead%27s_Inequality&oldid=114247"