Muirhead's inequality
# Muirhead's inequality

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

## Preliminary definitions

### a-mean

For any real vector

    $a=(a_{1},\dots ,a_{n})$

define the "a-mean" [a] of positive real numbers $x_1,$ ..., $x_n$ by

    $[a]={\frac {1}{n!}}\sum _{\sigma }x_{\sigma _{1}}^{a_{1}}\cdots x_{\sigma _{n}}^{a_{n}},$

where the sum extends over all permutations σ of { 1, ..., n }.

When the elements of a are nonnegative integers, the a-mean can be equivalently defined via the monomial symmetric polynomial $m_{a}(x_{1},\dots ,x_{n})$ as

    $[a]={\frac {k_{1}!\cdots k_{l}!}{n!}}m_{a}(x_{1},\dots ,x_{n}),$

where ℓ is the number of distinct elements in a, and $k_1,$ ..., $k_ℓ$ are their multiplicities.

Notice that the a-mean as defined above only has the usual properties of a mean (e.g., if the mean of equal numbers is equal to them) if $a_{1}+\cdots +a_{n}=1$. In the general case, one can consider instead $[a]^{1/(a_{1}+\cdots +a_{n})}$, which is called a Muirhead mean.

**Examples**

* For a = (1, 0, ..., 0), the a-mean is just the ordinary arithmetic mean of $x_1,$ ..., $x_n.$
* For a = (1/n, ..., 1/n), the a-mean is the geometric mean of $x_1,$ ..., $x_n.$
* For a = (x, 1 − x), the a-mean is the Heinz mean.
* The Muirhead mean for a = (−1, 0, ..., 0) is the harmonic 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.

## Statement

Muirhead's inequality states that [a] ≤ [b] for all x such that $x_i$ > 0 for every i ∈ { 1, ..., n } if and only if there is some doubly stochastic matrix P for which a = Pb.

Furthermore, in that case we have [a] = [b] if and only if a = b or all $x_i$ are equal.

The latter condition can be expressed in several equivalent ways; one of them is given below.

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:

    ${\begin{aligned}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}\\&\,\,\,\vdots \\a_{1}+\cdots +a_{n-1}&\leq b_{1}+\cdots +b_{n-1}\\a_{1}+\cdots +a_{n}&=b_{1}+\cdots +b_{n}.\end{aligned}}$

(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

It is convenient to use a 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 ($\alpha _{1},\ldots ,\alpha _{n}$) majorizes the other one.

    $\sum _{\text{sym}}x_{1}^{\alpha _{1}}\cdots x_{n}^{\alpha _{n}}$

This notation requires developing every permutation, developing an expression made of n! monomials, for instance:

    ${\begin{aligned}\sum _{\text{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}\end{aligned}}$

## Examples

### Arithmetic-geometric mean inequality

Let

    $a_{G}=\left({\frac {1}{n}},\ldots ,{\frac {1}{n}}\right)$

and

    $a_{A}=(1,0,0,\ldots ,0).$

We have

    ${\begin{aligned}a_{A1}=1&>a_{G1}={\frac {1}{n}},\\a_{A1}+a_{A2}=1&>a_{G1}+a_{G2}={\frac {2}{n}},\\&\,\,\,\vdots \\a_{A1}+\cdots +a_{An}&=a_{G1}+\cdots +a_{Gn}=1.\end{aligned}}$

Then

    $[a_A]$ ≥ $[a_G],$

which is

    ${\frac {1}{n!}}(x_{1}^{1}\cdot x_{2}^{0}\cdots x_{n}^{0}+\cdots +x_{1}^{0}\cdots x_{n}^{1})(n-1)!\geq {\frac {1}{n!}}(x_{1}\cdot \cdots \cdot x_{n})^{1/n}n!$

yielding the inequality.

### Other examples

We seek to prove that $x^2$ + $y^2$ ≥ 2xy by using bunching (Muirhead's inequality). We transform it in the symmetric-sum notation:

    $\sum _{\mathrm {sym} }x^{2}y^{0}\geq \sum _{\mathrm {sym} }x^{1}y^{1}.$

The sequence (2, 0) majorizes the sequence (1, 1), thus the inequality holds by bunching.

Similarly, we can prove the inequality

    $x^{3}+y^{3}+z^{3}\geq 3xyz$

by writing it using the symmetric-sum notation as

    $\sum _{\mathrm {sym} }x^{3}y^{0}z^{0}\geq \sum _{\mathrm {sym} }x^{1}y^{1}z^{1},$

which is the same as

    $2x^{3}+2y^{3}+2z^{3}\geq 6xyz.$

Since the sequence (3, 0, 0) majorizes the sequence (1, 1, 1), the inequality holds by bunching.

