Prove that the L1 distance between two arrays is minimized when both are sorted

Question

Suppose you are given two arrays of the same length $n$, say $a$ and $b$ containing unique positive integers. The L1 distance between $a$ and $b$ is defined as: $$d_1(a, b) = \sum_{i = 1}^n \lvert a_i - b_i \rvert$$ (assuming 1-indexing for convenience)

You are allowed to permute $a$ and $b$ and the goal is to minimize $d_1(a, b)$, or equivalently find a permutation which minimizes the L1 distance. As a corollary, you also need to prove that there is a unique mapping of elements of $a$ and $b$ for which this minimum is achieved, or equivalently, for a given permutation of $a$, only a unique permutation of $b$ can minimize the L1 distance.

My approach

The first trivial observation I made is that one can keep one of the arrays fixed and permute the other. So without loss of generality, let us keep $a$ and use the permutation where $a$ is sorted in increasing order and permute $b$. Taking several examples leads to the conclusion that $d_1(a, b)$ is minimized when $b$ is also sorted in increasing order. Take a few examples to demonstrate this fact:

1. $a = \{1, 5, 7\}\quad b = \{6, 3, 2\}$. For various permutations of $b$, the L1 distances are:
   • $b = \{2, 3, 6\}$, $d_1(a, b) = 4$
   • $b = \{2, 6, 3\}$, $d_1(a, b) = 6$
   • $b = \{3, 2, 6\}$, $d_1(a, b) = 6$
   • $b = \{3, 6, 2\}$, $d_1(a, b) = 8$
   • $b = \{6, 2, 3\}$, $d_1(a, b) = 13$
   • $b = \{6, 3, 2\}$, $d_1(a, b) = 12$
2. $a = \{1, 4, 5, 9\}\quad b = \{1, 3, 2, 6\}$. By programmatically listing down and calculating the L1 distance of all the permutations of $b$, one can prove that the minimum is achieved for the permutation where $b$ is sorted.

I tried to prove it by contradiction by assuming that $b$ is a sorted permutation, i.e. $b_1 \leq b_2 \leq \ldots b_n$ and $c$ is any other permutation. I am trying to prove that: $$ \left(d_1(a, b) > d_1(a, c) \right) \Rightarrow \text{Contradiction}$$ However, I haven't been able to proceed. How do I prove the claim?

Answer 1

Prove the lemma for arrays in two dimensions. That is, show that if $a_1 > a_2$ and $b_1 > b_2$, then $\vert a_1-b_1\vert + \vert a_2-b_2\vert < \vert a_2-b_1\vert + \vert a_1-b_2\vert $. Possibly there are smart ways to do that. But at worst, you can show this is true by completely enumerating all six possible cases:

• $a_1 > a_2 > b_1 > b_2$
• $a_1 > b_1 > a_2 > b_2$
• $a_1 > b_1 > b_2> a_2$
• $b_1 > a_1 > a_2 > b_2$
• $b_1 > a_1 > b_2 > a_2$
• $b_1 > b_2 > a_1 > a_2$

Once this is done, your approach is now straight forward. Consider a fixed vector $a$ that is already sorted. Now, if $b$ is unsorted, then by the above lemma, there exists a swap that necessarily reduces the $\ell_1$ norm.

Answer 2

Yes, two sorted sequences will always give you the minimum $l_1$ distance. Suppose that is not the case. Without loss of generality, assume that all $a_i$s are sorted but $b_i$s aren't. So there must be two indices, $i$ and $j$ ($i < j$), such that $b_i > b_j$. We will now show that swapping these two values decreases the overall cost, which contradicts the assumption that an unsorted sequence of $b_i$ gives the minimum cost.

Thus, we need to show that $|a_i - b_i| + |a_j - b_j| \ge |a_i - b_j| + |a_j - b_i|$.

Let $a_i + x = a_j$ and $b_j + y = b_i$ for some $x\ge 0$ and $y > 0$.

Now suppose $a_i - b_j \ge 0$. Then we have \begin{aligned} |a_i - b_i| + |a_j - b_j| &= |a_i - b_j - y| + |a_i - b_j + x|\\ &= |a_i - b_j - y| + |a_i - b_j| + x\\ &\ge |a_i - b_j + x - y| + |a_i - b_j|\\ &= |a_i - b_j| + |a_j - b_i| \end{aligned}

Similarly, when $a_i - b_j < 0$, we have \begin{aligned} |a_i - b_i| + |a_j - b_j| &= |a_i - b_j - y| + |a_i - b_j + x|\\ &= |b_j - a_i + y| + |b_j - a_i - x|\\ &\ge |b_j - a_i| + |b_j - a_i - x + y|\\ &= |a_i - b_j| + |a_i - b_j + x - y|\\ &= |a_i - b_j| + |a_j - b_i| \end{aligned}

PS: The idea is based on this post, which asks a similar problem but for the $l_2$ norm.

Answer 3

You can formulate this problem as a weighted version of maximum bipartite matching problem.

For each element $a_i$, create a vertex $u_i$, and for element $b_j$, create a vertex $v_j$. Let us define $U = \{a_i\}$ and $V = \{b_j\}$. Now for every pair of elements $(a_i, b_j)$ put an edge $(u_i, v_j)$ with weight $w_{i,j} = -|a_i - b_j|$. Now solve the maximum weight bipartite matching. This can be solved in polynomial time [ref: Hungarian Algorithm].