# 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

- [math]\displaystyle{ a=(a_1,\dots,a_n) }[/math]

define the "*a*-mean" [*a*] of positive real numbers *x*_{1}, ..., *x*_{n} by

- [math]\displaystyle{ [a]=\frac{1}{n!}\sum_\sigma x_{\sigma_1}^{a_1}\cdots x_{\sigma_n}^{a_n}, }[/math]

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 [math]\displaystyle{ m_a(x_1,\dots,x_n) }[/math] as

- [math]\displaystyle{ [a] = \frac{k_1!\cdots k_l!}{n!} m_a(x_1,\dots,x_n), }[/math]

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 [math]\displaystyle{ a_1+\cdots+a_n=1 }[/math]. In the general case, one can consider instead [math]\displaystyle{ [a]^{1/(a_1+\cdots+a_n)} }[/math], which is called a Muirhead mean.^{[1]}

- 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:

- [math]\displaystyle{ a_1 \geq a_2 \geq \cdots \geq a_n }[/math]

- [math]\displaystyle{ b_1 \geq b_2 \geq \cdots \geq b_n. }[/math]

Then the existence of a doubly stochastic matrix *P* such that *a* = *Pb* is equivalent to the following system of inequalities:

- [math]\displaystyle{ \begin{align} 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{align} }[/math]

(The *last* one is an equality; the others are weak inequalities.)

The sequence [math]\displaystyle{ b_1, \ldots, b_n }[/math] is said to **majorize** the sequence [math]\displaystyle{ a_1, \ldots, a_n }[/math].

## 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 ([math]\displaystyle{ \alpha_1, \ldots, \alpha_n }[/math]) majorizes the other one.

- [math]\displaystyle{ \sum_\text{sym} x_1^{\alpha_1} \cdots x_n^{\alpha_n} }[/math]

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

- [math]\displaystyle{ \begin{align} \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{align} }[/math]

## Examples

### Arithmetic-geometric mean inequality

Let

- [math]\displaystyle{ a_G = \left( \frac 1 n , \ldots , \frac 1 n \right) }[/math]

and

- [math]\displaystyle{ a_A = ( 1 , 0, 0, \ldots , 0 ). }[/math]

We have

- [math]\displaystyle{ \begin{align} a_{A1} = 1 & \gt a_{G1} = \frac 1 n, \\ a_{A1} + a_{A2} = 1 & \gt a_{G1} + a_{G2} = \frac 2 n, \\ & \,\,\, \vdots \\ a_{A1} + \cdots + a_{An} & = a_{G1} + \cdots + a_{Gn} = 1. \end{align} }[/math]

Then

- [
*a*] ≥ [_{A}*a*],_{G}

which is

- [math]\displaystyle{ \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! }[/math]

yielding the inequality.

### Other examples

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

- [math]\displaystyle{ \sum_ \mathrm{sym} x^2 y^0 \ge \sum_\mathrm{sym} x^1 y^1. }[/math]

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

Similarly, we can prove the inequality

- [math]\displaystyle{ x^3+y^3+z^3 \ge 3 x y z }[/math]

by writing it using the symmetric-sum notation as

- [math]\displaystyle{ \sum_ \mathrm{sym} x^3 y^0 z^0 \ge \sum_\mathrm{sym} x^1 y^1 z^1, }[/math]

which is the same as

- [math]\displaystyle{ 2 x^3 + 2 y^3 + 2 z^3 \ge 6 x y z. }[/math]

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

## See also

- Inequality of arithmetic and geometric means
- Doubly stochastic matrix
- Monomial symmetric polynomial

## Notes

- ↑ Bullen, P. S. Handbook of means and their inequalities. Kluwer Academic Publishers Group, Dordrecht, 2003. ISBN 1-4020-1522-4

## References

*Combinatorial Theory*by John N. Guidi, based on lectures given by Gian-Carlo Rota in 1998, MIT Copy Technology Center, 2002.- Kiran Kedlaya,
*A*<*B*(*A*less than*B*), a guide to solving inequalities - Muirhead's theorem at PlanetMath.org.
- Hardy, G.H.; Littlewood, J.E.; Pólya, G. (1952), Inequalities, Cambridge Mathematical Library (2. ed.), Cambridge: Cambridge University Press, ISBN 0-521-05206-8, MR0046395, Zbl 0047.05302, Section 2.18, Theorem 45.

Original source: https://en.wikipedia.org/wiki/Muirhead's inequality.
Read more |