Lemma › Guides › Muirhead's inequality: how to read it and when it applies
Guide

Muirhead's inequality: how to read it and when it applies

Muirhead's inequality compares two symmetric sums of monomials by looking only at their exponents. It works for symmetric, homogeneous inequalities in non-negative variables. You write down two exponent vectors, run a short test, and the inequality is settled.

The statement

For non-negative reals x1,…,xnx_1, \dots, x_n and a vector α=(α1,…,αn)\alpha = (\alpha_1, \dots, \alpha_n), write

∑symxα=∑σxσ(1)α1xσ(2)α2⋯xσ(n)αn,\sum_{\text{sym}} x^{\alpha} = \sum_{\sigma} x_{\sigma(1)}^{\alpha_1} x_{\sigma(2)}^{\alpha_2} \cdots x_{\sigma(n)}^{\alpha_n},

where the sum is over all n!n! permutations σ\sigma. With three variables, ∑syma2b\sum_{\text{sym}} a^2 b has six terms: a2b+a2c+b2a+b2c+c2a+c2ba^2b + a^2c + b^2a + b^2c + c^2a + c^2b. And ∑symabc\sum_{\text{sym}} abc is 6abc6abc.

Say that α\alpha majorizes β\beta when both are listed in decreasing order, they have the same sum, and every partial sum of α\alpha is at least the matching partial sum of β\beta:

α1≥β1,α1+α2≥β1+β2,…\alpha_1 \ge \beta_1,\quad \alpha_1 + \alpha_2 \ge \beta_1 + \beta_2,\quad \dots

Muirhead's inequality says that if α\alpha majorizes β\beta, then ∑symxα≥∑symxβ\sum_{\text{sym}} x^\alpha \ge \sum_{\text{sym}} x^\beta for all non-negative xix_i. For positive variables, equality needs all of them equal unless the two vectors are the same.

The test

Take two exponent vectors. Sort each from largest to smallest. Check the sums match. Then compare partial sums one by one. If every partial sum of the first is at least that of the second, you have the inequality.

For example, (3,0,0)(3,0,0) majorizes (2,1,0)(2,1,0), which majorizes (1,1,1)(1,1,1). That is a chain: 2∑a3≥∑syma2b≥6abc2\sum a^3 \ge \sum_{\text{sym}} a^2 b \ge 6abc. Both steps are Muirhead.

The proof idea

The whole thing rests on a two-variable step. If q≤s≤r≤pq \le s \le r \le p and p+q=r+sp + q = r + s, then

xpyq+xqyp−xrys−xsyr=(xy)q (xu−yu)(xv−yv),u=r−q,  v=s−q.x^p y^q + x^q y^p - x^r y^s - x^s y^r = (xy)^q\,(x^u - y^u)(x^v - y^v), \qquad u = r - q,\; v = s - q.

Both brackets have the same sign, so the product is non-negative. In words: pull two exponents apart while keeping their sum, and a symmetric sum goes up.

Any vector majorized by α\alpha can be reached from α\alpha by finitely many steps that bring two exponents closer together and keep their sum. Here is how one step acts inside the symmetric sum. Say the step changes the exponents p,qp, q into r,sr, s and leaves the others alone. Group the terms of ∑symxα\sum_{\text{sym}} x^\alpha by which variables carry the unchanged exponents. In one group, two variables x,yx, y carry pp and qq in some order, so the group contributes m (xpyq+xqyp)m\,(x^p y^q + x^q y^p), where m≥0m \ge 0 is the product of the other powers. The new sum has m (xrys+xsyr)m\,(x^r y^s + x^s y^r) in the same group, and by the identity above the first is at least the second. Add over the groups, and one step can only lower the total. That is the proof. A related idea sits behind smoothing, where you move two variables toward each other and watch the expression change monotonically.

The signals

Example: a classic

Prove (a+b)(b+c)(c+a)≥8abc(a+b)(b+c)(c+a) \ge 8abc for non-negative a,b,ca, b, c. This is the AM-GM warm-up in the archive.

Expand: (a+b)(b+c)(c+a)=∑syma2b+2abc(a+b)(b+c)(c+a) = \sum_{\text{sym}} a^2 b + 2abc. Then (2,1,0)(2,1,0) majorizes (1,1,1)(1,1,1), so ∑syma2b≥6abc\sum_{\text{sym}} a^2 b \ge 6abc. The total is at least 8abc8abc.

Check with numbers: at (1,2,3)(1,2,3) the product is 3⋅5⋅4=603 \cdot 5 \cdot 4 = 60, the symmetric sum is 4848, and 48+12=6048 + 12 = 60. Also 8abc=48≤608abc = 48 \le 60.

Example: after homogenising

Let a,b,c≥0a, b, c \ge 0 with a+b+c=3a + b + c = 3. Prove a3+b3+c3≥a2+b2+c2a^3 + b^3 + c^3 \ge a^2 + b^2 + c^2.

The two sides have different degrees, so replace the constraint by a multiplier. Since a+b+c=3a + b + c = 3, we can write the right side as 13(a2+b2+c2)(a+b+c)\tfrac13(a^2+b^2+c^2)(a+b+c). Then the claim is 3∑a3≥(∑a2)(∑a)3\sum a^3 \ge (\sum a^2)(\sum a). Expand the right side: ∑a3+∑syma2b\sum a^3 + \sum_{\text{sym}} a^2 b. So the claim becomes 2∑a3≥∑syma2b2\sum a^3 \ge \sum_{\text{sym}} a^2 b, which is Muirhead with (3,0,0)≻(2,1,0)(3,0,0) \succ (2,1,0).

Homogenising is a habit worth building. Any constraint like a+b+c=3a + b + c = 3 or abc=1abc = 1 is a tool for matching degrees.

Example: a quartic

Prove a4+b4+c4≥abc(a+b+c)a^4 + b^4 + c^4 \ge abc(a+b+c). On the left, ∑syma4=2(a4+b4+c4)\sum_{\text{sym}} a^4 = 2(a^4+b^4+c^4), because each fourth power comes from two permutations, the two that swap the other two variables. On the right, ∑syma2bc=2(a2bc+ab2c+abc2)=2abc(a+b+c)\sum_{\text{sym}} a^2bc = 2(a^2bc + ab^2c + abc^2) = 2abc(a+b+c) for the same reason. The vectors are (4,0,0)(4,0,0) and (2,1,1)(2,1,1), and the first majorizes the second: 4≥24 \ge 2, 4≥34 \ge 3, 4=44 = 4. So 2∑a4≥2abc(a+b+c)2\sum a^4 \ge 2abc(a+b+c), and dividing by 22 gives the claim.

Where it goes wrong

What to do with this

When you meet a symmetric inequality, expand it, write both sides as sums of monomials, and put the exponent vectors next to each other. If one majorizes the other you are done in a line. If neither does, the inequality is either false or needs a finer tool. The AM-GM and Cauchy-Schwarz page lists the ones to try next. The problem archive has more inequalities to practise on.

Related guides

Techniques in this guide

Competitions this guide helps with

Train it on Lemma

Every technique here is taught explicitly, in order. 128 lessons, 1237 curated problems and unlimited generated practice at six difficulties. Free to start, no card, and the paid plan opens with 3 free days.

Find your level