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"

(Wiki-fied and moved majorization definition)
Line 1: Line 1:
−
'''Muirhead's Inequality''' states that if a sequence <math>A</math> [[Majorization|majorizes]] a sequence <math>B</math>, then given a set of positive integers <math>\displaystyle x_1,x_2,\cdots,x_n</math>:
+
'''Muirhead's Inequality''' states that if a sequence <math>A</math> [[Majorization|majorizes]] a sequence <math>B</math>, then given a set of positive integers <math>x_1,x_2,\cdots,x_n</math>:
  
−
<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>
+
<math>\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>
  
 
=== Example ===
 
=== Example ===
  
−
The inequality is easier to understand given an example.  Since the sequence <math>\displaystyle (5,1)</math> majorizes <math>\displaystyle (4,2)</math>, Muirhead's inequality states that for any positive <math>\displaystyle x,y</math>,
+
The inequality is easier to understand given an example.  Since the sequence <math>(5,1)</math> majorizes <math>(4,2)</math>, Muirhead's inequality states that for any positive <math>x,y</math>,
  
−
<math>\displaystyle x^5y^1+y^5x^1\geq x^4y^2+y^4x^2</math>
+
<math>x^5y^1+y^5x^1\geq x^4y^2+y^4x^2</math>
  
 
=== Usage on Olympiad Problems ===
 
=== Usage on Olympiad Problems ===
Line 15: Line 15:
 
As an example, the above inequality can be proved using AM-GM as follows:
 
As an example, the above inequality can be proved using AM-GM as follows:
  
−
<math>\displaystyle \frac{x^4+x^4+x^4+y^4}{4}\geq\sqrt[4]{x^{12}y^4}=x^3y</math>
+
<math>\frac{x^4+x^4+x^4+y^4}{4}\geq\sqrt[4]{x^{12}y^4}=x^3y</math>
  
−
<math>\displaystyle \frac{x^4+y^4+y^4+y^4}{4}\geq\sqrt[4]{x^4y^{12}}=xy^3</math>
+
<math>\frac{x^4+y^4+y^4+y^4}{4}\geq\sqrt[4]{x^4y^{12}}=xy^3</math>
  
 
Adding these,
 
Adding these,
  
−
<math>\displaystyle x^4+y^4\geq x^3y+xy^3</math>
+
<math>x^4+y^4\geq x^3y+xy^3</math>
  
−
Multiplying both sides by <math>\displaystyle xy</math> (as both <math>\displaystyle x</math> and <math>\displaystyle y</math> are positive),
+
Multiplying both sides by <math>xy</math> (as both <math>x</math> and <math>y</math> are positive),
  
−
<math>\displaystyle x^5y+xy^5\geq x^4y^2+x^2y^4</math>
+
<math>x^5y+xy^5\geq x^4y^2+x^2y^4</math>
  
 
as desired.
 
as desired.
 +
 +
[[Category:Inequality]]
 +
[[Category:Number Theory]]

Revision as of 21:09, 14 October 2007

Muirhead's Inequality states that if a sequence $A$ majorizes a sequence $B$, then given a set of positive integers $x_1,x_2,\cdots,x_n$:

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

Example

The inequality is easier to understand given an example. Since the sequence $(5,1)$ majorizes $(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$

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=18058"