Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. Join them; it only takes a minute:

Sign up
Here's how it works:
  1. Anybody can ask a question
  2. Anybody can answer
  3. The best answers are voted up and rise to the top

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|cite|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
up vote 1 down vote accepted


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

share|cite|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


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.