Contents

Muirhead's inequality

Preliminary definitions[edit]

a-mean[edit]

For any real vector

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

define the "a-mean" [a] of positive real numbers x₁, ..., x_nby

${\displaystyle [$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 ${\displaystyle m_{a}(x_{1},\dots ,x_{n})}$as

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

Examples

• For a = (1, 0, ..., 0), the a-mean is just the ordinary arithmetic meanofx₁, ..., x_n.
• For a = (1/n, ..., 1/n), the a-mean is the geometric meanofx₁, ..., 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[edit]

Ann × n matrix Pisdoubly 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[edit]

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[edit]

Because of the symmetry of the sum, no generality is lost by sorting the exponents into decreasing order:

${\displaystyle a_{1}\geq a_{2}\geq \cdots \geq a_{n}}$

${\displaystyle 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:

${\displaystyle {\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 ${\displaystyle b_{1},\ldots ,b_{n}}$ is said to majorize the sequence ${\displaystyle a_{1},\ldots ,a_{n}}$.

Symmetric sum notation[edit]

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 (${\displaystyle \alpha _{1},\ldots ,\alpha _{n}}$) majorizes the other one.

${\displaystyle \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:

${\displaystyle {\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[edit]

Arithmetic-geometric mean inequality[edit]

Let

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

and

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

We have

${\displaystyle {\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

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

yielding the inequality.

Other examples[edit]

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

${\displaystyle \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

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

by writing it using the symmetric-sum notation as

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

which is the same as

${\displaystyle 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.

See also[edit]

• Inequality of arithmetic and geometric means
• Doubly stochastic matrix
• Maclaurin's inequality
• Monomial symmetric polynomial
• Newton's inequalities

Notes[edit]

References[edit]

• 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 theorematPlanetMath.
• 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.