Your American History Reference Guide!
- Muirhead's inequality
HistoryMania Information Site on Muirhead's inequality American History American History Search        American History Browse welcome to our free resource site for all enthusiasts!

Muirhead's inequality

In mathematics, Muirhead's inequality generalizes the inequality of arithmetic and geometric means.

Contents
1 Two preliminary definitions

1.1 The "a-mean"
1.2 Doubly stochastic matrices

2 The inequality

2.1 Another equivalent condition

3 Reference

Two preliminary definitions

The "a-mean"

For any real vector

a=(a_1,\dots,a_n)

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.

Doubly stochastic matrices

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

Muirhead's inequality states that [a] ≤ [b] for all xi ≥ 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.

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_1
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.)

Reference

Combinatorial Theory by John N. Guidi, based on lectures given by Gian-Carlo Rota in 1998, MIT Copy Technology Center, 2002.

Last updated: 06-01-2005 20:25:12
The contents of this article are licensed from Wikipedia.org under the
GNU Free Documentation License. How to see transparent copy
Search | Browse | Contact | Legal info