Preserving componentwise order of a vector when permutating the indices

26 Views Asked by At

I want to prove the following:

Let $x,y\in\Bbb R ^N$ and $\pi ^x , \pi ^y \in \mathcal S_N$ such that $$x_{\pi^x (1)} \geq \ldots \geq x_{\pi^x (N)} ,\quad y_{\pi^y (1)} \geq \ldots \geq y_{\pi^y (N)}.$$ Then it holds: $$x_i \geq y_i \quad\forall i=1,\ldots,N \Rightarrow x_{\pi^x(i)} \geq y_{\pi^y (i)} \quad \forall i = 1,\ldots, N$$

1

There are 1 best solutions below

0
On BEST ANSWER

Let $i \in \{1,\ldots,N\}$. Then $$x_{\pi^x (i)} \geq x_{\pi^x (j)} \geq y_{\pi^x (j)} \quad \forall j\in\{i,\ldots, N\}.$$ Hence $$\vert \{ k\in\{1,\ldots,N\} : x_{\pi^x (i)} \geq y_k \} \vert \geq \vert\{i,\ldots,N\}\vert = N+1-i .$$ This yields directly $x_{\pi^x (i)} \geq y_{\pi^y (i)}$.