Question

Suppose that \(a_{1} \leq a_{2} \leq \cdots \leq a_{n}\) and \(b_{1} \leq b_{2} \leq \cdots \leq b_{n} .\) Let \(\left\\{\ell_{1}, \ell_{2}, \ldots \ell_{n}\right\\}\) be a permutation of \(\\{1,2, \ldots, n\\},\) and define $$ Q\left(\ell_{1}, \ell_{2}, \ldots, \ell_{n}\right)=\sum_{i=1}^{n}\left(a_{i}-b_{\ell_{i}}\right)^{2} $$ Show that $$ Q\left(\ell_{1}, \ell_{2}, \ldots, \ell_{n}\right) \geq Q(1,2, \ldots, n) $$

Short answer

Question: Prove that for any permutation \(\ell_i\), the value of the function \(Q\) defined by \[Q\left(\ell_{1}, \ell_{2}, \ldots, \ell_{n}\right)=\sum_{i=1}^{n}\left(a_{i}-b_{\ell_{i}}\right)^{2}\] is minimized when we choose the permutation \(\ell_i = i\), for all \(1\leq i\leq n\), where the sequences \(a_i\) and \(b_i\) are sorted in non-decreasing order.

Step-by-step solution

Understand the permutation function

The function \(Q\) defined in the problem takes a permutation \(\left\\{ \ell_1, \ell_2, ..., \ell_n \right\\}\) and computes the sum of the squared differences between corresponding \(a\) and \(b\) elements: $$Q\left(\ell_{1}, \ell_{2}, \ldots, \ell_{n}\right)=\sum_{i=1}^{n}\left(a_{i}-b_{\ell_{i}}\right)^{2}$$

Rewrite the inequality

Our goal is to show that for any permutation \(\ell_i\), the value of \(Q(\ell_1, \ell_2, \ldots, \ell_n) \geq Q(1, 2, \ldots, n)\). Firstly, rewrite the inequality as follows: $$Q(\ell_1,\ell_2,\dots,\ell_n)-Q(1,2,\dots,n) \ge 0$$

Introduce the inequality

Now, let's plug the formula for \(Q(\ell_1,\ell_2,\dots,\ell_n)\) and \(Q(1,2,\dots,n)\) into the inequality from Step 2: $$\sum_{i=1}^{n}(a_i - b_{\ell_i})^2 - \sum_{i=1}^n (a_i - b_i)^2 \ge 0$$

Group the sums

Combine the sums and then rearrange the terms: $$\sum_{i=1}^{n} \left[(a_i - b_{\ell_i})^2 - (a_i - b_i)^2\right] \ge 0$$

Use the difference of squares

Apply the difference of squares formula to each element in the sum: $$\sum_{i=1}^{n} (a_i - b_{\ell_i} + a_i - b_i)(a_i - b_{\ell_i} - a_i + b_i) \ge 0$$

Simplify

Now simplify the terms inside the sum: $$\sum_{i=1}^{n} (2a_i - b_{\ell_i} - b_i)(b_i - b_{\ell_i}) \ge 0$$

Observe the sign of terms

Notice that the term \((2a_i - b_{\ell_i} - b_i)\) is always non-negative, because \(a_i \le b_i \le b_{\ell_i}\) for all \(i\), as \(\ell_i\) is a permutation of \(\{1,2,\ldots,n\}\) and \(a_i\)'s and \(b_i\)'s are sorted in non-decreasing order. Similarly, the term \((b_i - b_{\ell_i})\) is non-positive, because \(b_i \le b_{\ell_i}\) as well.

Prove the inequality

Since \((2a_i - b_{\ell_i} - b_i)\) is non-negative and \((b_i - b_{\ell_i})\) is non-positive for all \(i\), the product of these terms is non-negative. Hence, their sum is also non-negative. Thus, the inequality has been proved: $$\sum_{i=1}^{n} (2a_i - b_{\ell_i} - b_i)(b_i - b_{\ell_i}) \ge 0$$ And we get the desired result \(Q(\ell_1,\ell_2,\dots,\ell_n) \ge Q(1,2\dots,n)\) for any permutation \(\ell_i\).

Key concepts

Permutations

Permutations are a fundamental concept in mathematics and are essential when dealing with sequences or lists. A permutation is an arrangement of all the members of a set in a certain sequence or order. If you have a list of numbers or items, any reordering of this list is a permutation. For example, the set \(\{1, 2, 3\}\) has six possible permutations: (1, 2, 3), (1, 3, 2), (2, 1, 3), (2, 3, 1), (3, 1, 2), and (3, 2, 1). In the context of the exercise, we're dealing with permutations of indices. The function \(Q\) computes a certain value based on a permutation \(\{ \ell_1, \ell_2, \ldots, \ell_n \}\) of the indices \(\{1, 2, \ldots, n\}\). This means each \(\ell_i\) is a unique number from 1 to n, and all \(n\) numbers are used exactly once. Permutations are crucial for exploring all possible ways a sequence can be arranged, which is key to solving many types of mathematical problems, including optimizations and proofs like the one we are considering. By understanding permutations, we access a powerful tool for dealing with comparisons and orderings in sequences.

Squared Differences

Squared differences are a mathematical way to measure how far apart two values are. When we talk about the squared difference between two numbers, \(a\) and \(b\), we mean \((a - b)^2\). This calculation takes their difference and squares it.

Why Square the Difference?

Squaring a difference has several advantages:

• It ensures that the result is always non-negative. Negative differences become positive when squared, which is useful for measurement purposes as we often want to ignore the direction of the difference and focus on magnitude.
• Squaring penalizes larger differences more than smaller ones. If you double the difference, the squared difference becomes four times larger, emphasizing significant discrepancies.

In our exercise, the squared differences measure how well elements \(a_i\) align with permutation-altered elements \(b_{\ell_i}\). The proof then involves comparing this alignment to that of a direct, non-permuted arrangement \((b_1, b_2, \ldots, b_n)\), which is shown to generally minimize these discrepancies.

Applications in Inequalities

Using squared differences is common in inequality proofs because it gives us a clear, quantifiable measure of closeness between sequences or functions. In this context, we're proving an inequality that demonstrates how sequential, non-permuted pairings of sorted lists generally provide smaller squared differences than permuted ones.

Non-negative Sum

A non-negative sum is a sum where all the terms add up to a value that is zero or greater. Non-negative sums are important because they can help prove inequalities. In the exercise at hand, we show that the sum of certain terms is non-negative, which leads to proving the original inequality posed in the problem.

How Does it Work?

Our task is to show that the sum of products of terms \((2a_i - b_{\ell_i} - b_i)(b_i - b_{\ell_i})\) results in a non-negative value. Here's how:

• The term \((2a_i - b_{\ell_i} - b_i)\) can be non-negative due to the nature of the inequality. We know from the problem setup that \(a_i\) is small enough when compared to \(b_i\) and \(b_{\ell_i}\) that this holds true.
• The term \((b_i - b_{\ell_i})\) is non-positive, but when it's multiplied by the already established non-negative value of \(2a_i - b_{\ell_i} - b_i\), the product stays non-negative.

When you add these non-negative results across the entire sequence, the result is a non-negative sum, confirming the desired inequality \(Q(\ell_1,\ell_2,\ldots,\ell_n) \ge Q(1,2,\ldots,n)\). Non-negative sums provide a straightforward path to validate proofs involving inequalities, making them incredibly useful in mathematics.