Rearrangement inequality explained

\sigma

of the numbers

1,2,\ldotsn

we haveInformally, this means that in these types of sums, the largest sum is achieved by pairing large

x

values with large

y

values, and the smallest sum is achieved by pairing small values with large values. This can be formalised in the case that the

x1,\ldots,xn

are distinct, meaning that

x1<<xn,

then:
  1. The upper bound in is attained only for permutations

\sigma

that keep the order of

y1,\ldots,yn,

that is, y_ \le \cdots \le y_, or equivalently

(y1,\ldots,yn)=(y\sigma(1),\ldots,y\sigma(n)).

Such a

\sigma

can permute the indices of

y

-values that are equal; in the case

y1==yn

every permutation keeps the order of

y1,\ldots,yn.

If

y1<<yn,

then the only such

\sigma

is the identiy.
  1. Correspondingly, the lower bound in is attained only for permutations

\sigma

that reverse the order of

y1,\ldots,yn,

meaning that y_ \ge \cdots \ge y_. If

y1<<yn,

then

\sigma(i)=n-i+1

for all

i=1,\ldots,n,

is the only permutation to do this.Note that the rearrangement inequality makes no assumptions on the signs of the real numbers, unlike inequalities such as the arithmetic-geometric mean inequality.

Applications

Many important inequalities can be proved by the rearrangement inequality, such as the arithmetic mean – geometric mean inequality, the Cauchy–Schwarz inequality, and Chebyshev's sum inequality.

As a simple example, consider real numbers

x1\le\lexn

: By applying with

yi:=xi

for all

i=1,\ldots,n,

it follows thatx_1 x_n + \cdots + x_n x_1\le x_1 x_ + \cdots + x_n x_\le x_1^2 + \cdots + x_n^2for every permutation

\sigma

of

1,\ldots,n.

Intuition

The rearrangement inequality can be regarded as intuitive in the following way. Imagine there is a heap of $10 bills, a heap of $20 bills and one more heap of $100 bills. You are allowed to take 7 bills from a heap of your choice and then the heap disappears. In the second round you are allowed to take 5 bills from another heap and the heap disappears. In the last round you may take 3 bills from the last heap. In what order do you want to choose the heaps to maximize your profit? Obviously, the best you can do is to gain

7 ⋅ 100+5 ⋅ 20+3 ⋅ 10

dollars. This is exactly what the upper bound of the rearrangement inequality says for the sequences

3<5<7

and

10<20<100.

In this sense, it can be considered as an example of a greedy algorithm.

Geometric interpretation

Assume that

0<x1<<xn

and

0<y1<<yn.

Consider a rectangle of width

x1++xn

and height

y1++yn,

subdivided into

n

columns of widths

x1,\ldots,xn

and the same number of rows of heights

y1,\ldots,yn,

so there are

stylen2

small rectangles. You are supposed to take

n

of these, one from each column and one from each row. The rearrangement inequality says that you optimize the total area of your selection by taking the rectangles on the diagonal or the antidiagonal.

Proofs

Proof by contradiction

The lower bound and the corresponding discussion of equality follow by applying the results for the upper bound to- y_n \le \cdots \le - y_1.Therefore, it suffices to prove the upper bound in and discuss when equality holds. Since there are only finitely many permutations of

1,\ldots,n,

there exists at least one

\sigma

for which the middle term in x_1 y_ + \cdots + x_n y_is maximal. In case there are several permutations with this property, let σ denote one with the highest number of integers

i

from

\{1,\ldots,n\}

satisfying

yi=y\sigma(i).

We will now prove by contradiction, that

\sigma

has to keep the order of

y1,\ldots,yn

(then we are done with the upper bound in, because the identity has that property). Assume that there exists a

j\in\{1,\ldots,n-1\}

such that

yi=y\sigma(i)

for all

i\in\{1,\ldots,j-1\}

and

yjy\sigma(j).

Hence

yj<y\sigma(j)

and there has to exist a

k\in\{j+1,\ldots,n\}

with

yj=y\sigma(k)

to fill the gap. Therefore,which implies thatExpanding this product and rearranging giveswhich is equivalent to . Hence the permutation\tau(i):=\begin\sigma(i)&\texti \in \\setminus\,\\\sigma(k)&\texti = j,\\\sigma(j)&\texti = k,\endwhich arises from

