# 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.