0
$\begingroup$

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?

  • 0
    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$.2011-10-26

1 Answers 1

1

Hint:

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

  • 0
    @Benjamin That is the statement of the [Rearrangement inequality](http://en.wikipedia.org/wiki/Rearrangement_inequality). (It's not neccessary to assume x, y are unit norm and positive, by the way.)2011-11-09