3

Let $a_1 \ge a_2 \ge \cdots \ge a_n$ and $b_1 \ge b_2 \ge ... \ge b_n$.
Then $a_1b_1 + a_2b_2 + \cdots + a_nb_n \ge a_1b_{\pi(1)} + a_2b_{\pi(2)} + \cdots + a_nb_{\pi(n)}$

The proof I'm reading uses an exchange argument.

Consider a permutation $\pi(1), \pi(2), \ldots, \pi(n)$ such that $a_1b_1 + a_2b_2 + \cdots + a_nb_n$ is maximized.
The desired result is that $\pi$ is the identity permutation $\pi(i)=i$ for all i.
Suppose for the sake of contradiction that $\pi$ is not the identity.
Let $i$ be the smallest integer such that $\pi(i) \ne i$

Since $i$ is the smallest such integer, this means that $\pi(i) = j > i$
Also, there must exist $k > i$ such that $\pi(k) = i$

Since $i < j$ it follows that $b_i \le b_j$
Since $i < k$ it follows that $a_i \le a_k$
Therefore $0 \le (a_k - a_i)(b_j - b_i) \Rightarrow a_ib_j+a_kb_i \le a_ib_i + a_kb_j$

so the sum $a_1b_{\pi(1)} + a_2b_{\pi(2)} + \cdots + a_nb_{\pi(n)}$ is not decreased by changing $\pi(i) = j, \pi(k) = i$ to $\pi(i) = i, \pi(k) = j$
This implies that the identity permutation gives the maximum possible value of $a_1b_{\pi(1)} + a_2b_{\pi(2)} + \cdots + a_nb_{\pi(n)}$ as required.

I don't follow the following 2 lines of the proof:
$\quad$Since $i < j$ it follows that $b_i \le b_j$
$\quad$Since $i < k$ it follows that $a_i \le a_k$

Could someone clarify why it wouldn't be:
$\quad$Since $i < j$ it follows that $b_i \ge b_j$
$\quad$Since $i < k$ it follows that $a_i \ge a_k$

Michael Hardy
  • 1
user137481
  • 2,605

2 Answers2

2

You're right, both inequalities should both be the other way round. Since the proof also works if the order of the indices is reversed, the author presumably got mixed up. $(a_k-a_j)(b_j-b_i)$ is positive if either ($a_k \geq a_i$ and $b_j \geq b_i$) (both sequences increasing) or ($a_k \leq a_i$ and $b_j \leq b_i$) (both sequences decreasing).

Chappers
  • 67,606
0

Because $a_1\geq a_2\geq...\geq a_n$ and $b_1\geq b_2\geq...\geq b_n$.

Michael Rozenberg
  • 194,933