4
$\begingroup$

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?

  • 3
    This is a special case of the [rearrangement inequality](http://en.wikipedia.org/wiki/Rearrangement_inequality).2011-09-16

3 Answers 3

0

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.

4

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.

4

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.