Muirhead's inequality (original) (raw)

From Wikipedia, the free encyclopedia

Mathematical inequality

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]

For any real vector

a = ( a 1 , … , a n ) {\displaystyle a=(a_{1},\dots ,a_{n})} {\displaystyle a=(a_{1},\dots ,a_{n})}

define the "_a_-mean" [_a_] of positive real numbers _x_1, ..., x n by

[ a ] = 1 n ! ∑ σ x σ 1 a 1 ⋯ x σ n a n , {\displaystyle [a]={\frac {1}{n!}}\sum _{\sigma }x_{\sigma _{1}}^{a_{1}}\cdots x_{\sigma _{n}}^{a_{n}},} {\displaystyle [a]={\frac {1}{n!}}\sum _{\sigma }x_{\sigma _{1}}^{a_{1}}\cdots x_{\sigma _{n}}^{a_{n}},}

where the sum extends over all permutations σ of { 1, ..., n }.

When the elements of a are nonnegative integers, the _a_-mean can be equivalently defined via the monomial symmetric polynomial m a ( x 1 , … , x n ) {\displaystyle m_{a}(x_{1},\dots ,x_{n})} {\displaystyle m_{a}(x_{1},\dots ,x_{n})} as

[ a ] = k 1 ! ⋯ k l ! n ! m a ( x 1 , … , x n ) , {\displaystyle [a]={\frac {k_{1}!\cdots k_{l}!}{n!}}m_{a}(x_{1},\dots ,x_{n}),} {\displaystyle [a]={\frac {k_{1}!\cdots k_{l}!}{n!}}m_{a}(x_{1},\dots ,x_{n}),}

where ℓ is the number of distinct elements in a, and _k_1, ..., _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 + ⋯ + a n = 1 {\displaystyle a_{1}+\cdots +a_{n}=1} {\displaystyle a_{1}+\cdots +a_{n}=1}. In the general case, one can consider instead [ a ] 1 / ( a 1 + ⋯ + a n ) {\displaystyle [a]^{1/(a_{1}+\cdots +a_{n})}} ![{\displaystyle [a]^{1/(a{1}+\cdots +a_{n})}}](https://wikimedia.org/api/rest_v1/media/math/render/svg/8cc4b2046e4bdc2f1f4afe0b91b05dcf8dadcac7), which is called a Muirhead mean.[1]

Examples

Doubly stochastic matrices

[edit]

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.

Muirhead's inequality states that [_a_] ≤ [_b_] for all x such that x i > 0 for every i ∈ { 1, ..., n } 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

[edit]

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

a 1 ≥ a 2 ≥ ⋯ ≥ a n {\displaystyle a_{1}\geq a_{2}\geq \cdots \geq a_{n}} {\displaystyle a_{1}\geq a_{2}\geq \cdots \geq a_{n}}

b 1 ≥ b 2 ≥ ⋯ ≥ b n . {\displaystyle b_{1}\geq b_{2}\geq \cdots \geq b_{n}.} {\displaystyle 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 ≤ b 1 a 1 + a 2 ≤ b 1 + b 2 a 1 + a 2 + a 3 ≤ b 1 + b 2 + b 3 ⋮ a 1 + ⋯ + a n − 1 ≤ b 1 + ⋯ + b n − 1 a 1 + ⋯ + a n = b 1 + ⋯ + b n . {\displaystyle {\begin{aligned}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}.\end{aligned}}} {\displaystyle {\begin{aligned}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}.\end{aligned}}}

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

The sequence b 1 , … , b n {\displaystyle b_{1},\ldots ,b_{n}} {\displaystyle b_{1},\ldots ,b_{n}} is said to majorize the sequence a 1 , … , a n {\displaystyle a_{1},\ldots ,a_{n}} {\displaystyle a_{1},\ldots ,a_{n}}.

Symmetric sum notation

[edit]

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 ( α 1 , … , α n {\displaystyle \alpha _{1},\ldots ,\alpha _{n}} {\displaystyle \alpha _{1},\ldots ,\alpha _{n}}) majorizes the other one.

∑ sym x 1 α 1 ⋯ x n α n {\displaystyle \sum _{\text{sym}}x_{1}^{\alpha _{1}}\cdots x_{n}^{\alpha _{n}}} {\displaystyle \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:

∑ 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 {\displaystyle {\begin{aligned}\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}\end{aligned}}} {\displaystyle {\begin{aligned}\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}\end{aligned}}}

Arithmetic-geometric mean inequality

[edit]

Let

a G = ( 1 n , … , 1 n ) {\displaystyle a_{G}=\left({\frac {1}{n}},\ldots ,{\frac {1}{n}}\right)} {\displaystyle a_{G}=\left({\frac {1}{n}},\ldots ,{\frac {1}{n}}\right)}

and

a A = ( 1 , 0 , 0 , … , 0 ) . {\displaystyle a_{A}=(1,0,0,\ldots ,0).} {\displaystyle a_{A}=(1,0,0,\ldots ,0).}

We have

a A 1 = 1 > a G 1 = 1 n , a A 1 + a A 2 = 1 > a G 1 + a G 2 = 2 n , ⋮ a A 1 + ⋯ + a A n = a G 1 + ⋯ + a G n = 1. {\displaystyle {\begin{aligned}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.\end{aligned}}} {\displaystyle {\begin{aligned}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.\end{aligned}}}

Then

[_aA_] ≥ [_aG_],

which is

1 n ! ( x 1 1 ⋅ x 2 0 ⋯ x n 0 + ⋯ + x 1 0 ⋯ x n 1 ) ( n − 1 ) ! ≥ 1 n ! ( x 1 ⋅ ⋯ ⋅ x n ) 1 / n n ! {\displaystyle {\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!} {\displaystyle {\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.

We seek to prove that _x_2 + y_2 ≥ 2_xy by using bunching (Muirhead's inequality). We transform it in the symmetric-sum notation:

∑ s y m x 2 y 0 ≥ ∑ s y m x 1 y 1 . {\displaystyle \sum _{\mathrm {sym} }x^{2}y^{0}\geq \sum _{\mathrm {sym} }x^{1}y^{1}.} {\displaystyle \sum _{\mathrm {sym} }x^{2}y^{0}\geq \sum _{\mathrm {sym} }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 ≥ 3 x y z {\displaystyle x^{3}+y^{3}+z^{3}\geq 3xyz} {\displaystyle x^{3}+y^{3}+z^{3}\geq 3xyz}

by writing it using the symmetric-sum notation as

∑ s y m x 3 y 0 z 0 ≥ ∑ s y m x 1 y 1 z 1 , {\displaystyle \sum _{\mathrm {sym} }x^{3}y^{0}z^{0}\geq \sum _{\mathrm {sym} }x^{1}y^{1}z^{1},} {\displaystyle \sum _{\mathrm {sym} }x^{3}y^{0}z^{0}\geq \sum _{\mathrm {sym} }x^{1}y^{1}z^{1},}

which is the same as

2 x 3 + 2 y 3 + 2 z 3 ≥ 6 x y z . {\displaystyle 2x^{3}+2y^{3}+2z^{3}\geq 6xyz.} {\displaystyle 2x^{3}+2y^{3}+2z^{3}\geq 6xyz.}

Since the sequence (3, 0, 0) majorizes the sequence (1, 1, 1), 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