Discover

In mathematics, 'Muirhead's inequality', also known as the "bunching" method, generalizes the inequality of arithmetic and geometric means.

Contents

Two preliminary definitions

The "''a''-mean"

Doubly stochastic matrices

The inequality

Another equivalent condition

Symmetric sum-notation tricks

Deriving the arithmetic-geometric mean inequality

Examples

References

Two preliminary definitions

The "''a''-mean"

For any real vector
:$a=(a\_1,dots,a\_n)$
define the "''a''-mean" [''a''] of nonnegative real numbers ''x''₁, ..., ''x''_''n'' by
:$[a]=\{1\; over\; n!\}sum\_sigma\; x\_\{sigma\_1\}^\{a\_1\}cdots\; x\_\{sigma\_n\}^\{a\_n\},$
where the sum extends over all permutations σ of { 1, ..., ''n'' }.
In case ''a'' = (1, 0, ..., 0), this is just the ordinary arithmetic mean of ''x''₁, ..., ''x''_''n''. In case ''a'' = (1/''n'', ..., 1/''n''), it is the geometric mean of ''x''₁, ..., ''x''_''n''. (When ''n'' = 2, this is the Heinz mean.)

Doubly stochastic matrices

An ''n'' × ''n'' matrix ''P'' is ''doubly stochastic'' precisely if both ''P'' and its transpose ''P''^T are stochastic matrices. A ''stochastic matrix'' is a square matrix of nonnegative real entries in which the sum of the entries in each column is 1. Thus, a doubly stochastic matrix is a square matrix of nonnegative real entries in which the sum of the entries in each row and the sum of the entries in each column is 1.

The inequality

Muirhead's inequality states that [''a''] ≤ [''b''] for all ''x''_''i'' ≥ 0 if and only if there is some doubly stochastic matrix ''P'' for which ''a'' = ''Pb''.
The proof makes use of the fact that every doubly stochastic matrix is a weighted average of permutation matrices (Birkhoff-von Neumann theorem).

Another equivalent condition

Because of the symmetry of the sum, no generality is lost by sorting the exponents into decreasing order:
:$a\_1\; geq\; a\_2\; geq\; cdots\; geq\; a\_n$
:$b\_1\; geq\; b\_2\; geq\; cdots\; geq\; b\_n$
Then the existence of a doubly stochastic matrix ''P'' such that ''a'' = ''Pb'' is equivalent to the following system of inequalities:
:$a\_1\; leq\; b\_1$
:$a\_1+a\_2\; leq\; b\_1+b\_2$
:$a\_1+a\_2+a\_3\; leq\; b\_1+b\_2+b\_3$
:
:$a\_1+cdots\; +a\_\{n-1\}\; leq\; b\_1+cdots+b\_\{n-1\}$
:$a\_1+cdots\; +a\_n=b\_1+cdots+b\_n.$
(The ''last'' one is an equality; the others are weak inequalities.)
The sequence $b\_1,\; ldots,\; b\_n$ is said to 'majorize' the sequence $a\_1,\; ldots,\; a\_n$.

Symmetric sum-notation tricks

It is useful to use a kind of special notation for the sums. A success in reducing an inequality in this form means that the only condition for testing it is to verify whether one exponent sequence () majorizes the other one.
:
This notation requires developing every permutation, developing an expression made of n! monomials, for instance:
:$sum\_\{sym\}\; x^3\; y^2\; z^0\; =\; x^3\; y^2\; z^0\; +\; x^3\; z^2\; y^0\; +\; y^3\; x^2\; z^0\; +\; y^3\; z^2\; x^0\; +\; z^3\; x^2\; y^0\; +\; z^3\; y^2\; x^0\; =\; x^3\; y^2\; +\; x^3\; z^2\; +\; y^3\; x^2\; +\; y^3\; z^2\; +\; z^3\; x^2\; +\; z^3\; y^2\; !$

Deriving the arithmetic-geometric mean inequality

Let
:
ight)
:$a\_A\; =\; (\; 1\; ,\; 0,\; 0,\; ldots\; ,\; 0\; ),$
we have
:
:
:
:$a\_\{A1\}\; +\; cdots\; +\; a\_\{An\}\; =\; a\_\{G1\}\; +\; cdots\; +\; a\_\{Gn\}\; =\; 1\; ,$
then
:[''a_A''] ≥ [''a_G'']
which is
:
yielding the inequality.

Examples

Suppose you want to prove that ''x''² + ''y''² ≥ 2''xy'' by using bunching (Muirhead's inequality):
We transform it in the symmetric-sum notation:
:$sum\_\; mathrm\{sym\}\; x^2\; y^0\; ge\; sum\_mathrm\{sym\}\; x^1\; y^1$
The sequence (2, 0) majorizes the sequence (1, 1), thus the inequality holds by bunching. Again,
:$x^3+y^3+z^3\; ge\; 3\; x\; y\; z$
:$sum\_\; mathrm\{sym\}\; x^3\; y^0\; z^0\; ge\; sum\_mathrm\{sym\}\; x^1\; y^1\; z^1$
which yields
:$2\; x^3\; +\; 2\; y^3\; +\; 2\; z^3\; ge\; 6\; x\; y\; z$
the sequence (3, 0, 0) majorizes the sequence (1, 1, 1), thus the inequality holds by bunching.

References

★ ''Combinatorial Theory'' by John N. Guidi, based on lectures given by Gian-Carlo Rota in 1998, MIT Copy Technology Center, 2002.

★ Kiran Kedlaya's guide to solving inequalities at [1].

★ Simple explanation with examples

★ Reference on PlanetMath (Muirhead's theorem)