§ Muirhead's inequality

We denote by !F(x[1],,x[n])\sum_! F(x[1], \dots, x[n]) the sum ov FF evaluated over all permutations. Formally:
!F(x[1],,x[n])σSnF(x[σ[1]],,x[σ[n]]) \sum_! F(x[1], \dots, x[n]) \equiv \sum_{\sigma \in S_n} F(x[\sigma[1]], \dots, x[\sigma[n]])
We write
[a[1],a[n]]1/n!!x1a[1]x[n]a[n]=σSnjx[σ[j]]a[j] [a[1], \dots a[n]] \equiv 1/n! \sum_! x_1^{a[1]} \dots x[n]^{a[n]} = \sum_{\sigma \in S_n} \prod_{j} x[\sigma[j]]^{a[j]}
For example,we have:
  • [1,1]=1/2!(xy+yx)=xy[1, 1] = 1/2! (xy + yx) = xy
  • [1,1,1]=xyz[1, 1, 1] = xyz
  • [2,1,0]=1/3!(x2y+x2z+y2z+y2x+z2x+z2y)[2, 1, 0] = 1/3! (x^2y + x^2z + y^2z + y^2x + z^2x + z^2 y)
  • [1,0,0]=1/3!(x[1,0,0]+x[1,0,0]+x[0,1,0]+x[0,1,0]+x[0,0,1]+x[0,0,1])[1, 0, 0] = 1/3! (x^{[1, 0, 0']} + x^{[1, 0', 0]} + x^{[0, 1, 0']} + x^{[0', 1, 0]} + x^{[0, 0', 1]} + x^{[0', 0, 1]}). This is equal to 2!(x+y+z)/3!=(x+y+z)/32!(x + y + z)/3! = (x + y + z)/3.
  • In general, [1,0,0,0,,0][1, 0, 0, 0, \dots, 0] ( nn zeroes) is (n1)!/n!(ixi)(n-1)!/n!(\sum_i x_i) which is the AM.
  • Also, [1/2,1/2]=1/2!(x1/2y1/2+y1/2x1/2)=xy[1/2, 1/2] = 1/2!(x^{1/2}y^{1/2} + y^{1/2}x^{1/2}) = \sqrt{xy}.
  • In general, [1/n,1/n,,1/n][1/n, 1/n, \dots, 1/n] is the GM nx[1]x[2]x[n]\sqrt{n}{x[1] x[2] \dots x[n]}.

§ Majorization

Let (a),(b)Rn(a), (b) \in \mathbb R^n be two non-decreasing sequences: a[1]a[2]a[n]a[1] \geq a[2] \dots \geq a[n], and b[1]b[2]b[n]b[1] \geq b[2] \dots \geq b[n]. We will say that (b)(b) is majorized by (a)(a) (written as (b)(a)(b) \prec (a)) when we have that:
  1. a[1]a[2]a[n]a[1] \geq a[2] \geq \dots a[n], b[1]b[2]b[n]b[1] \geq b[2] \geq \dots b[n].
  2. ib[i]=ia[i]\sum_i b[i] = \sum_i a[i].
  3. i=1ub[i]i=1ua[i]\sum_{i=1}^u b[i] \leq \sum_{i=1}^u a[i] for 1in1 \leq i \leq n.
It is clear that this is a partial order. The below figure shows majorization in terms of partitions. For two sequences f,gf, g, define FF to be their "integral" (partial sums) and f,gf', g' to be their "derivatives" (finite differences). Then the condition that fgf \prec g states that FF is upper bounded by GG, and that F,GF, G are concave functions. The other lens of viewing majorization is to think of a number as some sort of fixed length ll, and we are allowed to make some progress to reach the goal ( f(x)>0f(x) > 0) as long as we progress less at each each timestep ( f(x)<0f''(x) < 0). In this viewpoint, the majorization condition asserts that fgf \prec g is that gg will always be ahead of/not fall behind ff.

§ Majorization and step

We can show that if (b)(a)(b) \prec (a) , then we can get from (b)(b) to (a)(a) in a finite number of discrete steps, that "borrow" from higherlocations in bb and "give" to lower locations. Formally, define a step operator S(l,r)S(l, r) where l<rl < r such that:
S(l,r)(b)[k]={b[l]+1k=lb[r]1k=rb[k]otherwise S(l, r)(b)[k] = \begin{cases} b[l]+1 & k = l \\ b[r]-1 & k = r \\ b[k] & \texttt{otherwise} \end{cases}
That is, this borrows a single value from b[j]b[j] and gives it to b[i]b[i]. We can see that (b)S(l,r)(b)(b) \prec S(l, r)(b). For a given (b)(a)(b) \prec (a), we can find a sequence of step operations S(l[i],r[i])S(l[i], r[i]) such that we transform (b)(b) into (a)(a); That is, it is possible to "single-step" the translation from (b)(b) to (a)(a).

§ Muirhead's theorem statement

for non negative numbers x[]x[], we have:
[b][a]    (b)(a)[b] \leq [a] \iff (b) \prec (a)
Expanding it out, this means that:
1/n!!x[b]1/n!!x[a]    (b)(a)!x[b]!x[a]    (b)(a) 1/n! \sum_! x^{[b]} \leq 1/n! \sum_! x^{[a]} \iff (b) \prec (a) \\ \sum_! x^{[b]} \leq \sum_! x^{[a]} \iff (b) \prec (a) \\