NationMaster - Encyclopedia: Muirhead's inequality

In mathematics, Muirhead's inequality, also known as the "bunching" method, generalizes the inequality of arithmetic and geometric means. Euclid, Greek mathematician, 3rd century BC, as imagined by by Raphael in this detail from The School of Athens. ... In mathematics, the inequality of arithmetic and geometric means, or more briefly the AM-GM inequality, states that the arithmetic mean of a list of non-negative real numbers is greater than or equal to the geometric mean of the same list; and further, that the two means are equal...

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

Two preliminary definitions

The "a-mean"

For any real vector In mathematics, the real numbers may be described informally as numbers that can be given by an infinite decimal representation, such as 2. ... In mathematics, a vector space (or linear space) is a collection of objects (called vectors) that, informally speaking, may be scaled and added. ...

$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 }. Permutation is the rearrangement of objects or symbols into distinguishable sequences. ...

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.) In mathematics and statistics, the arithmetic mean (or simply the mean) of a list of numbers is the sum of all the members of the list divided by the number of items in the list. ... The geometric mean of a collection of positive data is defined as the nth root of the product of all the members of the data set, where n is the number of members. ... The Heinz mean of two non-negative real numbers and was defined by Bhatia[1] as: . with 0 =< x =< 1/2. ...

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. In mathematics, especially in probability theory and statistics, and also in linear algebra and computer science, a stochastic matrix is a square matrix whose columns are probability vectors, i. ... In mathematics, especially in probability theory and statistics, and also in linear algebra and computer science, a left stochastic matrix is a square matrix whose columns are probability vectors, i. ...

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). In linear algebra, a permutation matrix is a binary matrix that has exactly one entry 1 in each row and each column and 0s elsewhere. ... In mathematics, especially in probability and combinatorics, a doubly stochastic matrix is a square matrix of nonnegative real numbers, each of whose rows and columns sums to 1. ...

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$

$qquadvdotsqquadvdotsqquadvdotsqquadvdots$

$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

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_{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 !$

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

$qquadvdotsqquadvdotsqquadvdots,$

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

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.

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)

Categories: Inequalities | Means Gian-Carlo Rota (April 27, 1932 – April 18, 1999, known as Juan Carlos Rota to Spanish speakers) was an Italian-born American mathematician and philosopher. ...

COMMENTARY

Share your thoughts, questions and commentary here

Want to know more?
Search encyclopedia, statistics and forums:

Feeds | Contact
The Wikipedia article included on this page is licensed under the GFDL.
Images may be subject to relevant owners' copyright.
All other elements are (c) copyright NationMaster.com 2003-5. All Rights Reserved.
Usage implies agreement with terms.

Contents

Two preliminary definitions GA_googleFillSlot("encyclopedia_square");