Muirhead's inequality

From Wikipedia, the free encyclopedia
Jump to: navigation, search

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

The "a-mean"[edit]

For any real vector


define the "a-mean" [a] of nonnegative real numbers x1, ..., xn by

[a]={1 \over n!}\sum_\sigma x_{\sigma_1}^{a_1}\cdots x_{\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 x1, ..., xn. In case a = (1/n, ..., 1/n), it is the geometric mean of x1, ..., xn. (When n = 2, this is the Heinz mean.)

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.[1]

Doubly stochastic matrices[edit]

An n × n matrix P is doubly stochastic precisely if both P and its transpose PT 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.

The inequality[edit]

Muirhead's inequality states that [a] ≤ [b] for all x such that xi ≥ 0 for all xi if and only if there is some doubly stochastic matrix P for which a = Pb.

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:

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:

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.

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

It is useful to use a kind of 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:

& \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

Deriving the arithmetic-geometric mean inequality[edit]


a_G = \left( \frac 1 n , \ldots ,  \frac 1 n \right)
a_A = ( 1 , 0, 0, \ldots ,  0 )\,

we have

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


[aA] ≥ [aG]

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.


Suppose you want to prove that x2 + y2 ≥ 2xy by using bunching (Muirhead's inequality): We transform it in the symmetric-sum notation:

\sum_ \mathrm{sym} x^2 y^0 \ge \sum_\mathrm{sym} x^1 y^1.\

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

x^3+y^3+z^3 \ge 3 x y z
\sum_ \mathrm{sym} x^3 y^0 z^0 \ge \sum_\mathrm{sym} x^1 y^1 z^1

which yields

 2 x^3 + 2 y^3 + 2 z^3 \ge 6 x y z

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


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