What is the maximum value of $\sum_{i=1}^{n} \vert \sigma(i) - i \vert, $ where $\ \sigma\ $ is a permutation of $\ [n]\ ?$

Question

What is the maximum value of $\ \displaystyle\sum_{i=1}^{n} \vert \sigma(i) - i \vert, $ where $\ \sigma\ $ is a permutation of $\ [n]:= \{1,2,\ldots, n\}\ ?$

Based on a program I ran in Python, the answer seems to be:

$ f(n)= \begin{cases} \frac{n^2 - 1}{2}&\text{if}\, n \text{ odd}\\ \frac{n^2 }{2}&\text{if}\, n \text{ even}\\ \end{cases} $

But my I start getting a memory error for $n=11,$ (which is not surprising as $11!$ is large), so I'm not certain the pattern continues according to that function. Here is my code for $n=8$, which is probably very inefficient:

from itertools import permutations
list8=[a for a in permutations( range(8) )]
'''print(list8)'''
max_list8=0
for x in list8:
    sum_diff = 0
    for i in range(8):
        sum_diff += abs( x[i] - i )
    if sum_diff > max_list8:
        max_list8 = sum_diff
        
print(max_list8)

So, I'm curious if that function above is the correct solution to the problem, and if so, why?

Answer 1

You can consider the more general problem: given numbers $a_1 \le a_2 \le \ldots \le a_n$, and $b_1 \le b_2 \ldots \le b_n$ find the maximum ( and the minimum) of $$\sum_{i=1}^n |a_{\sigma(i)} - b_i|$$ over all $\sigma\in \operatorname{Sym}_n$.

You can reduce it to the case $n=2$. Indeed, for $2$ numbers, the largest value is when the order is reversed, and the smallest when the order is preserved.
To check that: $a_1 \le a_2$ and $b_1 \le b_2$ there are $3$ cases: the intervals $[a_1, a_2]$ and $[b_1, b_2]$ are disjoint ( then the order does not matter), the intervals intersect, and one interval contains the other, these last two cases it's easy to check.

Therefore, for the permutation that reverses the order the sum is maximum, for the indentity permutation it is the minimum ( there may be other permutations that achieve the extremum). Note that if the permutations are comparable in the Bruhat order $\sigma \prec \tau$ then $S(\sigma) \le S(\tau)$.

It is interesting also that the same result holds for quadratic sums ( where it is a consequence of Chebyshev inequalities). It would be interesting to know the case of $$\sum_{i=1}^n |a_{\sigma(i)}- b_{i}|^p $$

$\bf{Added:}$ The case of the $l_p$ norm ($p\ge 1$) is entirely similar. The only analysis required ( for $n=2$ ) is the case of disjoint intervals $[a_1, a_2]$ and $[b_1, b_2]$. But here we see that for positive numbers $x$, $y$, $z$, $t$, with $x+y= z+t$, we have $x^p + y^p \le z^p + t^p$ if $z,t$ are more "extreme" than $x,y$ ( $\min(z,t) \le \min(x,y)$, $\max(z,t) \ge \max(x,y)$).

$\bf{Added:}$ Some details for the "reduction to $n=2$ case". Consider a permutation $\sigma \in S_n$. Assume that there exists $i< j$ such that $\sigma(i) < \sigma(j)$. Now consider the permutation $\tau \colon = \sigma \circ (i,j)$. Note that $\tau(k) = \sigma(k)$, for $k \not \in \{i, j\}$, $\tau(i) = \sigma(j)$, $\tau(j) = \sigma(i)$. From the $n=2$ case we get

$$|a_{\tau(i)} - b_i| + |a_{\tau(j)} - b_{j}| \ge |a_{\sigma(i)} - b_i| + |a_{\sigma(j)} - b_{j}|$$ so $$S(\tau) = \sum_k |a_{\tau(k)} - b_k|\ge S(\sigma) = \sum_k |a_{\sigma(k)}- b_k|$$

Moreover, we have for the number of inversions $n(\cdot)$

$$n(\tau) \ge n(\sigma) + 1$$

