Take the 2-minute tour ×
Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. It's 100% free, no registration required.

Consider a permutation matrix $P$ and two vectors $x$, $v$ with 2-norm = 1 and all positive entries.

Are the optimal solutions $P^\ast$ of $\max_P \; (x^T \cdot Py)$ and $\min_P \; \|x-Py\|_2$ the same?

share|improve this question
    
Minimizing $\|x-Py\|^2_2=\|x\|^2_2+\|y\|^2-2(x^T\cdot Py)$ over $P$ is equivalent to maximizing $x^T\cdot Py$. –  Did Oct 26 '11 at 6:57

1 Answer 1

up vote 1 down vote accepted

Hint:

$$ \|x-Py\|_2^2=\|x\|_2^2+\|Py\|_2^2-2x^T\cdot Py=2(1-x^T\cdot Py) $$

share|improve this answer
    
Thanks!! One more question, if both of the vectors are able to permute freely, is the best strategy equals to sort both vectors in either ascending or descending order? –  Benjamin Oct 26 '11 at 7:05
    
@Benjamin That approach works. In fact, you can fix one of the permutations arbitrarily, and optimize over the second permutation. (Note that $\| Px - Qy \| = \| x - P^{-1} Q y \|$.) –  Srivatsan Oct 26 '11 at 7:09
    
@SrivatsanNarayanan Thanks:) –  Benjamin Oct 26 '11 at 7:15
    
@Benjamin That is the statement of the Rearrangement inequality. (It's not neccessary to assume x, y are unit norm and positive, by the way.) –  p.s. Nov 9 '11 at 21:34

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

Not the answer you're looking for? Browse other questions tagged or ask your own question.