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

Two preliminary definitions

The "a-mean"

For any real vector

$a=(a\_1,\backslash dots,a\_n)$

define the "a-mean" ^* of nonnegative real numbers x₁, ..., x_n by

$*=\{1\; \backslash over\; n!\}\backslash sum\_\backslash sigma\; x\_\{\backslash sigma\_1\}^\{a\_1\}\backslash cdots\; x\_\{\backslash 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.

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 matric 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 ≤ [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.

Another equivalent condition

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

$a\_1\backslash geq\; a\_2\; \backslash geq\; \backslash cdots\; \backslash geq\; a\_n$

$b\_1\backslash geq\; b\_2\; \backslash geq\; \backslash cdots\; \backslash 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\; \backslash leq\; b\_1$

$a\_1+a\_2\; \backslash leq\; b\_1+b\_2$

$a\_1+a\_2+a\_3\; \backslash leq\; b\_1+b\_2+b\_3$

$\backslash qquad\backslash vdots\backslash qquad\backslash vdots\backslash qquad\backslash vdots\backslash qquad\backslash vdots$

$a\_1+\backslash cdots\; +a\_\{n-1\}\; \backslash leq\; b\_1+\backslash cdots+b\_\{n-1\}$

$a\_1+\backslash cdots\; +a\_n=b\_1+\backslash cdots+b\_n.$

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

Deriving the arithmetic-geometric mean inequality

Let

$a\_G\; =\; \backslash left(\; \backslash frac\; 1\; n\; ,\; \backslash ldots\; ,\; \backslash frac\; 1\; n\; \backslash right)$

$a\_A\; =\; (\; 1\; ,\; 0,\; 0,\; \backslash ldots\; ,\; 0\; )\backslash ,$

we have

$a\_\{A1\}\; =\; 1\; >\; a\_\{G1\}\; =\; \backslash frac\; 1\; n\; \backslash ,$

$a\_\{A1\}\; +\; a\_\{A2\}\; =\; 1\; >\; a\_\{G1\}\; +\; a\_\{G2\}\; =\; \backslash frac\; 2\; n\backslash ,$

$\backslash qquad\backslash vdots\backslash qquad\backslash vdots\backslash qquad\backslash vdots\backslash ,$

$a\_\{A1\}\; +\; \backslash cdots\; +\; a\_\{An\}\; =\; a\_\{G1\}\; +\; \backslash cdots\; +\; a\_\{Gn\}\; =\; 1\; \backslash ,$

then

≥ [a_G

which is

$\backslash frac\; 1\; \{n!\}\; (x\_1^1\; \backslash cdot\; x\_2^0\; \backslash cdots\; x\_n^0\; +\; \backslash cdots\; +\; x\_1^0\; \backslash cdots\; x\_n^1)\; (n-1)!\; \backslash geq\; \backslash frac\; 1\; \{n!\}\; (x\_1\; \backslash cdot\; \backslash cdots\; \backslash cdot\; x\_n)^\{\backslash frac\; 1\; n\}\; n!$

yielding the inequality.

Reference

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 ^*.

Inequalities | Means

Muirhead-Ungleichung