Results 1 to 8 of 8

Math Help - Ordering proof?

  1. #1
    Senior Member
    Joined
    Jul 2006
    Posts
    364

    Ordering proof?

    Given unit vectors q and d_i, i=1, 2, 3, ...,
    q, d_i \in \mathbb{R}^n<br />
    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?
    Last edited by scorpion007; June 24th 2010 at 07:07 PM.
    Follow Math Help Forum on Facebook and Google+

  2. #2
    A Plied Mathematician
    Joined
    Jun 2010
    From
    CT, USA
    Posts
    6,318
    Thanks
    4
    Awards
    2
    A couple of comments.

    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.
    Follow Math Help Forum on Facebook and Google+

  3. #3
    Senior Member
    Joined
    Jul 2006
    Posts
    364
    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:

    Follow Math Help Forum on Facebook and Google+

  4. #4
    A Plied Mathematician
    Joined
    Jun 2010
    From
    CT, USA
    Posts
    6,318
    Thanks
    4
    Awards
    2
    Ok, you're going to have to help me out, here, please. What are "cosine similarities"?
    Follow Math Help Forum on Facebook and Google+

  5. #5
    Senior Member
    Joined
    Jul 2006
    Posts
    364
    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.
    Follow Math Help Forum on Facebook and Google+

  6. #6
    A Plied Mathematician
    Joined
    Jun 2010
    From
    CT, USA
    Posts
    6,318
    Thanks
    4
    Awards
    2
    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.
    Follow Math Help Forum on Facebook and Google+

  7. #7
    Senior Member
    Joined
    Jul 2006
    Posts
    364
    Thanks a lot!

    Would it make a difference if the numbers in the vectors were nonnegative?
    Follow Math Help Forum on Facebook and Google+

  8. #8
    A Plied Mathematician
    Joined
    Jun 2010
    From
    CT, USA
    Posts
    6,318
    Thanks
    4
    Awards
    2
    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.
    Follow Math Help Forum on Facebook and Google+

Similar Math Help Forum Discussions

  1. Well-Ordering Proof
    Posted in the Number Theory Forum
    Replies: 2
    Last Post: February 18th 2011, 02:06 AM
  2. Replies: 5
    Last Post: November 25th 2010, 12:11 PM
  3. Proof using Well Ordering
    Posted in the Advanced Algebra Forum
    Replies: 1
    Last Post: February 27th 2010, 11:17 PM
  4. Well Ordering Proof?
    Posted in the Differential Geometry Forum
    Replies: 8
    Last Post: January 14th 2010, 07:31 PM
  5. Well-Ordering Proof Skeleton
    Posted in the Number Theory Forum
    Replies: 4
    Last Post: January 31st 2009, 11:31 AM

Search Tags


/mathhelpforum @mathhelpforum