<p>The concept you've described has some similarity to the &quot;sorting permutations by reversals&quot; problem which comes from the field of computational biology. In this problem, you're given a permutation of the numbers 1, 2, ..., n, and the goal is to sort this permutation into increasing order using the fewest number of reversals. Each reversal selects a contiguous segment of the permutation and reverses its order.</p>
<p>However, in your case, you're dealing with more than one dimension (or column), and your cost function is a bit more complex (it's based on the number of times the difference between adjacent entries changes sign). So, it's not exactly the same problem, but it seems to be in the same spirit.</p>
<p>If we simplify the problem to sorting a single permutation by minimum reversals, it's known that this problem is NP-hard. The time complexity of the brute force solution is O(n!), because in the worst case, you might need to try all n! permutations to find the one with the minimum reversals.</p>
<p>Your problem, which involves k columns (or dimensions), is likely to be even harder than this. One might hypothesize that your problem is within the exponential time complexity class due to its combinatorial nature. Therefore, a conservative upper bound would be O((n!)^k), because you might need to try all n! permutations for each of the k columns in the worst case.</p>
<p>However, I should note that this is a very loose upper bound, and it's quite possible that there are more efficient algorithms or tighter bounds.</p>

CC BY-SA 4.0
2023-06-25T08:20:30.730Z
2023-06-25T08:20:30.730Z
tomasantunes
<p>Let <span class="math-container">$A \in \mathbb{R}^{n \times k}$</span> be a matrix where each column contains all of the numbers from <span class="math-container">$\{1,\dots,n\}$</span> in some arbitrary order. For example, if <span class="math-container">$n=3, k=2$</span>, we could have
<span class="math-container">$$ A =
 \begin{pmatrix} 
 1 &amp; 3 \\
 3 &amp; 1 \\
 2 &amp; 2 \\
 \end{pmatrix}
$$</span>
I am now allowed to permute rows of <span class="math-container">$A$</span> with the goal of making the entries of the new matrix <span class="math-container">$A'$</span> as ''monotone'' as possible in each column. By that I mean that if I were to interpolate between the points of each column vector, the slope of the interpolating function would change sign as seldom as possible for each. Formally, we could minimize
<span class="math-container">$$L(A') = \sum_{i=1}^{k} \sum_{j=3}^{n} 1 \Big(sign(A'_{i,j} - A'_{i,j-1}) \neq sign(A'_{i,j-1} - A'_{i,j-2}) \Big)$$</span>
I am now interested in how bad this may be depending on <span class="math-container">$n$</span> and <span class="math-container">$k$</span>. Obviously, for <span class="math-container">$k=1$</span> we can get <span class="math-container">$L=0$</span> by simply sorting the only column.</p>
<p>Is there a better way to look at this problem and does it perhaps have an official name? I would like to learn more about worst case bounds.</p>

<co.combinatorics><matrices><sorting>
Sorting multiple columns of a matrix
Claudio Moneo
# Sorting multiple columns of a matrix

(Asked by: username_0 on 2022-05-03)

Let $A \in \mathbb{R}^{n \times k}$ be a matrix where each column contains all of the numbers from $\{1,\dots,n\}$ in some arbitrary order. For example, if $n=3, k=2$, we could have
$$ A =
\begin{pmatrix}
1 & 3 \\
3 & 1 \\
2 & 2 \\
\end{pmatrix}
$$
I am now allowed to permute rows of $A$ with the goal of making the entries of the new matrix $A'$ as ''monotone'' as possible in each column. By that I mean that if I were to interpolate between the points of each column vector, the slope of the interpolating function would change sign as seldom as possible for each. Formally, we could minimize
$$L(A') = \sum\_{i=1}^{k} \sum\_{j=3}^{n} 1 \Big(sign(A'\_{i,j} - A'\_{i,j-1}) \neq sign(A'\_{i,j-1} - A'\_{i,j-2}) \Big)$$
I am now interested in how bad this may be depending on $n$ and $k$. Obviously, for $k=1$ we can get $L=0$ by simply sorting the only column.

Is there a better way to look at this problem and does it perhaps have an official name? I would like to learn more about worst case bounds.

**Tags:** co.combinatorics, matrices, sorting


---

## 1 answers

### Answer by username_1 on 2023-06-25. Score: -1

The concept you've described has some similarity to the "sorting permutations by reversals" problem which comes from the field of computational biology. In this problem, you're given a permutation of the numbers 1, 2, ..., n, and the goal is to sort this permutation into increasing order using the fewest number of reversals. Each reversal selects a contiguous segment of the permutation and reverses its order.

However, in your case, you're dealing with more than one dimension (or column), and your cost function is a bit more complex (it's based on the number of times the difference between adjacent entries changes sign). So, it's not exactly the same problem, but it seems to be in the same spirit.

If we simplify the problem to sorting a single permutation by minimum reversals, it's known that this problem is NP-hard. The time complexity of the brute force solution is O(n!), because in the worst case, you might need to try all n! permutations to find the one with the minimum reversals.

Your problem, which involves k columns (or dimensions), is likely to be even harder than this. One might hypothesize that your problem is within the exponential time complexity class due to its combinatorial nature. Therefore, a conservative upper bound would be O((n!)^k), because you might need to try all n! permutations for each of the k columns in the worst case.

However, I should note that this is a very loose upper bound, and it's quite possible that there are more efficient algorithms or tighter bounds.


---

