A proof of Muirhead’s Inequality

I’ve been reading Thomas Mildorf’s Olympiad Inequalities, and trying to prove the 12 Theorems stated at the beginning. I’m recording my proof of Muirhead’s Inequality below. Although it is probably known to people working in this area, I could not find it on the internet.

Muirhead’s Inequality states the following: if the sequence a_1,\dots,a_n majorizes the sequence b_1,\dots,b_n, then for nonnegative numbers x_1,\dots,x_n, we have the following inequality

\sum\limits_{\text{sym}} x_1^{a_1}x_2^{a_2}\dots x_n^{a_n}\geq \sum\limits_{\text{sym}}x_1^{b_1}x_2^{b_2}\dots x_n^{b_n}

We will derive it as an easy consequence of the fact that for a convex function f, if the sequence \{a_i\} majorizes the sequence \{b_j\}, then f(a_1)+\dots f(a_n)\geq f(b_1)+\dots+f(b_n). This is theorem 9 in Mildorf’s document (the Majorization Theorem).

We will prove the Muirhead Inequality by induction on the number of x_i‘s. For just one such x_i, this is true by the Majorization Inequality. Now assume that it is true for (n-1) number of x_i‘s. Then the statement of Muirhead’s Inequality is equivalent to the statement

(x_1^{a_1}+x_1^{a_2}+\dots x_1^{a_n})(x_2^{a_1}+x_2^{a_2}+\dots x_2^{a_n})\dots (x_n^{a_1}+x_n^{a_2}+\dots x_n^{a_n})\geq (x_1^{b_1}+x_1^{b_2}+\dots x_1^{b_n})(x_2^{b_1}+x_2^{b_2}+\dots x_2^{b_n})\dots (x_n^{b_1}+x_n^{b_2}+\dots x_n^{b_n})

The above is true because f_i(y)=x_i^y is a convex function, as it is an exponential function. Hence, f_i(a_1)+\dots f_i(a_n)\geq f_i(a_1)+\dots+f_i(a_n). Therefore, x_i^{a_1}+\dots x_i^{a_n}\geq x_i^{b_1}+\dots x_i^{b_n}.

It follows that

(x_1^{a_1}+x_1^{a_2}+\dots x_1^{a_n})(x_2^{a_1}+x_2^{a_2}+\dots x_2^{a_n})\dots (x_n^{a_1}+x_n^{a_2}+\dots x_n^{a_n})\geq (x_1^{b_1}+x_1^{b_2}+\dots x_1^{b_n})(x_2^{b_1}+x_2^{b_2}+\dots x_2^{b_n})\dots (x_n^{b_1}+x_n^{b_2}+\dots x_n^{b_n})

A note on the induction: Consider the base case, where we just have x_1. Then the inequality is equivalent to proving that

x_1^{a_1}+x_1^{a_2}+\dots+x_1^{a_n}\geq x_1^{b_1}+x_1^{b_2}+\dots+x_1^{b_n}, which is true by Muirhead inequality.

Now if we have two x_i‘s, say x_1 and x_2, then this is equivalent to the inequality (x_1^{a_1}+\dots+x_1^{a_n})(x_2^{a_1}+\dots+x_2^{a_n})\geq (x_1^{b_1}+\dots+x_1^{b_n})(x_2^{b_1}+\dots+x_2^{b_n}).

We get the above inequality + terms of the form (xy)^{a_1}+\dots+(xy)^{a_n}, which we know from the Majorization Inequality is \geq (xy)^{b_1}+\dots+(xy)^{b_n}

The induction will work similarly for higher numbers of x_i‘s.

Published by ayushkhaitan3437

Hello! My name is Ayush Khaitan, and I'm a graduate student in Mathematics.

Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out /  Change )

Google photo

You are commenting using your Google account. Log Out /  Change )

Twitter picture

You are commenting using your Twitter account. Log Out /  Change )

Facebook photo

You are commenting using your Facebook account. Log Out /  Change )

Connecting to %s

%d bloggers like this: