§ Muirhead's inequality
We denote by the sum ov evaluated over all
For example,we have:
- .This is equal to .
- In general, ( zeroes) is which is the AM.
- Also, .
- In general, is the GM .
Let be two non-decreasing sequences: ,
and . We will say that is majorized by
(written as ) when we have that:
It is clear that this is a partial order. The below figure shows majorization
in terms of partitions. For two sequences , define to be their "integral"
(partial sums) and to be their "derivatives" (finite differences).
Then the condition that states that is upper bounded by ,
and that are concave functions.
The other lens of viewing majorization is to think of a number as some sort
of fixed length , and we are allowed to make some progress to reach the goal
() as long as we progress less at each each timestep ().
In this viewpoint, the majorization condition asserts that is that
will always be ahead of/not fall behind .
- , .
- for .
§ Majorization and step
We can show that if , then we can get from to
in a finite number of discrete steps, that "borrow" from higherlocations in
and "give" to lower locations. Formally, define a step operator where
That is, this borrows a single value from and gives it to . We can see
For a given , we can find a sequence of step operations
such that we transform into ; That is, it is possible
to "single-step" the translation from to .
§ Muirhead's theorem statement
for non negative numbers , we have:
Expanding it out, this means that: