Bunching (mathematics)

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''₁, ..., ''x''_''n'' by

: \frac\sum_\sigma x_^\cdots x_^,

where the sum extends over all permutations σ of .

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
: = \frac 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 $a_1+\cdots+a_n=1$. In the general case, one can consider instead , which is called a Muirhead mean.Bullen, P. S. Handbook of means and their inequalities. Kluwer Academic Publishers Group, Dordrecht, 2003.

; Examples
* For ''a'' = (1, 0, ..., 0), the ''a''-mean is just the ordinary arithmetic mean of ''x''₁, ..., ''x''_''n''.
* For ''a'' = (1/''n'', ..., 1/''n''), the ''a''-mean is the geometric mean of ''x''₁, ..., ''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'' ∈ 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 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_ & \leq b_1+\cdots+b_ \\ a_1+\cdots +a_n & = b_1+\cdots+b_n. \end$

(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 x_1^ \cdots x_n^$

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

:$\begin \sum_\text 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$

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 a_ = 1 & > a_ = \frac 1 n, \\ a_ + a_ = 1 & > a_ + a_ = \frac 2 n, \\ & \,\,\, \vdots \\ a_ + \cdots + a_ & = a_ + \cdots + a_ = 1. \end$
Then
: 'a_A''≥ 'a_G''
which is
:$\frac 1 (x_1^1 \cdot x_2^0 \cdots x_n^0 + \cdots + x_1^0 \cdots x_n^1) (n-1)! \geq \frac 1 (x_1 \cdot \cdots \cdot x_n)^ n!$
yielding the inequality.

Other examples

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

:$\sum_ \mathrm x^2 y^0 \ge \sum_\mathrm 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 \ge 3 x y z$

by writing it using the symmetric-sum notation as

:$\sum_ \mathrm x^3 y^0 z^0 \ge \sum_\mathrm x^1 y^1 z^1,$

which is the same as

:$2 x^3 + 2 y^3 + 2 z^3 \ge 6 x y z.$

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

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
*
* Hardy, G.H.; Littlewood, J.E.; Pólya, G. (1952), Inequalities, Cambridge Mathematical Library (2. ed.), Cambridge: Cambridge University Press, , , {{Zbl, 0047.05302, Section 2.18, Theorem 45.

Inequalities
Means