Sorting multiple columns of a matrix

Question

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.

Answer 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.