Rearrangement Inequality - Proof

Proof

The lower bound follows by applying the upper bound to

Therefore, it suffices to prove the upper bound. Since there are only finitely many permutations, there exists at least one for which

is maximal. In case there are several permutations with this property, let σ denote one with the highest number of fixed points.

We will now prove by contradiction, that σ has to be the identity (then we are done). Assume that σ is not the identity. Then there exists a j in {1, ..., n − 1} such that σ(j) ≠ j and σ(i) = i for all i in {1, ..., j − 1}. Hence σ(j) > j and there exists k in {j + 1, ..., n} with σ(k) = j. Now

j<k\Rightarrow y_j\le y_k \qquad\text{and}\qquad j=\sigma(k)<\sigma(j)\Rightarrow x_j\le x_{\sigma(j)}.\quad(1)

Therefore,

Expanding this product and rearranging gives

hence the permutation

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

which arises from σ by exchanging the values σ(j) and σ(k), has at least one additional fixed point compared to σ, namely at j, and also attains the maximum. This contradicts the choice of σ.

If

then we have strict inequalities at (1), (2), and (3), hence the maximum can only be attained by the identity, any other permutation σ cannot be optimal.

Read more about this topic:  Rearrangement Inequality

Famous quotes containing the word proof:

    “The fact that several men were able to become infatuated with that latrine is truly the proof of the decline of the men of this century.”
    —Charles Baudelaire (1821–1867)

    “Sculpture and painting are very justly called liberal arts; a lively and strong imagination, together with a just observation, being absolutely necessary to excel in either; which, in my opinion, is by no means the case of music, though called a liberal art, and now in Italy placed even above the other two—a proof of the decline of that country.”
    —Philip Dormer Stanhope, 4th Earl Chesterfield (1694–1773)

    “If any doubt has arisen as to me, my country [Virginia] will have my political creed in the form of a “Declaration &c.” which I was lately directed to draw. This will give decisive proof that my own sentiment concurred with the vote they instructed us to give.”
    —Thomas Jefferson (1743–1826)