\sigma

by exchanging the values

\sigma(j)

and

\sigma(k),

has at least one additional point which keeps the order compared to

\sigma,

namely at

j

satisfying

yj=y\tau(j),

and also attains the maximum in due to . This contradicts the choice of

\sigma.

If

x1<<xn,

then we have strict inequalities in,, and, hence the maximum can only be attained by permutations keeping the order of

y1\le\leyn,

and every other permutation

\sigma

cannot be optimal.

Proof by induction

As above, it suffices to treat the upper bound in . For a proof by mathematical induction, we start with

n=2.

Observe that x_1 \le x_2 \quad \text \quad y_1 \le y_2implies thatwhich is equivalent tohence the upper bound in is true for

n=2.

If

x1<x2,

then we get strict inequality in and if and only if

y1<y2.

Hence only the identity, which is the only permutation here keeping the order of

y1<y2,

gives the maximum.

As an induction hypothesis assume that the upper bound in the rearrangement inequality is true for

n-1

with

n\ge3

and that in the case

x1<<xn-1

there is equality only when the permutation

\sigma

of

1,\ldots,n-1

keeps the order of

y1,\ldots,yn-1.

Consider now

x1\le\lexn

and

y1\le\leyn.

Take a

\sigma

from the finite number of permutations of

1,\ldots,n

such that the rearrangement in the middle of gives the maximal result. There are two cases:

\sigma(n)=n,

then

yn=y\sigma(n)

and, using the induction hypothesis, the upper bound in is true with equality and

\sigma

keeps the order of

y1,\ldots,yn-1,yn

in the case

x1<<xn.

k:=\sigma(n)<n,

then there is a

j\in\{1,...,n-1\}

with

\sigma(j)=n.

Define the permutation \tau(i)=\begin\sigma(i)&\texti \in \\setminus\,\\k&\texti = j,\\n&\texti = n,\end which arises from

\sigma

by exchanging the values of

j

and

n.

There are now two subcases:
  1. If

xk=xn

or

yk=yn,

then this exchange of values of

\sigma

has no effect on the middle term in because

\tau

gives the same sum, and we can proceed by applying the first case to

\tau.

Note that in the case

x1<<xn,

the permutation

\tau

keeps the order of

y1,\ldots,yn

if and only if

\sigma

does.
  1. If

xk<xn

and

yk<yn,

then

0<(xn-xk)(yn-yk),

which is equivalent to

xkyn+xnyk<xkyk+xnyn

and shows that

\sigma

is not optimal, hence this case cannot happen due to the choice of

\sigma.

Generalizations

Three or more sequences

A straightforward generalization takes into account more sequences. Assume we have finite ordered sequences of nonnegative real numbers0 \le x_1\le\cdots\le x_n\quad\text\quad 0\le y_1\le\cdots\le y_n\quad\text\quad 0\le z_1\le\cdots\le z_nand a permutation

y\sigma(1),\ldots,y\sigma(n)

of

y1,...,yn

and another permutation

z\tau(1),...,z\tau(n)

of

z1,...,zn.

Then x_1 y_ z_ + \cdots + x_n y_ z_ \le x_1 y_1 z_1 + \cdots + x_n y_n z_n.

Note that, unlike the standard rearrangement inequality, 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

x1\le\lexn

and every choice of continuously differentiable functions

fi:[x1,xn]\to\R

for

i=1,2,\ldots,n

such that their derivatives

f'1,\ldots,f'n

satisfyf'_1(x) \le f'_2(x) \le \cdots \le f'_n(x) \quad \text x \in [x_1,x_n],the inequality\sum_^n f_(x_i) \le \sum_^n f_(x_i) \le \sum_^n f_i(x_i)holds for every permutation

f\sigma(1),\ldots,f\sigma(n)

of

f1,\ldots,fn.

Taking real numbers

y1\le\leyn

and the linear functions

fi(x):=xyi

for real

x

and

i=1,\ldots,n,

the standard rearrangement inequality is recovered.

See also

Notes and References

  1. , Section 10.2, Theorem 368