Therefore, in a finite number of steps, from any permutation $\sigma$ we reach the reversal permutation $\tau(i) = n+1-i$, with no decrease in the value of $S(\cdot)$. So the maximum is achieved at the reversal.

$\bf{Added:}$ It was at the insistence of @Ingix: that I had to provide a clearer argument. Here is the problem: we have a function from a finite set $$\operatorname{Sym}_n \ni \sigma \mapsto S(\sigma)= \sum_i |a_{\sigma(i)} - b_i|$$

and we want to show that $\sigma= w_0$ ( the longest element), $w_0(i) = n+1-i$ achieves the maximum.

The lemma for $n=2$ only shows this: if $\sigma\ne w_0$, (that is, form some $i< j$ we have $\sigma(i) < \sigma(j)$), then there exists a $\tau$ obtained from $\sigma$ such that $S(\tau) \ge S(\sigma)$ ( note that the inequality might not be strict). Does this prove that the maximum is achieved at $w_0$? Apriori no! We might just go on with $\sigma\mapsto \tau \mapsto \eta\mapsto \cdots $, and and some point the values of $S(\cdot)$ stabilize, and we never reach in this way $w_0$. So necessarily we'll have some cycling. But cycling doe not happen here because there is another variable $n(\sigma)$ that increases. It may not be right away that the number of inversions strictly increases. However, we have another variable that is easily seen to strictly increase: $S_2(\sigma) = \sum_i |a_{\sigma(i)} - b_i|^2$. So now we can modify the problem to this: maximize

$$\sigma \mapsto S_1(\sigma) + \epsilon\cdot S_2(\sigma)$$

Now $\sigma =w_0$ is the unique point of maximum ( assume the values $a_i$ distinct and $b_i$ distinct). From here we take $\epsilon\to 0$ and conclude that $w_0$ is a point of maximum.

Answer 2

Credits to @zwim for the paper they linked.

Define
$N^+ = \{\sigma(i) - i: i \in [n]\land \sigma(i) - i > 0\}$
$N^- = \{\sigma(i) - i : i\in [n]\land \sigma(i) - i < 0\}$
$N^0 = \{\sigma(i) - i: i \in [n]\land \sigma(i) - i = 0\}$. Then we have: $$\sum_{i=1}^n \sigma(i) - i = \sum_{i\in N^+} i + \sum_{i\in N^-} i + \sum_{i\in N^0} i = 0 \\ \implies \sum_{i\in N^+} i + \sum_{i\in N^-} i = 0 \\ \implies \sum_{i\in N^+} i = - \sum_{i\in N^-} i$$ So the sum of all positive entries is the negative of the sum of all the negative entries. Next note that: $$\sum_{i=1}^n |\sigma(i) - i| = \sum_{i\in N^+} |i| + \sum_{i\in N^-} |i| \\ = \left|\sum_{i\in N^+} i\right| + \left|\sum_{i\in N^-} i\right| = 2\left|\sum_{i\in N^+} i\right| = 2\sum_{i\in N^+} i$$ So to maximize $\sum_{i=1}^n |\sigma(i) - i|$, we need to maximize $\sum_{i\in N^+} i$.

Now consider a vector $\vec{V} = \langle\sigma(1) - 1, \sigma(2) - 2, \ldots, \sigma(n) - n\rangle$. Since we just need to maximize the positive entries of $\sigma(i) - i$, we will do this by maximizing the components of the vector $\vec{V}$ in order going from left to right, since in that order we are subtracting the smallest available integer from $[n]$.

The largest possible value for $\sigma(1) - 1$ is $n - 1$. This sets $\sigma(1) = n$. Next, the largest possible value of $\sigma(2) - 2$ occurs when $\sigma(2) = n-1$ which is $n - 3$, continuing on, we see a pattern. Namely $\sigma(i) - i = n - (2i-1)$. Now we can split into the cases where $n$ is even and odd respectively.

