minimizing the $\ell_1$ distance between any equal sized vectors

Question

I got an assignment in a course I'm taking that includes proving the following theorem:

let $\mathbf{a, b}\in\mathbb{R}^N$ be ordered vectors s.t $a_i\leq a_j, b_i\leq b_j \;\;\forall\;i\leq j$. In addition, let $\Pi$ be the set of all permutations of the set $\{1,2,\dots,N\}$. Prove that the following equality holds for every $N\geq 1$: $$\min_{\pi\in\Pi}\sum_{k=1}^{N}|a_k-b_{\pi(k)}|=\sum_{k=1}^{N} |a_k-b_k| $$ where $\pi(k)$ is the $k$-th element of some permutation $\pi\in\Pi$.

In other words: the permutation minimizing the $\ell_1$ distance between any equal sized vectors can be found by ordering both of them in a monotonically increasing order.

It was suggested to prove it by induction. The base case ($N=1$) is trivial and immediate. The induction step was a bit more complicated for me, and I hope that someone might help me with it...

Thanks.

Answer 1

Let us deal with the $N=2$ case first. This case reduces to showing $|a_1-b_1|+|a_2-b_2| \leq |a_1-b_2|+|a_2-b_1|$. To this end, let $x=a_1-b_1,y=a_2-b_2$ and $z=a_1-b_2,t=a_2-b_1$. We then have to show that $|x|+|y| \leq |z|+|t|$. If $x$ and $y$ have the same sign, then $|x|+|y|=|x+y|=|z+t| \leq |z|+|t|$ and we are done. If $x\geq 0$ and $y\leq 0$, then $b_1\leq a_1\leq a_2 \leq b_2$ whence $|x|+|y|=x-y=t-z-2(a_2-a_1) \leq t-z \leq |t|+|z|$. Finally, if $x\leq 0$ and $y\leq 0$, then $a_1\leq b_1\leq a_2 \leq a_2$ whence $|x|+|y|=y-x=t-z-2(b_2-b_1) \leq t-z \leq |t|+|z|$.

Let us now explain the general case. Let $\pi\in \Pi$ and $F(\pi)=\sum_{k=1}^{N} |a_k-b_{\pi(k)}|$ ; we must show that $F(\pi) \geq F(\mathsf{id})$. If $\pi$ is the identity, there is nothing to prove. So suppose that $\pi$ is not the identity. Then there are two indices $i<j$ such that $\pi(i)>\pi(j)$. Because of the $N=2$ case, we have

$$ |a_i-b_{\pi(i)}|+|a_j-b_{\pi(j)}| \geq |a_i-b_{\pi(j)}|+|a_j-b_{\pi(i)}| \tag{1} $$

Let $\pi'$ be the permutation which coincides with $\pi$ except that $\pi(i)$ and $\pi(j)$ have been swapped. Then $F(\pi) \geq F(\pi')$ because of (1). If $\pi'$ is the identity we are done, otherwise we can iterate this argument on $\pi'$ again. The process must stop because every time there are more and more pairs $(i,j)$ whose order is preserved by the permutation. This finishes the proof.

Answer 2

Mark the points $A_k=(0,a_k)$ and $B_k=(1,b_k)$ on the lines $x=0$ and $x=1$. Draw the segments $[A_k,B_{\pi(k)}]$ and obtain a bipartite graph $\Gamma$. This graph will now be modified in steps as follows: If $A_1$ is connected to some $B_j$ with $j>1$ then some $A_k$ with $k>1$ is connected to $B_1$. In this case replace the segments $\sigma_1=[A_1,B_j]$ and $\sigma_2=[A_k,B_1]$ by $\sigma_1'=[A_1,B_1]$ and $\sigma_2'=[A_k,B_j]$. It is easily seen that $$\bigl|\Delta y(\sigma_1')\bigr|+\bigl|\Delta y(\sigma_2')\bigr|\leq\bigl|\Delta y(\sigma_1)\bigr|+\bigl|\Delta y(\sigma_2)\bigr|\ .$$ Therefore the total $\Delta y$-length of the modified graph is at most equal to the total $\Delta y$-length of $\Gamma$. Now work your way up until you are left with the bipartite graph $\Gamma^*$ consisting of the segments $[A_k,B_k]$. The total $\Delta y$-length of $\Gamma^*$ is at most equal to the $\Delta y$-length of the $\Gamma$ we started with.