Take the 2-minute tour ×
Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. It's 100% free, no registration required.

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?

share|improve this question
    
I'm not even sure that [correlation] fits here, but I am sure that [elementary-set-theory] doesn't. –  Asaf Karagila Oct 25 '12 at 8:55

3 Answers 3

up vote 2 down vote accepted

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

share|improve this answer

This also follows from Cauchy Schwartz:

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

share|improve this answer

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<a_j$ 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.$$

share|improve this answer

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

Not the answer you're looking for? Browse other questions tagged or ask your own question.