Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. Join them; it only takes a minute:

Sign up
Here's how it works:
  1. Anybody can ask a question
  2. Anybody can answer
  3. The best answers are voted up and rise to the top

The minimum scalar product of two set of data is when they are ordered in an inverse way.

$$A=\langle 200, 8, 110, 300\rangle$$ $$B=\langle 22, 34, 88, 1 \rangle$$

Ordering both in an inverse way and putting in a vector

$$A_0= \langle 8, 110, 200, 300 \rangle$$ $$B_0= \langle 88, 34, 22, 1 \rangle$$

Now the minimum scalar product is $A_0 \times B_0$. How to prove that?

share|cite|improve this question
This is a special case of the rearrangement inequality. – Srivatsan Sep 16 '11 at 16:50
up vote 1 down vote accepted

Suppose we have 2 vectors:

  • a = (a1, a2, a3, ..., an)
  • b = (b1, b2, b3, ..., bn)

And suppose we have already sorted the two vectors above, such that:

  • a1 <= a2 <= a3 <= ... <= an
  • b1 >= b2 >= b3 >= ... >= bn

Let scalar_product1 = a * b = a1*b1 + a2*b2 + a3*b3 + ... + an*bn

If we swap any 2 elements in any vector, for example, in b we swap b2 and b3, then:

  • b' = (b1, b3, b2, ..., bn)

We have: scalar_product2 = a * b' = a1*b1 + a2*b3 + a3*b2 + ... + an*bn

We then do a calculation: scalar_product1 - scalar_product2 = (a2 - a3)*(b2-b3) < 0. This means our original scalar product would be increased if any swapping is done.

share|cite|improve this answer

The scalar product will be the same if you reorder $A$ and $B$ in the same way, so we can order $A$ in some way and then ask which order for $B$ leads to the minimum product. So order $A$ in ascending order, and start with $B$ in any order. Whenever you swap two numbers in $B$ that are not already in descending order, you bring them into descending order and you don't increase the scalar product. You can continue this process until all of $B$ is ordered in descending order, and since this never increases the scalar product no matter which order of $B$ you start from, it must yield the minimum scalar product.

share|cite|improve this answer

In order to prove the above fact...we proceed as below... 1) consider both the vectors contains positive X = ( x1 , x2 ,x3 , x4..) // x1 , x2 ,x3 >0 similarly for Y....

lets solve for the simple case...for 2 dimensional things... X = ( x , x+1 ) //arranging in ascending order.. Y = ( y , y-1 ) //arranging in descending order... just check now X.Y

then put Y = ( y-1 , y ) //disarranging the descending order... and compute X.Y

we will see that indeed the fact is true....

Now because i have given you'll a start go ahead and do the rest because i need a rest now.

share|cite|improve this answer

Your Answer


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.