Difference between revisions of "Muirhead's Inequality"
Franklin.vp (talk | contribs) (→Example revisited: Changing pmatrix to bmatrix such that column 2-vectors do not look like binomial coefficients) |
Franklin.vp (talk | contribs) (→Proof: Some more steps in the crucial part to make it easier to follow) |
||
Line 66: | Line 66: | ||
<cmath> | <cmath> | ||
\begin{align*} | \begin{align*} | ||
− | [p]&=\sum_{i=1}^{n!}c_i[p]\\ | + | [p]&=1\cdot [p]\\ |
+ | &=\left(\sum_{i=1}^{n!}c_i\right)[p]\\ | ||
+ | &=\sum_{i=1}^{n!}c_i[p]\\ | ||
+ | &=\sum_{i=1}^{n!}c_i[P_ip]\\ | ||
&\geq\left[\sum_{i=1}^{n!}c_iP_ip\right]\\ | &\geq\left[\sum_{i=1}^{n!}c_iP_ip\right]\\ | ||
&=[Dp]\\ | &=[Dp]\\ |
Revision as of 00:25, 6 July 2023
Muirhead's Inequality states that if a sequence majorizes a sequence
, then given a set of positive reals
:
Example
The inequality is easier to understand given an example. Since the sequence majorizes
(as
), Muirhead's inequality states that for any positive
,
Usage on Olympiad Problems
A common bruteforce technique with inequalities is to clear denominators, multiply everything out, and apply Muirhead's or Schur's. However, it is worth noting that any inequality that can be proved directly with Muirhead can also be proved using the Arithmetic Mean-Geometric Mean inequality. In fact, IMO gold medalist Thomas Mildorf says it is unwise to use Muirhead in an Olympiad solution; one should use an application of AM-GM instead. Thus, it is suggested that Muirhead be used only to verify that an inequality can be proved with AM-GM before demonstrating the full AM-GM proof.
Example revisited
To understand the proof further below, let's also prove the inequality from the (weighted) AM-GM inequality.
where the step with the inequality consists in applying the weighted AM-GM inequality to each expression in parentheses.
The coefficients and
and the use grouping of terms according to the permutations
and
come from the following arithmetic facts.
Note that , where the matrix
. This matrix has non-negative entries and all its rows and columns add up to
. Such matrices are called doubly stochastic matrices. We can write
. Matrices like
and
, with exactly one
in each row and each column and
everywhere else, are called permutation matrices. Observe how
and
gives us all permutations of
.
So, we can write
A single inequality that follows from Muirhead's inequality could be proven from the AM-GM inequality in multiple ways. Another way is
Adding these,
Multiplying both sides by
(as both
and
are positive),
as desired.
Proof
Given , let's write
Let's denote that
majorizes
as
.
These notation is useful in the context of Muirhead's inequality. In particular the theorem can be stated as
implies
.
Even though and
are written above as
-tuples, it will be convenient to think of them as column vectors, vertical.
The first goal of the proof is to show that there is a doubly stochastic matrix such that
. Then Birkhoff-von Neuman theorem tells us that there are
such that
and
, where
are permutation matrices.
Note that once we have such an expression for , then
where the step with the inequality (like in the example above) consists of applying the weighted AM-GM inequality grouping the terms from each element of the sum
, corresponding to each permutation of the variables
. Remember that the brackets
are representing also a summation
.
Before showing how to produce the matrix , note that knowing the computational aspect of Birkhoff-von Newmann theorem is useful, since it gives us an algorithm to compute the
.
To produce the matrix we construct a sequence
of
-tuples (or rather column vectors), such that
, each
has at least one more component equal to a component of
than its predecessor
, and
, for some doubly stochastic matrix
. Note that then we can take
to get
and since products of doubly stochastic matrices is a doubly stochastic matrix, we get what we wanted.
In the case there is nothing to prove. Even Muirhead's inequality would be an equality in this case.
So, assume that
and
.
Define
Define the matrix with entries
all other diagonal entries
, for
are equal to
and the remaining entries equal to
.
It is straightforward from the definition to verify that this matrix is doubly stochastic, satisfies , all components of
before position
and after position
are equal to those of
, but at least one of the components at position
or
became equal to the corresponding component in
. By repeating this construction with
etc. we get the matrices
.