# Sum of Itemwise Products of Two Sets of Real Numbers

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.

• Rearrangement inequality? – lastresort Nov 15 '18 at 6:10
• Is that the name for this theorem that I've asked for verification & proof of? I thought it probably would have a name & be a theorem ... but I just couldn't find it anywhere! – AmbretteOrrisey Nov 15 '18 at 6:27
• Seen it now - thanks for that. And you don't even need the >1 condition! – AmbretteOrrisey Nov 15 '18 at 6:30

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.)

• That looks like an answer, that does. I'll scrutinise it ... but it has a solid look about it. – AmbretteOrrisey Nov 15 '18 at 1:27
• Oh ... thankyou, by the way! – AmbretteOrrisey Nov 15 '18 at 1:28
• You're welcome! – Chris Culter Nov 15 '18 at 21:18

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.

• Yes - the other guy said essentially the same thing. It's essentially proving it for $n=1$ (two items), then proceeding by induction thence to arbitrary n. Thankyou! – AmbretteOrrisey Nov 15 '18 at 1:30
• Or maybe not induction strictly speaking ... but showing that by applying the two-item case repeatedly until they are both in sorted order always increases the sum of products as defined. – AmbretteOrrisey Nov 15 '18 at 1:37