8
$\begingroup$

We know that many of the famous classical inequalities have geometric interpretations. Can you give a geometric interpretation of Rearrangement Inequality?

Note: Rearrangement Inequality is

$$x_ny_1 + \ldots + x_1y_n \leq x_{\sigma(1)}y_1+ \ldots + x_{\sigma(n)}y_n \leq x_1y_1+\ldots + x_ny_n$$

for every choice of real numbers

$$x_1 \leq \ldots \leq x_n$$ and

$$y_1 \leq \ldots \leq y_n$$

and every permutation $x_{\sigma(1)}, \ldots, x_{\sigma(n)}$ of $x_1, \ldots , x_n$.

The wikipedia page of the rearrangement inequality can be found here

$\endgroup$
4
+50
$\begingroup$

Here is an interpretation (and proof) of the rearrangement inequality, in pictures that resemble abstract art.

Draw an $x_1 + \dots + x_n$ by $y_1 + \dots + y_n$ rectangle, divided into columns of width $x_1, \dots, x_n$ and rows of height $y_1, \dots, y_n$. A sum of the form $$x_{\sigma(1)}y_1+ \dots + x_{\sigma(n)}y_n$$ is equivalent to choosing $n$ cells, one in each row and one in each column, and finding their total area. One such area is shown below.

one possible choice of permutation

Let's begin by comparing two choices of $\sigma$ that differ only by a single transposition, as shown in the diagram below. (One area is in red, the other in blue, with overlaps in purple.)

comparison between two permutations

This lets us focus on only a $2 \times 2$ example: the place where the two permutations disagree. We can throw away all the rows and columns where they agree, and zoom in on that:

2x2 example

Here, the two columns have width $x_1 < x_2$ and the two rows have height $y_1 < y_2$. The red area is $x_1 y_2 + x_2 y_1$ and the blue area is $x_1 y_1 + x_2 y_2$. I will show that blue is bigger than red by pairing up equal areas and seeing a blue area left over:

pairing proof

Here, we've further subdivided the rectangle into columns of width $x_1, x_1, x_2-x_1$ and rows of height $y_1, y_1, y_2-y_1$. In the first two rows and first two columns, we've paired each red cell with a blue cell of equal area. But the top right cell, which has area $(x_2 -x_1)(y_2 -y_1)$, is blue and unpaired. So the blue area is greater!


Now the rearrangement inequality follows. We know that if we make local changes (such as from red to blue in the second diagram) that bring the two sequences closer to the same order, we increase the area. From an arbitrary product $x_{\sigma(1)}y_1+ \dots + x_{\sigma(n)}y_n$, if we keep doing such swaps while they're possible, we eventually get to the product $x_1y_1 + \dots + x_ny_n$, so we know this product is the greatest.

Similarly, if we make the opposite local changes, bringing the two sequences closer to opposite orders, we decrease the area. From an arbitrary product $x_{\sigma(1)}y_1+ \dots + x_{\sigma(n)}y_n$, if we keep doing such swaps whil ethey're possible, we eventually get to the product $x_1y_n + \dots + x_ny_1$, so we know this product is the least.

$\endgroup$
  • $\begingroup$ The bounty is yours! @MishaLavrov . Thank you very much for your efforts. $\endgroup$ – scarface Apr 24 '17 at 23:45
1
$\begingroup$

One interpretation is derived from the fact that a rectangle with a given perimeter has the maximum area when the rectangle is square.

Further if sides of one rectangle are $w_0,l_0$ and another rectangle with same perimeter has sides $w_1,l_1$ then if $|l_0-w_0| < |l_1-w_1|$ then first rectangle's area will be greater than second.

Rearranging the sequences of $x_i,y_i$ tends to make the products larger. It's like you have a bunch of widths and lengths and you want to compose rectangles from them, whose sum of areas is maximized. Then making the rectangles as close to squares as possible maximizes the sum of areas.

This isn't a rigorous argument but it could be made rigorous by including the elements of the proof of the inequality in the argument.

For example, using the ascending sequences $x_0,x_1$ and $y_0,y_1$ it can easily be seen that $x_0y_0+x_1y_1 \geq x_0y_1+x_1y_0 ==> (x_1-x_0)y_1 > (x_1-x_0)y_0$ and hence that of the two possible compositions of rectangles the one with the biggest and smallest rectangle has more area than the one with the two intermediate sized rectangles.

In the same way that the inequality proves the sum of products is maximized when the products are corresponding factors from sorted sequences, the geometrical interpretation is that the rectangle areas are maximized when the widths and lengths are taken from sorted sequences.

$\endgroup$
  • $\begingroup$ Thank you for your efforts. May you add a picture (or pictures) about rearranging sequences $x_i,y_i$ and the compose rectangles? May you give supporter pictures? Especially for your third paragraph and last paragraph. $\endgroup$ – scarface Apr 18 '17 at 22:53

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.