If $n$ is even, we just need to find the sum of all terms in $N^+$, so we just need to sum from $i=1$ to $i=\frac{n}{2}$. If we let $S^+$ be the sum of the elements of $N^+$, then writing this out we get: $$n-1 + n-3 + \ldots + 3 + 1 = S^+ = \frac{n^2}{4} = \sum_{i\in N^+} i$$ So for $n$ even we get: $$\max\sum_{n=1}^n |\sigma(i) - i| = 2 S^+ = \frac{n^2}{2}$$

If instead $n$ is odd, then the largest $i$ we can take is $i=\frac{n+1}{2}$, in which case our sum, $S^+$ becomes: $$n - 1 + n - 3 + \ldots + 2 + 0 = \frac{n^2-1}{4} = \sum_{i\in N^+} i$$ So for $n$ odd we get: $$\max\sum_{n=1}^n |\sigma(i) - i| = 2 S^+ = \frac{n^2-1}{2}$$

Answer 3

It is not so hard to see that the reverse permutation $\hat\sigma(k)=n+1-k$ maximizes this displacement. What happens when we switch two of the elements in the reverse permutation? The displacement has to go down, or stay the same. If we switch the number at position $i$, which is $\hat\sigma(i)=n+1-i$ with the number at position $j$ which is $\hat\sigma(j)=n+1-j$ then the displacement of this new permutation is

$$\operatorname{disp}(\hat\sigma\circ (i\leftrightarrow j))=\operatorname{disp}(\hat\sigma)-|\hat{\sigma} (i)-i|-|\hat\sigma(j)-j|+|\hat{\sigma}(i)-j|+|\hat{\sigma}(j)-i| \\ =\operatorname{disp}(\hat{\sigma})-|n+1-2i|-|n+1-2j|+|n+1-i-j|+|n+1-j-i| \\ =\operatorname{disp}(\hat\sigma)+2|n+1-(i+j)|-\bigg(|n+1-2i|+|n+1-2j|\bigg)$$ But, due to the triangle inequality, $$|n+1-2i|+|n+1-2j|\geq |n+1+n+1-2i-2j|=2|n+1-(i+j)|$$ Therefore $$\operatorname{disp}(\hat\sigma\circ (i\leftrightarrow j))\leq \operatorname{disp}(\hat\sigma).$$

Answer 4

You asked me to explain a bit better why $E\big[|\sigma(i)-i|\big]$ is around $n/2$. To me it feels intuitive, but here is the exact calculation. It's too long to fit in a comment.

Observe that $P(|\sigma(i)-i|=k)=\frac{(n-1)!}{n!}=\frac1n$ or $2\frac{(n-1)!}{n!}=\frac2n$, depending on whether $k< i\leqslant n-k$ or not (i.e., whether $k\leqslant t:=\min(n-i,i-1)$ or not). Thus \begin{align*} E\big[|\sigma(i)-i|\big]&=\sum_{k=1}^n k\cdot P(|\sigma(i)-i|=k)\\ &=\sum_{k\leqslant t}k\cdot \frac2n + \sum_{k> t} k\cdot \frac1n\\ &=\frac{n^2+n+t^2+t}{2n} \\ &=\frac n2+O(1) \end{align*} as $n\to\infty$. Consequently, $$E\bigg[\sum_{i=1}^n |\sigma(i)-i|\bigg] = \sum_{i=1}^n E\big[|\sigma(i)-i|\big] = \frac{n^2}2+O(n). $$ This doesn't clearly indicate why the maximum of your sum is what you got, but it feels intuitive that the average case is the same as the worst case (as in most situations when dealing with lists).

Answer 5

I think we can expound on K.defoaite's idea and prove that the reverse permutation maximize $S_{\sigma}= \sum_{i=1}^n |\sigma (i)-i|$

by using the following idea:

Starting from any permutation $\sigma_0$, we construct a sequence of $$\sigma_1,\sigma_2, \cdots, \sigma_k $$ s.t.

$$S_{\sigma_0} \leq S_{\sigma_1} \leq S_{\sigma_2} \leq \cdots \leq S_{\sigma_k}$$

