0
$\begingroup$

If we have two identical sets $A_1 = A_2 $, and we were asked to get the maximum sum of multiplying one distinct element from $A_1$ by another distinct element of $A_2$, for all elements in $A_1$.

For example, if $A_1 = A_2 = \{1, 0, 4, 5\}$, one (not maximum) option would be to do the following:

Multiply 1st element of $A_1$ by 2nd element of $A_2$, and vice versa (2nd of $A_1$ by 1st of $A_2$), then we can multiply 3rd of $A_1$ by 4th of $A_2$ and vice versa (4th of $A_1$ by 3rd of $A_2$):

$(1*0) + (0*1) + (4*5) + (5*4) = 40$

Clearly this will not give us the maximum value, and by only doing the correlation (dot product) we would get the maximum value, which is $(1*1) + (0*0) + (4*4) + (5*5) = 42$

My question is: is there a way to mathematically prove that? That by only doing the dot product we will get the max value?

  • 0
    I'm not even sure that [correlation] fits here, but I am sure that [elementar$y$-set-theory] $d$oesn't.2012-10-25

3 Answers 3

2

This is a direct consequence of Rearrangement Inequality. All you need to assume WLOG is that the elements of your set are ordered. This assumption does not affect your problem statement as it is. Then, application of rearrangement inequality gives the result you desire.

[1] http://en.wikipedia.org/wiki/Rearrangement_inequality

1

This also follows from Cauchy-Schwarz:

If your first ordering is $(x_1,.., x_n)$ an your last one is $(y_1,.., y_n)$ then

$x_1y_1+...+x_ny_n \leq \sqrt{x_1^2+...+x_n^2}\sqrt{y_1^2+...+y_n^2}=x_1^2+...x_n^2 \,.$

Moreover, you get equality if and only if $\frac{x_1}{y_1}=...=\frac{x_n}{y_n}$.

If $\frac{x_1}{y_1}=...=\frac{x_n}{y_n}$ then $\frac{x_1}{y_1}=...=\frac{x_n}{y_n}=\frac{x_1+..+x_n}{y_1+...+y_n}=1$. Using this, you can easily prove that you get equality if and only if $\frac{x_1}{y_1}=...=\frac{x_n}{y_n}=1$.

0

As long as you have any instance of misarrangement, i.e. your sum is $\ldots+a_i b_i+\ldots+a_jb_j+\ldots$ with $a_i and $b_i>b_j$, you can increase the sum by swapping $b_i, b_j$:

$(a_ib_j+a_jb_i)-(a_ib_i+a_jb_j)=(a_j-a_i)(b_i-b_j)>0.$