Muirhead's inequality

From Wikipedia, the free encyclopedia

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

1 Two preliminary definitions
- 1.1 The "a-mean"
- 1.2 Doubly stochastic matrices
2 The inequality
- 2.1 Another equivalent condition
3 Symmetric sum-notation tricks
4 Deriving the arithmetic-geometric mean inequality
5 Examples
6 References

[edit] Two preliminary definitions

[edit] The "a-mean"

For any real vector

$a=(a_1,\dots,a_n)$

define the "a-mean" [a] of nonnegative real numbers x₁, ..., x_n 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 x₁, ..., x_n. In case a = (1/n, ..., 1/n), it is the geometric mean of x₁, ..., x_n. (When n = 2, this is the Heinz mean.)

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

[edit] The inequality

Muirhead's inequality states that [a] ≤ [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 (Birkhoff-von Neumann theorem).

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

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

$\qquad\vdots\qquad\vdots\qquad\vdots\qquad\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$ .

[edit] Symmetric sum-notation tricks

It's tricky and 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_{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_{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 \!$

[edit] Deriving the arithmetic-geometric mean inequality

Let

$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\,$

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

$a_{A1} + \cdots + a_{An} = a_{G1} + \cdots + a_{Gn} = 1 \,$

then

[a_A] ≥ [a_G]

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)^{\frac 1 n} n!$

yielding the inequality.

[edit] Examples

Suppose you want to prove that x² + y² ≥ 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.

[edit] References

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 [1].
Simple explanation with examples
Reference on PlanetMath (Muirhead's theorem)

Retrieved from "http://en.wikipedia.org../../../m/u/i/Muirhead%27s_inequality.html"

Categories: Inequalities | Means

Muirhead's inequality

From Wikipedia, the free encyclopedia

Contents

[edit] Two preliminary definitions

[edit] The "a-mean"

[edit] Doubly stochastic matrices

[edit] The inequality

[edit] Another equivalent condition

[edit] Symmetric sum-notation tricks

[edit] Deriving the arithmetic-geometric mean inequality

[edit] Examples

[edit] References

Views

Navigation

interaction

Search

In other languages