Rearrangement

Big times big beats big times small — sorted pairs maximize ∑ a_i b_ (i).

The idea

The rearrangement inequality says how to pair off two sorted lists so that the sum of the products is as large, or as small, as possible.

Theorem (Rearrangement inequality).

Let $a_1 \le a_2 \le \cdots \le a_n$ and $b_1 \le b_2 \le \cdots \le b_n$ be two sorted lists of reals. For every permutation $\sigma$, $\sum_{i=1}^{n} a_i b_{n+1-i} \;\le\; \sum_{i=1}^{n} a_i b_{\sigma(i)} \;\le\; \sum_{i=1}^{n} a_i b_i.$ If both lists are strictly increasing, the sorted pairing is the unique maximizer and the reversed pairing the unique minimizer.

Equality with any other pairing therefore requires repeated values in one of the lists.

The statement answers a matching question: pair each entry of one list with exactly one entry of the other, and add the products. Among the $n!$ possible pairings, the sum is largest when the lists are traversed in the same order, smallest when one is traversed backwards, and every other pairing lands between the two.

An optimization over $n!$ arrangements is therefore settled by sorting, and the answer depends only on the order of the entries. Many symmetric inequalities amount to the claim that one particular pairing of two lists is the best or worst available, and the rearrangement inequality proves every claim of that form at once.

Ways to work on it

• Walkthrough. Verify the rearrangement inequality on two small triples by comparing sorted, reversed, and mixed pairings.
• Proof. Prove the rearrangement inequality by an exchange argument: un-crossing one pair never decreases the sum.
• Practice. Compute max and min pairings for random sorted triples.
• Hardest. Use the rearrangement inequality to prove a classic cyclic inequality.

Not sure where to start? Take the ten-question placement test.