Choosing the Permutation Which Maximizes a Weighted Sum

Question

Prove

Consider ordered real numbers $x_1 \le x_2 \le \dots \le x_n$ and $y_1 \le y_2 \le \dots \le y_n$.

Let $ \sigma : \{ 1,2,\dots,n\} \rightarrow \{ 1,2,\dots,n\}$ be a permutation on the integers $1,2,\dots,n$.

Show that $\sum\limits_{k=1}^n x_ky_{\sigma(k)} \le \sum\limits_{k=1}^n x_ky_k$.

My Intuition

Algebraically, to maximize a weighted sum, we want to put the heaviest weights $x_k$ on the heaviest values of $y_{\sigma(k)}$. The easiest way to do that is to order them in the same way. In other words,

$max\{ \sum\limits_{k=1}^n x_ky_{\sigma(k)} \} = \sum\limits_{k=1}^n x_ky_k$

Geometrically, the permutation of $y_{\sigma(k)}$ which satisfies this condition would be the one which is ordered in the same direction as $x_k$. To maximize the dot product, we maximize the cosine or minimize the angle between these two vectors. Since permutations would only change the direction of the vector, not its length, we pick the permutation which points in the same increasing direction as $x_k$.

I'm having trouble formalizing a proof for these observations.

Any hints on either a geometric or algebraic approach for a proof would be appreciated.

Answer 1

First Attempt

Using Steve Kass' comment as a guide, I will attempt a proof by contradiction.

Suppose we choose a $\sigma(k)$ that is out-of-order. For example, $y_2$ and $y_1$ are switched.

We claim that $\sum\limits_{k=1}^nx_ky_{\sigma(k)} \color{red}{>} \sum\limits_{k=1}^nx_ky_k$

Common terms on rhs/lhs cancel out giving us,

$(x_1y_2 + x_2y_1) \color{red}{>} (x_1y_1 + x_2y_2)$

$y_2(x_1-x_2) + y_1(x_2-x_1)\color{red}{>} 0$

$y_2(x_1-x_2) - y_1(x_1-x_2)\color{red}{>} 0$

$(y_2-y_1)(x_1-x_2)\color{red}{>} 0$

but this is a contradiction, because the product of a positive number and a negative number cannot be greater than zero.

Therefore, our original assumption was wrong. We are left with:

$\sum\limits_{k=1}^nx_ky_{\sigma(k)} \le \sum\limits_{k=1}^nx_ky_k$.

Similar arguments can be made for any $\sigma(k)$ that is out-of-order.

Second Attempt (Proof By Induction)

We will generalize the proof for any out-of-order weightings. We want to prove

$max\{ \sum\limits_{k=1}^n x_ky_{\sigma(k)} \} = \sum\limits_{k=1}^n x_ky_k$

given

$x_1 \le x_2 \le \dots \le x_n$

$y_1 \le y_2 \le \dots \le y_n$

Note that any permutation can be decomposed into a series of transpositions, or a permutation of two elements. Any transposition can be ordered in two ways, with the coordinates in the same (increasing or decreasing) direction or in the opposite directions.

We start by defining indexes $i<j$ and $k<l$. So $x_iy_l + x_jy_k$ is ordered in opposite directions, while $x_iy_k + x_jy_l$ is weighted in the same direction. We make the assumption that the former sum is larger than the latter.

$(x_iy_l + x_jy_k) \color{red}{>} (x_iy_k + x_jy_l)$

$(x_iy_l + x_jy_k) - (x_iy_k + x_jy_l) \color{red}{>} 0$

$x_i(y_l - y_k) - x_j(y_l - y_k) \color{red}{>} 0$

$(x_i-x_j)*(y_l - y_k) \color{red}{>} 0$

Again, we have a contradiction, because the product of a negative number and a positive number cannot be greater than zero. So the correct expression is

$(x_iy_l + x_jy_k) \le (x_iy_k + x_jy_l)$

The transposition with the matched order produces the greater sum.

From here, one step at a time, we can then increase the value of the weighted sum by applying transpositions until the two vectors are entirely matched up in ordering. Any further transposition would only decrease the sum, so at this point, we have reached the ordering for the maximal sum.

Answer 2

Consider the permutation $\sigma:\{1,2,3,\ldots,n\} \rightarrow \{1,2,3,\ldots,n\} $ for which $\Sigma_{i=1}^n x_i y_{\sigma(i)}$ is maximized.
If possible, let this be a permutation $\sigma_0$ which is not the identity permutation for which the following strict inequality holds:
$ \Sigma_{i=1}^n x_i y_{\sigma_0(i)} > \Sigma_{i=1}^n x_i y_i$
Since $\sigma_0$ is not the identity permutation, there exist at least two distinct numbers $i_1$ and $i_2$ where $i_1,i_2 \in \{1,2,3,\ldots,n\} $ and $i_1 < i_2$ such that $y_{\sigma_0(i_1)}>y_{\sigma_0(i_2)}$.
Now, consider the permutation $\sigma_1:\{1,2,3,\ldots,n\} \rightarrow \{1,2,3,\ldots,n\}$ such that:
$\sigma_1(i) = \sigma_0(i)$ for $i\in \{1,2,3,\ldots,n\}\backslash \{i_1,i_2 \} ,$
$\sigma_1(i_1) = \sigma_0(i_2) ,$
$\sigma_1(i_2) = \sigma_0(i_1). $
Consider the following expression:
$ \Sigma_{i=1}^n x_i y_{\sigma_1(i)} -\Sigma_{i=1}^n x_i y_{\sigma_0(i)} $
$ = x_{i_1}y_{\sigma_0(i_2)}+x_{i_2}y_{\sigma_0(i_1)} - x_{i_1}y_{\sigma_0(i_1)} -x_{i_2}y_{\sigma_0(i_2)} $
$ = (x_{i_2} - x_{i_1}) (y_{\sigma_0(i_1)} - y_{\sigma_0(i_2)}) \geq 0 $
In other words, $ \Sigma_{i=1}^n x_i y_{\sigma_1(i)} \geq \Sigma_{i=1}^n x_i y_{\sigma_0(i)}.$
However, $\sigma_0$ is supposed to maximize the experession $\Sigma_{i=1}^n x_i y_{\sigma(i)}$, which means $ \Sigma_{i=1}^n x_i y_{\sigma_1(i)} = \Sigma_{i=1}^n x_i y_{\sigma_0(i)} $.
This means that for any pair of integers $\{i_1,i_2 \}\subset \{1,2,3,\ldots,n\} $ for which $y_{\sigma_0(i_1)}>y_{\sigma_0(i_2)}$, swapping $\sigma_0$'s values on $\{i_1,i_2 \}$ should not change the expression $\Sigma_{i=1}^n x_i y_{\sigma_0(i)} $.
Thus, performing a bubble sort on the list $ \{y_{\sigma(i)} \}_{i\in\{1,2,3,\ldots,n\}} $ and assigning the indices of $y_i$ in the new order to $\sigma_0(i)$ should not change the above expression. But the end result of this bubble sort is $y_1,y_2,y_3,\ldots,y_n$, making the expression:
$ \Sigma_{i=1}^n x_i y_{\sigma_0(i)} = \Sigma_{i=1}^n x_i y_i$ But this contradicts our initial assumption.

Hence, the problem.