Geometric Interpretation of Rearrangement Inequality

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.

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.)

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:

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:

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.