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

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?

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.

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.

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].

• This gives an algorithm to solve the problem, however, I already have an algorithm to solve it, i.e. just sort the two arrays and take the sum of absolute difference between the elements. This can be solved in $\mathcal{O}(n \log n)$ as opposed to $\mathcal{O}(n^3)$ which the Hungarian Algorithm takes. The Wikipedia page you mentioned doesn't prove the version I have asked. Could you help me with proving optimality? Commented Jun 14 at 9:30