1

Given a permutation of size N, you can create a distance matrix that shows the distance between each element to each other element, giving a complete description of the permutation. ie 1,2,3,4 creates \begin{array}{|c|c|c|c|c|} \hline & \textbf{1} & \textbf{2} & \textbf{3} & \textbf{4} \\ \hline \textbf{1} & 0 & 1 & 2 & 3 \\ \hline \textbf{2} & * & 0 & 1 & 2 \\ \hline \textbf{3} & * & * & 0 & 1 \\ \hline \textbf{4} & * & * & * & 0 \\ \hline \end{array} The bold table entries show elements and the body entries are distances between the row and column elements for that cell.

The distance matrix will always have a 0 diagonal and be symmetric, so for the diagonal and symmetric elements will be omitted.

The permutation 1,3,4,2 generates: \begin{array}{|c|c|c|c|} \hline & \textbf{2} & \textbf{3} & \textbf{4} \\ \hline \textbf{1} & 3 & 1 & 2 \\ \hline \textbf{2} & & 2 & 1 \\ \hline \textbf{3} & & & 1 \\ \hline \end{array}

The absolute difference of the two distance matrices is: \begin{array}{|c|c|c|c|} \hline & \textbf{2} & \textbf{3} & \textbf{4} \\ \hline \textbf{1} & 2 & 1 & 1 \\ \hline \textbf{2} & & 1 & 1 \\ \hline \textbf{3} & & & 0 \\ \hline \end{array}

The sum of this difference matrix is 6 (D). The sequence 2,3,1,4 gives a maximum value of D=8 for a permutation of N=4 length.

Given the size of a permutation N, is it possible to find an expression for the maximum possible difference matrix sum? That is D(N)?

I tried some brute force computation methods for this but it becomes very slow once going past around 12 or 13, and hits the memory limits of 32 bit array indexing.

Can someone recommend places to look for leads on this or more specific terms for the problem? I'm not very familiar with math lingo.

Treeman
  • 13

1 Answers1

1

If I understand correctly, this can be formulated as a maximization version of the quadratic assignment problem. I get the following values for $N \le 10$. Please confirm whether these match what you obtained.

 N D(N) 
 1   0 
 2   0 
 3   2 
 4   8 
 5  16 
 6  28 
 7  44 
 8  68 
 9  96 
10 134

I obtained these values via integer linear programming. For $i,j \in \{1,\dots,n\}$, let binary decision variable $x_{i,j}$ indicate whether $i$ appears in position $j$. For $i_1,i_2,j_1,j_2 \in \{1,\dots,n\}$ with $i_1 \not= i_2$ and $j_1 < j_2$, let binary decision variable $y_{i_1,i_2,j_1,j_2}$ represent the product $x_{i_1,j_1}x_{i_2,j_2}$. The problem is to maximize $$\sum_{i_1,i_2,j_1,j_2} \left||i_1-i_2|-|j_1-j_2|\right| y_{i_1,i_2,j_1,j_2}$$ subject to the following constraints: \begin{align} \sum_j x_{i,j} &= 1 &&\text{for all $i$} \\ \sum_i x_{i,j} &= 1 &&\text{for all $j$} \\ y_{i_1,i_2,j_1,j_2} &\le x_{i_1,j_1} &&\text{for all $i_1,i_2,j_1,j_2$} \\ y_{i_1,i_2,j_1,j_2} &\le x_{i_2,j_2} &&\text{for all $i_1,i_2,j_1,j_2$} \\ x_{i,j} &\in \{0,1\} &&\text{for all $i,j$} \\ y_{i_1,i_2,j_1,j_2} &\in \{0,1\} &&\text{for all $i_1,i_2,j_1,j_2$} \end{align}

RobPratt
  • 45,619
  • Your values match what I got. Can you tell me a bit more about your method or where to research? Will mark as solved for now since it answers the question as given. – Treeman Oct 14 '19 at 23:37