Sum of Itemwise Products of Two Sets of Real Numbers

Question

The memory that I considered this question a long time ago was jogged by my perusing an earlier one about whether a product is always greater than a sum.

If you have two sequences of real positive numbers, all greater than 1, and each sequence increasing with increasing index $k$

$$a_k , k \in {0 ... n}$$

&

$$b_k , k \in {0 ... n} , $$

and if the elements are multiplied together itemwise & the products summed, is the maximum always

$\sum_{k=0}^n a_k b_k$

and the minimum always

$\sum_{k=0}^n a_k b_{n-k}$?

It would seem so, merely casting it in the mind ... but I can't see how it would be rigorously proven ... nor am I absolutely sure it's absolutely true, either.

Answer 1

First consider the simplest nontrivial case, $n=2$. Let $a_1>a_0$ and $b_1>b_0$. Then $(a_1-a_0)(b_1-b_0)>0$, which simplifies to $a_0b_0+a_1b_1>a_0b_1+a_1b_0$, which is what we want.

Now let $n>2$. Without loss of generality, fix $a$ in its sorted permutation and consider permutations of $b$. If $b$ is not sorted, then there are two indices that are out of order, and the $n=2$ lemma proves that we can increase the product by swapping those two indices. Therefore only the sorted order of $b$ maximizes the product. For the same reason, only the anti-sorted order of $b$ minimizes the product.

(You could toss a bunch of index notation at the previous paragraph to make it look more formal.)

Answer 2

Yes. Start with $n=1$ so there are two items in each list. Note that $$(a_0b_0+a_1b_1) - (a_0b_1+a_1b_0)=a_1(b_1-b_0)-a_0(b_1-b_0)\gt 0$$ For longer lists, you can use the same argument to swap any pair that is out of order and increase the sum.