Rearrangement Inequality

Idea · Advanced

Algebra

Let

a_1\le a_2\le\cdots\le a_n

and

b_1\le b_2\le\cdots\le b_n

be two sequences of real numbers. For any permutation $b_{i_1},b_{i_2},\ldots,b_{i_n}$ of $b_1,b_2,\ldots,b_n$ ,

a_1b_n+a_2b_{n-1}+\cdots+a_nb_1\le a_1b_{i_1}+a_2b_{i_2}+\cdots+a_nb_{i_n}\le a_1b_1+a_2b_2+\cdots+a_nb_n

We first prove that pairing numbers in the same order gives the maximum sum.

Suppose

a_i\le a_j,\qquad b_p\le b_q.

Compare the two pairings:

a_ib_p+a_jb_q

and

a_ib_q+a_jb_p.

Their difference is

\begin{aligned}(a_ib_p+a_jb_q)-(a_ib_q+a_jb_p)&=(a_j-a_i)(b_q-b_p)\\&\ge0.\end{aligned}

Therefore,

a_ib_p+a_jb_q\ge a_ib_q+a_jb_p.

Pairing two numbers in the same order never gives a smaller sum than pairing them in the opposite order.

Starting with any permutation, we can repeatedly swap inverted pairs until the two sequences are paired in the same order. Each swap does not decrease the sum.

Uncrossing an inverted pairing in the proof of the Rearrangement Inequality

If two pairings are inverted, swapping their endpoints does not decrease the sum. Repeating this process eventually gives the maximum sum.

Hence,

a_1b_{i_1}+a_2b_{i_2}+\cdots+a_nb_{i_n}\le a_1b_1+a_2b_2+\cdots+a_nb_n.

For the minimum, note that

a_1\le a_2\le\cdots\le a_n,\qquad -b_n\le -b_{n-1}\le\cdots\le -b_1.

Applying the maximum case to the sequence $-b_1,-b_2,\ldots,-b_n$ gives

-a_1b_{i_1}-a_2b_{i_2}-\cdots-a_nb_{i_n}\le -\left(a_1b_n+a_2b_{n-1}+\cdots+a_nb_1\right).

Multiplying both sides by $-1$ reverses the inequality. Hence,

a_1b_n+a_2b_{n-1}+\cdots+a_nb_1\le a_1b_{i_1}+a_2b_{i_2}+\cdots+a_nb_{i_n}.

a_1\le a_2\le\cdots\le a_n,\qquad b_1\le b_2\le\cdots\le b_n,

then

\frac{a_1b_1+a_2b_2+\cdots+a_nb_n}{n}\ge\frac{a_1+a_2+\cdots+a_n}{n}\cdot\frac{b_1+b_2+\cdots+b_n}{n}\ge\frac{a_1b_n+a_2b_{n-1}+\cdots+a_nb_1}{n}.

\begin{aligned}a_1b_1+a_2b_2+\cdots+a_nb_n&\ge a_1b_1+a_2b_2+\cdots+a_nb_n\\&\ge a_1b_n+a_2b_{n-1}+\cdots+a_nb_1,\end{aligned}

\begin{aligned}a_1b_1+a_2b_2+\cdots+a_nb_n&\ge a_1b_2+a_2b_3+\cdots+a_nb_1\\&\ge a_1b_n+a_2b_{n-1}+\cdots+a_nb_1,\end{aligned}

\begin{aligned}a_1b_1+a_2b_2+\cdots+a_nb_n&\ge a_1b_3+a_2b_4+\cdots+a_nb_2\\&\ge a_1b_n+a_2b_{n-1}+\cdots+a_nb_1,\end{aligned}

⋮

\begin{aligned}a_1b_1+a_2b_2+\cdots+a_nb_n&\ge a_1b_n+a_2b_1+\cdots+a_nb_{n-1}\\&\ge a_1b_n+a_2b_{n-1}+\cdots+a_nb_1.\end{aligned}

Adding all of them gives

\begin{aligned}n(a_1b_1+a_2b_2+\cdots+a_nb_n)&\ge a_1(b_1+b_2+\cdots+b_n)+\cdots+a_n(b_1+b_2+\cdots+b_n)\\&\ge n(a_1b_n+a_2b_{n-1}+\cdots+a_nb_1).\end{aligned}

n(a_1b_1+a_2b_2+\cdots+a_nb_n)\ge(a_1+a_2+\cdots+a_n)(b_1+b_2+\cdots+b_n)\ge n(a_1b_n+a_2b_{n-1}+\cdots+a_nb_1).

Divide both sides by $n^2$ .

\frac{a_1b_1+a_2b_2+\cdots+a_nb_n}{n}\ge\frac{a_1+a_2+\cdots+a_n}{n}\cdot\frac{b_1+b_2+\cdots+b_n}{n}\ge\frac{a_1b_n+a_2b_{n-1}+\cdots+a_nb_1}{n}.