# Ordering proof?

• June 24th 2010, 05:42 AM
scorpion007
Ordering proof?
Given unit vectors $q$ and $d_i$, i=1, 2, 3, ...,
$q, d_i \in \mathbb{R}^n
$

and we compute $q\cdot d_i$ and the L2 distance between them, $|q-d_i|^2=\sum_{j=1}^n (q_i-d_{ij})^2$, and we were to order the $d_i$'s in increasing order of those computations, show that the relative orders of $d_i$ would be the same for both cases (i.e. the inner product and L2-norm).

(This is paraphrased from a problem in a non-math book)
Any tips?
• June 24th 2010, 06:58 AM
Ackbeet

1. You're confusing your notation there. You've got $d_{i}$ for the ith vector, but also for the ith component of one of those vectors. Better to write $(d_{i})_{j}$ for the jth component of the ith vector, and sum over j in the $L^{2}$ norm.

2. I'm a bit surprised at the result. I would have expected the order to reverse:
$|q-d_{i}|^{2}=(q-d_{i})\cdot(q-d_{i})=|q|^{2}-2q\cdot d_{i}+|d_{i}|^{2}=2-2q\cdot d_{i}$.

That last step is valid because everything in sight is a unit vector. So, in comparing $q\cdot d_{i}$ with the $L^{2}$ norm of the difference, you've got a sign reversal. Hence, I would expect the order to reverse.
• June 24th 2010, 06:04 PM
scorpion007
Thanks - about the notation, that's a result of me editing in the d_i at the last minute, I forgot to fix the sum :)

The result does indeed strange; Here's what the question said:

http://img192.imageshack.us/img192/8703/math30.png
• June 24th 2010, 06:07 PM
Ackbeet
Ok, you're going to have to help me out, here, please. What are "cosine similarities"?
• June 24th 2010, 06:08 PM
scorpion007
That's just the cos(theta) = a.b/|a||b|, but because |a|=|b|=1 we can ignore it. So $q\cdot d_i$ in our case.
• June 24th 2010, 06:16 PM
Ackbeet
Well, if that's the case, I don't buy it. Let's take the 2-dimensional case. Let $\vec{q}=\{1,0\}$, $\vec{d}_{1}=\{1,0\}$, $\vec{d}_{2}=\{0,1\}$, and $\vec{d}_{3}=\{-1,0\}$.

Then we have the following ordering for Euclidean distance (least to greatest):

$|\vec{q}-\vec{d}_{1}|=0$
$|\vec{q}-\vec{d}_{2}|=\sqrt{2}$
$|\vec{q}-\vec{d}_{3}|=2$.

Now, we compute the dot products:

$\vec{q}\cdot\vec{d}_{1}=1$
$\vec{q}\cdot\vec{d}_{2}=0$
$\vec{q}\cdot\vec{d}_{3}=-1$.

The order is reversed, like I thought it would be.
• June 24th 2010, 06:39 PM
scorpion007
Thanks a lot!

Would it make a difference if the numbers in the vectors were nonnegative?
• June 25th 2010, 02:10 AM
Ackbeet
No, it wouldn't. Think about it. All the vectors lie on the unit sphere. If you think of the d_i vector tips as getting farther and farther away from the q tip (pun intended), then the amount of d_i that is going in the same direction as q is getting smaller (this is what the dot product is measuring: the projection either of d_i onto q, or of q onto d_i). This is true, even if, in my example, the x component of the d_i's never goes negative.