Permute rows of a matrix to minimize total number of inversions of its column vectors

Question

Let $A$ be an $n \times k$ matrix of real numbers.

I'm looking for an exact algorithm to find a permutation of the rows of $A$, in such a way that the total number of inversions found in the resulting $k$ column vectors is minimal. That is, if $B$ is a row-wise permutation of $A$, I want to minimize:

$$ L(B) = \sum _{j = 1} ^k \iota (B ^ j),$$

where $\iota(x)$ is the number of inversions in the array $x$, and $B^j$ denotes the $j$-th column of $B$.

I tried to do some basic research on the topic, but could not find anything particularly relevant. The $k=1$ special case amounts to simple array sorting, and I'm hoping one could generalize some array sorting algorithm to this more general case.

Any hint and/or reference would be very appreciated, thanks!

Side note: in the special application I have in mind, $n$ is small (around $100$), so that any solution with time complexity less than, say, $2^n$, could work for all practical purposes.)

Answer 1

While I do not have an answer, I have given this some thought and would like to share my ideas.

I am making two simplifying assumptions but the general case shouldn't be much harder.

1. All numbers are distinct on each column.
2. $k$ is odd.

Now let $c_{i,j}$ be the number of inversions caused by putting row $i$ above row $j$; that is, the number of columns $l$ for which $A_{i,l} > A_{j,l}$. For the rest of the argument, we can ignore $A$ and work with the matrix $c$. Due to assumption 1, $c_{i,j} + c_{j,i} = k$ for all row pairs. Furthermore, due to assumption 2, $c_{i,j} \neq c_{j,i}$ and exactly one of the two will be smaller than $k/2$. When $c_{i,j} < k/2$, we say that row $i$ dominates row $j$.

Domination among rows can be cyclical as illustrated by the three rows below. Row 1 dominates row 2 (columns 1, 2 and 3 have smaller elements, thus $c_{1,2} = 2$ and $c_{2,1} = 3$), row 2 dominates row 3 and row 3 dominates row 1. Note that, for every pair of rows $i$ and $j$, either $i$ dominates $j$ or viceversa. You can view this as a tournament graph with $n$ nodes.

(1 1 2 3 3)
(2 2 3 1 2)
(3 3 1 2 1)

The task with these notations is to find a permutation of rows $\pi$ which minimizes

$$ \sum_{i<j} c_{\pi(i), \pi(j)}$$

Let us consider what happens if we swap two consecutive elements, $\pi(i)$ and $\pi(i + 1)$. Those elements do not move relative to the other $n-2$, only relative to one another. The total cost changes by

$$ -c_{\pi(i),\pi(i+1)} + c_{\pi(i + 1),\pi(i)} = \\ -c_{\pi(i),\pi(i+1)} + (k - c_{\pi(i),\pi(i + 1)}) = \\ k - 2 \cdot c_{\pi(i),\pi(i + 1)} $$

Since $\pi$ is optimal, it follows that the swap must increase the cost, hence

$$ c_{\pi(i),\pi(i + 1)} < k/2 $$

, in other words row $\pi(i)$ dominates row $\pi(i + 1)$. This holds for every consecutive pair of rows in the permutation. It follows that, if any of the $n$ rows dominates all the others, then no other rows may come before it in $\pi$. It must necessarily be placed first and we can reduce the problem by one row.

This is where I got stuck. If all the rows are part of a cycle in the tournament graph mentioned above, I do not know how to break the tie. Still, the following backtracking algorithm might perform well, depending on how adversarial your data is.

Assume we have filled $\pi(1...i-1)$. If there exists a row that dominates all the remaining rows, place it at position $i$ and recurse. Otherwise, from the remaining rows, iterate among those dominated by $\pi(i-1)$. Place each of them at position $i$ and recurse. Some heuristic might be useful here to prune the backtracking more quickly. For example, we could consider rows in increasing order of

$$\sum_{j \in \mbox{ remaining rows }} c_{i,j}$$

Keep a running cost of the permutation so far. If at any point it exceeds the minimum cost found so far, go back one level.