Maximum euclidean and cosine distance between "permutation" vectors?

Question

This is more out of curiosity than anything else. I actually want to know how you would prove this, so don't just write an answer. thanks!

Let's say I have two vectors of length n which are permutations of the number 1 to n. For example, u = [1 3 2] and v = [3 1 2].

Then I want to know which such vector pair would maximize

1) the euclidean distance

2) the cosine distance

For the euclidean distance, a heuristic approach would make it seem that reversing the vectors would lead to the greatest distance (eg [1 2 3] and [3 2 1]). I'm not sure how to prove it yet but I haven't put much thought into this.

I'm also not sure that same strategy would work with dot product, although I'm guessing it might.

Proof please?

Answer 1

I will answer the second part first as it is easier:

In order to maximize u dot v, we can take advantage of the fact that we know that u dot v = |u||v|cos (theta) where theta is the angle between u and v.  Now since u and v are permutations of each other, we know that |u| = |v| = summation from j = 1 to n (j^2) where n is the number of dimensions of the corresponding vectors.  Therefore we wish to maximize cos (theta), which can only be maximized when theta = 0 which occurs when the two vectors are pointing in the same direction which can only occur in this case when they are in fact the same vector (if u = kv with k > 0, k = 1 since |u| = |v|).  Thus u dot v is maximized if and only if u = v.

Now for the first part, since we wish to maximize |u - v|, we can do so by observing that this is the same as maximizing |u - v|^2.  But

|u - v|^2 = (u - v) dot (u - v)

= u dot u + v dot v - 2 u dot v

= |u|^2 + |v|^2 - 2 u dot v

Now |u|^2 + |v|^2 is fixed for all permutations, so we really just need to maximize (- 2 u dot v) or in other words minimize (u dot v).

I claim that this occurs whenever the value i in vector u is paired with n - i in vector v.

Suppose that we have any other pair of vectors u and v and let k be the smallest value in vector u which is NOT paired with n - k in vector v.  Since all the values larger than n - k in vector v are already matched, the element k in u must be paired with a value smaller than n - k in v.  Similarly the element in u which pairs with n - k in v must be a value larger than k.  So we have 1 in u paired with n - 1 in v, 2 paired with n - 2, ... (k - 1) paired with (n - (k - 1)) and k paired with n - (k + s) with s >= 1 (and k + t paired with (n - k) with t >= 1).  If we alter u and v so that k is paired with (n - k) and k + t is paired with (n - (k + s)) and keep all the other pairings the same, we change a portion of the dot product from

(k)(n - (k + s)) + (k + t)(n - k) = 2kn - 2k^2 - k(s + t) + tn

TO

k(n - k) + (k + t)(n - (k + s)) = 2kn - 2k^2 - k(s + t) + tn - st

which is smaller.

We can repeat this process until we have a pairing where value i in vector u is paired with value (n - i) in vector v and that any such pairing of permutation vectors u and v gives us the smallest possible sum.

Thus your intution was correct assuming you keep in mind that

u = [1 3 2] and v = [3 1 2] is also a valid distance-minimizing pairing because what matters are the pairings of elements, not the order that they are listed in the corresponding vectors.

The above may not constitute the most elegant proof as certain theorems about inequalities (which fail to come to mind at present) might be used.

In the proof of the dot product maximization, I used the fact that the cosine of the angle is at most 1 and went from there.  The truth is that as you increase dimensions, the DEFINITION of the cosine of the angle between two vectors is given by (u dot v)/(|u||v|) and the proof that this value is in fact less than 1 (with equality iff the vectors are positive scalar multiples of each other) can be executed by applying the Cauchy-Schwartz inequality.