and yet the last $\sigma_k$ is the reverse permutation.

Let $\sigma_0 : [n] \to [n] \text{ }$ be any permutation

Step $(1)$

Case $1(a)$

If $\sigma_0 (1)=n$, define $\sigma_1=\sigma_0$ and go to $(2)$.

Note that $S_{\sigma_1}=S_{\sigma_0}$ since we have done nothing.

Case $1(b)$

If $\sigma_0 (1) \neq n$, then $$\sigma_0 (1)= j\tag{i}\label{eqi}$$

for some $j \lt n$

Also there must exist some $i \gt 1$ s.t. $$\sigma_0 (i)=n\tag{ii}\label{eqii}$$

Now we define a new permutation $\sigma_1 : [n] \to [n] \text{ }$ by swapping the values of $\sigma_0$ at $1$ and $i$.

\begin{cases} \sigma_1(1)=n, & \text{ } \\ \sigma_1(i)=j, & \text{ } \\ \sigma_1(k)=\sigma_0(k) & \text{for $k \neq 1, i$ } \\ \end{cases}

Notice that $$|\sigma_1(1)-1|+|\sigma_1(i)-i|=|n-1|+|j-i| \tag{iii}\label{eqiii}$$

While $$|\sigma_0(1)-1|+|\sigma_0(i)-i|=|j-1|+|n-i| $$ $$=(j-1)+n-i=(n-1)+j-i\tag{iv}\label{eqiv}$$

and

$$|\sigma_0(k)-k|=|\sigma_1(k)-k| \tag{v}\label{eqv}$$ for all other $k $

$(iii)$, $(iv)$ and $(v) \implies$

$$S_{\sigma_0} \leq S_{\sigma_1}$$

Now go to step $(2)$

Step (2)

Now that we have $\sigma_1(1)=n$, we turn our attention to $\sigma_1(n)$. The steps are obvious.

Case $2(a)$

If $\sigma_1 (n)=1$, define $\sigma_2=\sigma_1$ and go to $(3)$.

Case $2(b)$

If not, then $$\sigma_1(n)=j\tag{vi}\label{eqvi}$$ for some $ 1 \lt j \lt n$

Also there exists some $i \neq 1, n$ s.t.

$$\sigma_1(i)=1\tag{vii}\label{eqvii}$$

We swap the values of $\sigma_1(n)$ and $\sigma_1(i)$ as in step $(1)$. That is

\begin{cases} \sigma_2(n)=1, & \text{ } \\ \sigma_2(i)=j, & \text{ } \\ \sigma_2(k)=\sigma_1(k) & \text{for $k \neq 1, i$ } \\ \end{cases}

Note again that

$$|\sigma_2(n)-n|+|\sigma_2(i)-i|=|1-n|+|j-i| \tag{viii}\label{eqviii}$$ while $$|\sigma_1(n)-n|+|\sigma_1(i)-i|=|j-n|+|1-i|$$ $$ =(n-j)+i-1=(n-1)+(i-j)\tag{ix}\label{eqix}$$

and for all other $k $

$$|\sigma_2(k)-k|=|\sigma_1(k)-k| \tag{x}\label{eqx}$$

Similar to step $(1)$, $(viii), (ix)$ and $(x) \implies$

$$S_{\sigma_1} \leq S_{\sigma_2}$$

Go to $(3)$

Step (3)

Note that $\sigma_2(1)=n$ and $\sigma_2(n)=1$. The restriction of $\sigma_2$ on $\{2, 3, \cdots n-1 \}$ is a permutation on $\{2, 3, \cdots n-1 \}$ itself.

Thus we can repeatedly apply the algorithms in steps $(1)$ and $(2)$ above so as to obtain a sequence of permutations

$$\sigma_1,\sigma_2, \cdots, \sigma_k $$ s.t.

$$S_{\sigma_0} \leq S_{\sigma_1} \leq S_{\sigma_2} \leq \cdots \leq S_{\sigma_k}$$

It obviously ends when the last permutation is the reverse permutation, where we cannot go further.

The job is done.