Polynomial notation (1 Viewer)

[largarithmic]

Nope, I'm not even sure how it is proven. Its just a useful sledgehammer to know.
What is this geometric interpretation?

The cool geometric thing is this, and this is the only way I know to prove muirhead. In three variables you can think of each sequence (x1,x2,x3) which has sum say k as a barycentric coordinate, determining a point within an equilateral triangle of "weight" k. If you haven't come across this before, consider k = 4. The triangle would look something like:

(4,0,0)
(3,1,0) (3,0,1)
(2,2,0) (2,1,1) (2,0,2)
(1,3,0) (1,2,1) (1,1,2) (1,0,3)
(0,4,0) (0,3,1) (0,2,2) (0,1,3) (0,0,4)

essentially the three coordinates give the distance from the point to each of the sides; the sum of those distances is constant in an equilateral triangle and the individual coordinates determine a unique point.

Anyway then one sequence 'majorises' another if the polygon formed by the permutations of the coordinates formed by the major sequence fully encloses the polygon formed by the coordinates of the other one. So you can see directly that (3,1,0) majorises (2,2,0) and (2,1,1): (3,1,0) forms a sort of hexagon
(4,0,0)
(3,1,0) (3,0,1)
(2,2,0) (2,1,1) (2,0,2)
(1,3,0) (1,2,1) (1,1,2) (1,0,3)
(0,4,0) (0,3,1) (0,2,2) (0,1,3) (0,0,4)

whereas both (2,2,0) and (2,1,1) form triangles that are enclosed by it. This obviously generalises to values of k much bigger than 4, and to higher numbers of variables as well - you just need to add in other dimensions! (so a tetrahedron is needed for the 4-variable muirhead, for instance).

The proof that this is equivalent to the standard definition of majorisation isn't that hard either; the actual definition of majorisation is something like: "sequence S majorises sequence T, if you perform the following move a finite number of times on S you can reach T, the move being: select two elements a and b of S where a > b, and replace them with a-k, b+k where k <= a-b/2". Its not too hard to see this "pick two elements and move them closer together" is equivalent to the geometric interpretation, but its pretty tricky to make it equivalent to the standard definition on wikipedia. You basically need to properly define the process that sends S to T rigorously, and its a bit annoying but I've done it before and can't remember. (EDIT: after thinking about it I worked out how to do it, if youre interested Ill post it later, and Im 100% sure its different to how I worked it out about a year ago so ^^). That makes the geometric definition "rigorous": since the "move" of picking two things and moving them closer together only sends the polygon of S to polygons enclosed in S (not hard to see: the elements of S come in pairs e.g. the (1,0) subpairs of the (3,1,0) and in the polygon these pairs come in duos e.g. (1,3,0) and (0,3,1) that form sides of the polygon; the 'move' makes each of these sides shorter and thus stays within the convex hull of the original). This operation can then be done in reverse to send T to S, which makes it clear that if the geometric/combinatorial definition is true, then the algebraic one is as well.

Now to prove muirheads, you can actually just do this. Suppose you have sequences S (s1,s2,...,sn) and T (t1,t2,...,tn) where S majorises T; and variables (x1,x2,...,xn). It is sufficient to prove that the single term x1^t1 x2^t2... xn^tn is smaller than some weighted average of the symmetric S-sum (with equality reached in this smaller sub-inequality if x1=x2=...=xn): the reason is, if you formed that inequality and took the symmetric sum of both sides of the inequality, the 'bigger' side must be symmetric in all variables and thus the coefficient of each permutation of x1 x2 ... xn must be the same, and this in turn has to be 1 because you need to get equality if x1=x2=...=xn.

So its sufficient to prove a single term of the smaller side is less than a weighted sum of the right hand side. Now just do this: pick a single term of the smaller side. then pick all the terms of the bigger side, and think about it geometrically. That single term corresponds to one point in the smaller polygon; all the bigger sums correspond to another polygon. Now geometrically find the weighted mean of the bigger side that corresponds to the smaller side - you know that geometrically you can represent every point inside a polygon as a barycentric coordinate in each of the vertices, so you're done because this gives you the weighted mean you need (nb "polygon" there refers to a hyper-polyhedron, in the case when there are more than 3 variables) ^^ If you're not convinced by barycentric coordnates though, heres something cool that will:

