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?


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.


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.


In order to prove the above fact...we proceed as below... 1) consider both the vectors contains positive scalars...ie... 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.


Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

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