Exercise 1019Algebra › InequalitiesL1Added 3 Nov 2026

The rearrangement inequality

#rearrangement#inequality#sequences

Statement

Let $a_1\le a_2\le\cdots\le a_n$ and $b_1\le b_2\le\cdots\le b_n$ be two increasing sequences of real numbers. Show that
$\sum_{i=1}^n a_i b_i\ge\sum_{i=1}^n a_i b_{\sigma(i)}$
for any permutation $\sigma$ .

Hint

Use the identity $\sum a_ib_i-\sum a_ib_{\sigma(i)}=\sum_{i<j}(a_j-a_i)(b_j-b_{\sigma(j)})$ type, or prove by exchange argument: swapping two out-of-order elements increases the sum.

Show solutionHide solution

Solution

Exchange argument. Suppose $\sigma$ is not the identity. Then there exist $i<j$ with $\sigma(i)>\sigma(j)$ , i.e. the pairing is "inverted". Consider swapping the values assigned to $i$ and $j$ :
$a_ib_{\sigma(i)}+a_jb_{\sigma(j)}\quad\to\quad a_ib_{\sigma(j)}+a_jb_{\sigma(i)}.$
The difference is
$(a_ib_{\sigma(j)}+a_jb_{\sigma(i)})-(a_ib_{\sigma(i)}+a_jb_{\sigma(j)})=(a_j-a_i)(b_{\sigma(i)}-b_{\sigma(j)})\ge0,$
since $a_j\ge a_i$ and $b_{\sigma(i)}\ge b_{\sigma(j)}$ (because $\sigma(i)>\sigma(j)$ and $b$ is increasing).

Iteration. Repeatedly swapping out-of-order pairs strictly increases the sum until it reaches the pairing $\sigma=\mathrm{id}$ . Hence the maximum is attained at the identity, and
$\sum a_ib_i\ge\sum a_ib_{\sigma(i)}.$

Remark. Similarly, the minimum is attained by the "oppositely ordered" pairing $a_ib_{n+1-i}$ .

The rearrangement inequality

Statement

Solution

More problems in Inequalities