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?

  • $\begingroup$ 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$. $\endgroup$ – Did Oct 26 '11 at 6:57


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

  • $\begingroup$ 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? $\endgroup$ – Benjamin Oct 26 '11 at 7:05
  • $\begingroup$ @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 \|$.) $\endgroup$ – Srivatsan Oct 26 '11 at 7:09
  • $\begingroup$ @SrivatsanNarayanan Thanks:) $\endgroup$ – Benjamin Oct 26 '11 at 7:15
  • $\begingroup$ @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.) $\endgroup$ – p.s. Nov 9 '11 at 21:34

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

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