## Sunday, September 14, 2014

### a bit of random stuff: Rearrangement Inequality

Theorem:
Let $$x_1 \leq x_2 \leq \ldots \leq x_n$$, $$y_1 \leq y_2 \leq \ldots \leq y_n$$,  and $$S = x_1y_2 + x_2y_2 + \ldots + x_ny_n$$. Then $$S \geq \sum x'y'$$ Where $$x'$$ and $$y'$$ is some permutation of $$x_i$$ and $$y_i$$.

Proof:
First we prove the case where $$n = 2$$:
Since $$x_1 \leq x_2$$ and $$y_1 \leq y_2$$ we have $$0 \leq (x_2-x_1)(y_2-y_1) = x_2y_2 +x_1y_2 - (x_1y_2+x_2y_1)$$ and hence $$x_2y_2 +x_1y_2 \geq x_1y_2+x_2y_1$$.

This means that whenever we see two pairs $$x_1y_2$$ and $$x_2y_1$$, swapping the $$y_1$$ and $$y_2$$ will lead to a larger value.

Suppose that there is $$S'$$ that is larger than $$S$$. Then there is some $$x'_iy'_i$$ and $$x'_jy'_j$$ in $$S'$$ such that either:
1.  $$x'_i \leq x'_j \text{ and } y'_i \geq y'_j$$ or
2. $$x'_i \geq x'_j \text{ and } y'_i \leq y'_j$$
Because if there is not such pairs, then every pair is in the form $$x'_i \leq x'_j$$ and $$y'_i \leq y'_j$$ which by incremental construction will lead to the conclusion that $$S' = S$$ which is not the case.
Then we can swap $$y'_i$$ and $$y'_j$$ and arrive at a larger value than $$S'$$, a contradiction. Therefore $$S$$ must have been maximal.