1
$\begingroup$

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.

$\endgroup$
1
  • $\begingroup$ I don't understand your tables. Please elaborate to clarify. $\endgroup$
    – amsmath
    Oct 13, 2019 at 23:24

1 Answer 1

1
$\begingroup$

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}

$\endgroup$
1
  • $\begingroup$ 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. $\endgroup$
    – Treeman
    Oct 14, 2019 at 23:37

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.