
Ordering proof?
Given unit vectors and , i=1, 2, 3, ...,
and we compute and the L2 distance between them, , and we were to order the 's in increasing order of those computations, show that the relative orders of would be the same for both cases (i.e. the inner product and L2norm).
(This is paraphrased from a problem in a nonmath book)
Any tips?

A couple of comments.
1. You're confusing your notation there. You've got for the ith vector, but also for the ith component of one of those vectors. Better to write for the jth component of the ith vector, and sum over j in the norm.
2. I'm a bit surprised at the result. I would have expected the order to reverse:
.
That last step is valid because everything in sight is a unit vector. So, in comparing with the norm of the difference, you've got a sign reversal. Hence, I would expect the order to reverse.

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

Ok, you're going to have to help me out, here, please. What are "cosine similarities"?

That's just the cos(theta) = a.b/ab, but because a=b=1 we can ignore it. So in our case.

Well, if that's the case, I don't buy it. Let's take the 2dimensional case. Let , , , and .
Then we have the following ordering for Euclidean distance (least to greatest):
.
Now, we compute the dot products:
.
The order is reversed, like I thought it would be.

Thanks a lot!
Would it make a difference if the numbers in the vectors were nonnegative?

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.