Proof by contradiction

The lower bound and the corresponding discussion of equality follow by applying the results for the upper bound to

$${\displaystyle -y_{n}\leq \cdots \leq -y_{1}.}$$

Therefore, it suffices to prove the upper bound in (1) and discuss when equality holds. Since there are only finitely many permutations of ${\displaystyle 1,\ldots ,n,}$ there exists at least one ${\displaystyle \sigma }$ for which the middle term in (1)

$${\displaystyle x_{1}y_{\sigma (1)}+\cdots +x_{n}y_{\sigma (n)}}$$

is maximal. In case there are several permutations with this property, let σ denote one with the highest number of integers ${\displaystyle i}$ from ${\displaystyle \{1,\ldots ,n\}}$ satisfying ${\displaystyle y_{i}=y_{\sigma (i)}.}$

We will now prove by contradiction, that ${\displaystyle \sigma }$ has to keep the order of ${\displaystyle y_{1},\ldots ,y_{n}}$ (then we are done with the upper bound in (1), because the identity has that property). Assume that there exists a ${\displaystyle j\in \{1,\ldots ,n-1\}}$ such that ${\displaystyle y_{i}=y_{\sigma (i)}}$ for all ${\displaystyle i\in \{1,\ldots ,j-1\}}$ and ${\displaystyle y_{j}\neq y_{\sigma (j)}.}$ Hence ${\displaystyle y_{j}<y_{\sigma (j)}}$ and there has to exist a ${\displaystyle k\in \{j+1,\ldots ,n\}}$ with ${\displaystyle y_{j}=y_{\sigma (k)}}$ to fill the gap. Therefore,

${\displaystyle x_{j}\leq x_{k}\qquad {\text{and}}\qquad y_{\sigma (k)}<y_{\sigma (j)},}$

(2)

which implies that

${\displaystyle 0\leq (x_{k}-x_{j})(y_{\sigma (j)}-y_{\sigma (k)}).}$

(3)

Expanding this product and rearranging gives

${\displaystyle x_{j}y_{\sigma (j)}+x_{k}y_{\sigma (k)}\leq x_{j}y_{\sigma (k)}+x_{k}y_{\sigma (j)}\,,}$

(4)

which is equivalent to (3). Hence the permutation

$${\displaystyle \tau (i):={\begin{cases}\sigma (i)&{\text{for }}i\in \{1,\ldots ,n\}\setminus \{j,k\},\\\sigma (k)&{\text{for }}i=j,\\\sigma (j)&{\text{for }}i=k,\end{cases}}}$$

which arises from ${\displaystyle \sigma }$ by exchanging the values ${\displaystyle \sigma (j)}$ and ${\displaystyle \sigma (k),}$ has at least one additional point which keeps the order compared to ${\displaystyle \sigma ,}$ namely at ${\displaystyle j}$ satisfying ${\displaystyle y_{j}=y_{\tau (j)},}$ and also attains the maximum in (1) due to (4). This contradicts the choice of ${\displaystyle \sigma .}$

If ${\displaystyle x_{1}<\cdots <x_{n},}$ then we have strict inequalities in (2), (3), and (4), hence the maximum can only be attained by permutations keeping the order of ${\displaystyle y_{1}\leq \cdots \leq y_{n},}$ and every other permutation ${\displaystyle \sigma }$ cannot be optimal.

Proof by induction

As above, if suffices to treat the upper bound in (1). For a proof by mathematical induction, we start with ${\displaystyle n=2.}$ Observe that

$${\displaystyle x_{1}\leq x_{2}\quad {\text{ and }}\quad y_{1}\leq y_{2}}$$

implies that

${\displaystyle 0\leq (x_{2}-x_{1})(y_{2}-y_{1}),}$

(5)

which is equivalent to

${\displaystyle x_{1}y_{2}+x_{2}y_{1}\leq x_{1}y_{1}+x_{2}y_{2},}$

(6)

hence the upper bound in (1) is true for ${\displaystyle n=2.}$ If ${\displaystyle x_{1}<x_{2},}$ then we get strict inequality in (5) and (6) if and only if ${\displaystyle y_{1}<y_{2}.}$ Hence only the identity, which is the only permutation here keeping the order of ${\displaystyle y_{1}<y_{2},}$ gives the maximum.

As an induction hypothesis assume that the upper bound in the rearrangement inequality (1) is true for ${\displaystyle n-1}$ with ${\displaystyle n\geq 3}$ and that in the case ${\displaystyle x_{1}<\cdots <x_{n-1}}$ there is equality only when the permutation ${\displaystyle \sigma }$ of ${\displaystyle 1,\ldots ,n-1}$ keeps the order of ${\displaystyle y_{1},\ldots ,y_{n-1}.}$

Consider now ${\displaystyle x_{1}\leq \cdots \leq x_{n}}$ and ${\displaystyle y_{1}\leq \cdots \leq y_{n}.}$ Take a ${\displaystyle \sigma }$ from the finite number of permutations of ${\displaystyle 1,\ldots ,n}$ such that the rearrangement in the middle of (1) gives the maximal result. There are two cases:

