Muirhead's inequality

Muirhead's 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.

Contents

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. (When n = 2, this is the Heinz mean.)

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

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 (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:

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.

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_\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:


\begin{align}
\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{align}

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

[aA] ≥ [aG]

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 x2 + y2 ≥ 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


Wikimedia Foundation. 2010.

Игры ⚽ Поможем написать курсовую

Look at other dictionaries:

  • Muirhead (disambiguation) — Muirhead is a Scottish place and a surname of Scottish origin, and may refer to: Places Muirhead a village near Glasgow, Scotland Muirhead, Angus, a village near Dundee, Scotland Muirhead, Northern Territory, a suburb of Darwin, Australia 7818… …   Wikipedia

  • Inequality of arithmetic and geometric means — 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… …   Wikipedia

  • MacLaurin's inequality — In mathematics, MacLaurin s inequality, named after Colin Maclaurin, is a refinement of the inequality of arithmetic and geometric means. Let a 1, a 2, ..., a n be positive real numbers, and for k = 1, 2, ..., n define the averages S k as follows …   Wikipedia

  • List of inequalities — This page lists Wikipedia articles about named mathematical inequalities. Inequalities in pure mathematics =Analysis= * Askey–Gasper inequality * Bernoulli s inequality * Bernstein s inequality (mathematical analysis) * Bessel s inequality *… …   Wikipedia

  • List of mathematics articles (M) — NOTOC M M estimator M group M matrix M separation M set M. C. Escher s legacy M. Riesz extension theorem M/M/1 model Maass wave form Mac Lane s planarity criterion Macaulay brackets Macbeath surface MacCormack method Macdonald polynomial Machin… …   Wikipedia

  • Arithmetic mean — In mathematics and statistics, the arithmetic mean, often referred to as simply the mean or average when the context is clear, is a method to derive the central tendency of a sample space. The term arithmetic mean is preferred in mathematics and… …   Wikipedia

  • Geometric mean — The geometric mean, in mathematics, is a type of mean or average, which indicates the central tendency or typical value of a set of numbers. It is similar to the arithmetic mean, which is what most people think of with the word average, except… …   Wikipedia

  • Heinz mean — The Heinz mean of two non negative real numbers A and B was defined by Bhatia [R. Bhatia, Interpolating the arithmetic geometric mean inequality and its operator version, Lin. Alg. Appl., Vol. 413, p. 355 363 (2006)] as: :H x(A, B) = frac{A^x… …   Wikipedia

  • Stochastic matrix — For a matrix whose elements are stochastic, see Random matrix In mathematics, a stochastic matrix (also termed probability matrix, transition matrix, substitution matrix, or Markov matrix) is a matrix used to describe the transitions of a Markov… …   Wikipedia

  • Bunching — can refer to:*Bunching (mathematics). See Muirhead s inequality. *Bunching (animals), the practice of stealing pets for laboratories. See Laboratory animal sources …   Wikipedia

Share the article and excerpts

Direct link
Do a right-click on the link above
and select “Copy Link”