Real functions Classical inequalities Theorem

Rearrangement inequality

Statement

Let $x_1 \le x_2 \le \dots \le x_n$ and $y_1 \le y_2 \le \dots \le y_n$ be real numbers, and let $\sigma$ be a permutation of $\set{1, \dots, n}$ . Then $\sum_{i=1}^{n} x_i y_{n+1-i} \le \sum_{i=1}^{n} x_i y_{\sigma(i)} \le \sum_{i=1}^{n} x_i y_i.$

Remarks

Proof idea: suppose $i < j$ but $y_{\sigma(i)} > y_{\sigma(j)}$ . Swapping the two values changes the sum by $(x_j - x_i)(y_{\sigma(i)} - y_{\sigma(j)}) \ge 0$ . Repeated swaps sort $\sigma$ into the identity without decreasing the sum, which gives the upper bound. The lower bound follows by applying the upper bound to $-y_n \le \dots \le -y_1$ .

Example: with $x = (1, 2, 3)$ and $y = (4, 5, 6)$ , the sums range from $1 \cdot 6 + 2 \cdot 5 + 3 \cdot 4 = 28$ to $1 \cdot 4 + 2 \cdot 5 + 3 \cdot 6 = 32$ .

Mathlib states a form as Monovary.sum_smul_comp_perm_le_sum_smul.

Going deeper

For a student

The rearrangement inequality gives quick proofs of several classical inequalities. Averaging it over the cyclic shifts of $y$ gives Chebyshev's sum inequality. Applied to suitable sequences it also gives the AM–GM inequality and the Cauchy–Schwarz inequality in special cases.

Reading path

To understand this page from the ground up, read these 2 pages in order. The foundations come first.

Show the path as a graph

Each page uses the pages above it. The colour of the bar on a box shows how strong the evidence is, and the box also gives it as text. The list has the same pages.

no evidence level

Permutation definition
Rearrangement inequality statement

Tag	`6E9TAF8HCY`
URI	`m2://6E9TAF8HCY`
Kind	statement, theorem
Writing	W0 stub
MSC	26D15
Status	This copy of the site has no build data. Run `m2 status 6E9TAF8HCY`.
About	Permutation
Uses	Permutation
Same as	Wikidata Q1149189 Wikipedia Rearrangement inequality
Changed	2 November 2026