• If ${\displaystyle \sigma (n)=n,}$ then ${\displaystyle y_{n}=y_{\sigma (n)}}$ and, using the induction hypothesis, the upper bound in (1) is true with equality and ${\displaystyle \sigma }$ keeps the order of ${\displaystyle y_{1},\ldots ,y_{n-1},y_{n}}$ in the case ${\displaystyle x_{1}<\cdots <x_{n}.}$
• If ${\displaystyle k:=\sigma (n)<n,}$ then there is a ${\displaystyle j\in \{1,\dots ,n-1\}}$ with ${\displaystyle \sigma (j)=n.}$ Define the permutation
  $${\displaystyle \tau (i)={\begin{cases}\sigma (i)&{\text{for }}i\in \{1,\ldots ,n\}\setminus \{j,n\},\\k&{\text{for }}i=j,\\n&{\text{for }}i=n,\end{cases}}}$$

  
  which arises from ${\displaystyle \sigma }$ by exchanging the values of ${\displaystyle j}$ and ${\displaystyle n.}$ There are now two subcases:

1. If ${\displaystyle x_{k}=x_{n}}$ or ${\displaystyle y_{k}=y_{n},}$ then this exchange of values of ${\displaystyle \sigma }$ has no effect on the middle term in (1) because ${\displaystyle \tau }$ gives the same sum, and we can proceed by applying the first case to ${\displaystyle \tau .}$ Note that in the case ${\displaystyle x_{1}<\cdots <x_{n},}$ the permutation ${\displaystyle \tau }$ keeps the order of ${\displaystyle y_{1},\ldots ,y_{n}}$ if and only if ${\displaystyle \sigma }$ does.
2. If ${\displaystyle x_{k}<x_{n}}$ and ${\displaystyle y_{k}<y_{n},}$ then ${\displaystyle 0<(x_{n}-x_{k})(y_{n}-y_{k}),}$ which is equivalent to ${\displaystyle x_{k}y_{n}+x_{n}y_{k}<x_{k}y_{k}+x_{n}y_{n}}$ and shows that ${\displaystyle \sigma }$ is not optimal, hence this case cannot happen due to the choice of ${\displaystyle \sigma .}$

Three or more sequences

A straightforward generalization takes into account more sequences. Assume we have finite ordered sequences of nonnegative real numbers

$${\displaystyle 0\leq x_{1}\leq \cdots \leq x_{n}\quad {\text{and}}\quad 0\leq y_{1}\leq \cdots \leq y_{n}\quad {\text{and}}\quad 0\leq z_{1}\leq \cdots \leq z_{n}}$$

and a permutation ${\displaystyle y_{\sigma (1)},\ldots ,y_{\sigma (n)}}$ of ${\displaystyle y_{1},\dots ,y_{n}}$ and another permutation ${\displaystyle z_{\tau (1)},\dots ,z_{\tau (n)}}$ of ${\displaystyle z_{1},\dots ,z_{n}.}$ Then

$${\displaystyle x_{1}y_{\sigma (1)}z_{\tau (1)}+\cdots +x_{n}y_{\sigma (n)}z_{\tau (n)}\leq x_{1}y_{1}z_{1}+\cdots +x_{n}y_{n}z_{n}.}$$

Note that, unlike the standard rearrangement inequality (1), this statement requires the numbers to be nonnegative. A similar statement is true for any number of sequences with all numbers nonnegative.

Functions instead of factors

Another generalization of the rearrangement inequality states that for all real numbers ${\displaystyle x_{1}\leq \cdots \leq x_{n}}$ and every choice of continuously differentiable functions ${\displaystyle f_{i}:[x_{1},x_{n}]\to \mathbb {R} }$ for ${\displaystyle i=1,2,\ldots ,n}$ such that their derivatives ${\displaystyle f'_{1},\ldots ,f'_{n}}$ satisfy

$${\displaystyle f'_{1}(x)\leq f'_{2}(x)\leq \cdots \leq f'_{n}(x)\quad {\text{ for all }}x\in [x_{1},x_{n}],}$$

the inequality

$${\displaystyle \sum _{i=1}^{n}f_{n-i+1}(x_{i})\leq \sum _{i=1}^{n}f_{\sigma (i)}(x_{i})\leq \sum _{i=1}^{n}f_{i}(x_{i})}$$

holds for every permutation ${\displaystyle f_{\sigma (1)},\ldots ,f_{\sigma (n)}}$ of ${\displaystyle f_{1},\ldots ,f_{n}.}$^[2] Taking real numbers ${\displaystyle y_{1}\leq \cdots \leq y_{n}}$ and the linear functions ${\displaystyle f_{i}(x):=xy_{i}}$ for real ${\displaystyle x}$ and ${\displaystyle i=1,\ldots ,n,}$ the standard rearrangement inequality (1) is recovered.