(NB I realised my proof as contained in hayabusaboston's post is false because it only works in 2D. heres a nice way to do it though)

We induct on the statement, "in n-dimensional space, any point inside the convex hull of a finite set of vectors S can be written as the weighted mean of vectors from that set". Its clearly true for n = 1, since this is just ratio division (and can be proven with simultaneous eqns / whatever). So suppose its true for some n. Then consider n+1 dimensional space with a set of points/vectors S and a vector P within S's convex hull. Now the convex hull of S is an n+1 dimension hyper-polyhedron, with each of its "sides/faces" being n-dimensional co-hyperplanar, if that makes sense. Now if P lies on a side, then P lies on an n-dimensional hyperplane of that side, so by the inductive hypothesis P can be expressed as a weighted mean of this "side" and thus S. Now if P does not, pick some arbitrary A in S on the convex hull, and extend AP to meet the convex hull again at a point X. X must lie on a "side" since it is on the convex hull and thus hyperpolyhedron, so by inductive hypothesis X can be expressed as a weighted mean of S; then since A,P,X are collinear we can perform ratio division to express P as a weighted mean of A and X and thus a weighted mean of the whole set S. This completes the induction, and then proves muirheads.

 

[hayabusaboston]

The cool geometric thing is this, and this is the only way I know to prove muirhead. In three variables you can think of each sequence (x1,x2,x3) which has sum say k as a barycentric coordinate, determining a point within an equilateral triangle of "weight" k. If you haven't come across this before, consider k = 4. The triangle would look something like:

(4,0,0)
(3,1,0) (3,0,1)
(2,2,0) (2,1,1) (2,0,2)
(1,3,0) (1,2,1) (1,1,2) (1,0,3)
(0,4,0) (0,3,1) (0,2,2) (0,1,3) (0,0,4)

essentially the three coordinates give the distance from the point to each of the sides; the sum of those distances is constant in an equilateral triangle and the individual coordinates determine a unique point.

Anyway then one sequence 'majorises' another if the polygon formed by the permutations of the coordinates formed by the major sequence fully encloses the polygon formed by the coordinates of the other one. So you can see directly that (3,1,0) majorises (2,2,0) and (2,1,1): (3,1,0) forms a sort of hexagon
(4,0,0)
(3,1,0) (3,0,1)
(2,2,0) (2,1,1) (2,0,2)
(1,3,0) (1,2,1) (1,1,2) (1,0,3)
(0,4,0) (0,3,1) (0,2,2) (0,1,3) (0,0,4)

whereas both (2,2,0) and (2,1,1) form triangles that are enclosed by it. This obviously generalises to values of k much bigger than 4, and to higher numbers of variables as well - you just need to add in other dimensions! (so a tetrahedron is needed for the 4-variable muirhead, for instance).

The proof that this is equivalent to the standard definition of majorisation isn't that hard either; the actual definition of majorisation is something like: "sequence S majorises sequence T, if you perform the following move a finite number of times on S you can reach T, the move being: select two elements a and b of S where a > b, and replace them with a-k, b+k where k <= a-b/2". Its not too hard to see this "pick two elements and move them closer together" is equivalent to the geometric interpretation, but its pretty tricky to make it equivalent to the standard definition on wikipedia. You basically need to properly define the process that sends S to T rigorously, and its a bit annoying but I've done it before. That makes the geometric definition "rigorous": since the "move" of picking two things and moving them closer together only sends the polygon of S to polygons enclosed in S (not hard to see: the elements of S come in pairs e.g. the (1,0) subpairs of the (3,1,0) and in the polygon these pairs come in duos e.g. (1,3,0) and (0,3,1) that form sides of the polygon; the 'move' makes each of these sides shorter and thus stays within the convex hull of the original). This operation can then be done in reverse to send T to S, which makes it clear that if the geometric/combinatorial definition is true, then the algebraic one is as well.

Now to prove muirheads, you can actually just do this. Suppose you have sequences S (s1,s2,...,sn) and T (t1,t2,...,tn) where S majorises T; and variables (x1,x2,...,xn). It is sufficient to prove that the single term x1^t1 x2^t2... xn^tn is smaller than some weighted average of the symmetric S-sum (with equality reached in this smaller sub-inequality if x1=x2=...=xn): the reason is, if you formed that inequality and took the symmetric sum of both sides of the inequality, the 'bigger' side must be symmetric in all variables and thus the coefficient of each permutation of x1 x2 ... xn must be the same, and this in turn has to be 1 because you need to get equality if x1=x2=...=xn.

So its sufficient to prove a single term of the smaller side is less than a weighted sum of the right hand side. Now just do this: pick a single term of the smaller side. then pick all the terms of the bigger side, and think about it geometrically. That single term corresponds to one point in the smaller polygon; all the bigger sums correspond to another polygon. Now geometrically find the weighted mean of the bigger side that corresponds to the smaller side - you know that geometrically you can represent every point inside a polygon as a barycentric coordinate in each of the vertices, so you're done because this gives you the weighted mean you need ^^ If you're not convinced by barycentric coordnates though, heres something cool that will:

you pick your single term (call it A) and then pick any vertex of the bigger polygon, call this B. Then extend BA: since A is inside the polygon, BA must intersect the polygon's convex hull a second time. If it does this at another vertex C, then as B,A,C are collinear then you can perform ratio division (HSC maths!) to write A as a weighted mean of B,C (in particular if A is actually on a side of the bigger polygon, pick B as an endpoint of that side). If BA intersects the polygon again at a side not on endpoint though, let that side be CD and let BA intersect CD at X. Then perform a ratio division to get X as a weighted mean fo C and D, and then again on BX to get A as a weighted mean of B and X and thus A as a weighted mean of B,C,D. So you're done then right, coz you can write each term of the smaller sum as a weighted sum of the parts of the bigger sum.

you are a really hardcore maths guy amigo