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