Objective function from a set indexed with permutations

Question

The question posed is as follows:

Prove that $f: \mathbb{R}^n \to \mathbb{R}$ defined by

$f(x) = \operatorname{min}_{\sigma} \sum_{i=1}^{n-1} |x_{\sigma(i)}-x_{\sigma(i+1)}|,$

where the minimum above is over all permutations of $\{1, \dots, n\}$, is convex.

According to the points alloded in the assignment, this is not supposed to be a difficult question. My question is, what does $x_{\sigma(k)}$ with a permutation as an index signify? Are you permuting the components of the coordinates, does this constitute an indexed set of some sorts, is the notation a common means of expressing that this value comes from an ordered subset of $\mathbb{R}^n$ with certain special properties, or something else entirely?

This is a homework assignment, but in the lectures and corresponding slides i found no examples involving anything analogous, so I assume this is something that you are just supposed to know.

Answer 1

The notation $x_i$ is supposed to refer to the $i$th coordinate of a vector $x \in \mathbb{R}^n$. If you think about it, this makes $i \mapsto x_i$ a function from $\lbrace 1, \ldots, n \rbrace$ to $\mathbb{R}$. For example, $(1, 7, -9)$ corresponds to the function that maps $1$ to $1$, $2$ to $7$, and $3$ to $-9$.

The notation $x_{\sigma(i)}$ is therefore a composition of this function with a permutation $\sigma$. So, $\sigma$ mixes up the indices $1, \ldots, n$ in some order, and $(x_{\sigma(1)}, \ldots, x_{\sigma(n)})$ mixes up the vector $x$ by rearranging the corresponding coordinates.

To solidify this, let's compute this function for the vector I used above: $(1, 7, -9)$. Here, $n = 3$, and there are $3! = 6$ permutations: the identity, two rotation permutations $(1 \, 2 \, 3)$ (i.e. $1 \mapsto 2 \mapsto 3 \mapsto 1$) and $(1 \, 3\, 2)$, as well as three reflection permutations, $(1 \, 2)$, $(2 \, 3)$, and $(1 \, 3)$. Applying these (in the listed order) to this vector, we get:

1. $(1, 7, -9)$,
2. $(7, -9, 1)$,
3. $(-9, 1, 7)$,
4. $(7, 1, -9)$,
5. $(1, -9, 7)$,
6. $(-9, 7, 1)$.

So, in each of the $6$ cases, we can compute the absolute sum of the difference of consecutive terms, as per the definition of $f$:

1. $|1 - 7| + |7 - (-9)| = 22$
2. $|7 - (-9)| + |-9 - 1| = 26$
3. $|-9 - 1| + |1 - 7| = 16$
4. $|7 - 1| + |1 - (-9)| = 16$
5. $|1 - (-9)| + |-9 - 7| = 26$
6. $|-9 - 7| + |7 - 1| = 22$

So $f(1,7,-9) = 16$. I hope the definition of $f$ is clear now. Good luck with your homework!

Answer 2

Unfortunately, many problems in tests are of the variety that if you know the trick, the problem is easy, otherwise it is an exercise in creative thinking. This is such a problem.

The 'aha' moment is to see that, for a fixed $x$, the $\min$ is attained when the selected permulation $\sigma^*$ orders the $x_k$ such that $x_{\sigma^*(1)} \le \cdots \le x_{\sigma^*(n)}$, in which case $f(x) = \min_{\sigma} \sum_{i=1}^{n-1} |x_{\sigma(i)}-x_{\sigma(i+1)}| = x_{\sigma^*(n)} - x_{\sigma^*(1)} $.

To confirm that this is indeed the $\min$, suppose $\sigma$ is another permutation and suppose $\sigma(i),\sigma(j)$ are the indices of the (a) smallest and largest element of the $x_k$. Let $I$ be the set of indices including $\sigma(i),\sigma(j)$ and all integers in between. Then (please excuse the sloppy choice of indices) $x_{\sigma(j)} - x_{\sigma(i)} = | x_{\sigma(j)} - x_{\sigma(i)} | \le \sum_{k=\inf I}^{\sup I -1} | x_{\sigma(k)} - x_{\sigma(k+1)} | \le \sum_{i=1}^{n-1} |x_{\sigma(i)}-x_{\sigma(i+1)}|$.

Hence we have $f(x) = \max_{i,j} (x_i - x_j)$, the $\max$ of a finite collection of linear (hence convex) functions from which it follows that $f$ is convex.