0
$\begingroup$

I have a square matrix that looks like this: $$ \left(\matrix{ 0 & 0 & 17 & 1 \\ 2 & 0 & 1 & 19 \\ 14 & 1 & 0 & 0 \\ 1 & 25 & 2 & 0 }\right) $$

It's obvious that, if I rearranged the columns, the matrix would be "almost-diagonal", in the sense that the sum of off-diagonal elements would be minimized.

Is there a general technique for finding this "most diagonal" column arrangement on matrices bigger than, say, $10\times 10$, but smaller than around $100\times 100$?

A brute-force search over permutations of columns starts to become computationally more intensive around $10\times10$, and really becomes infeasible around $15\times15$, having $k!$ solutions ($k$ being the number of rows/columns).

$\endgroup$
1
  • $\begingroup$ One very significant improvement you can make is to compute for each subset of $k$ of the columns the "cheapest way" to put them in the first $k$ slots. This gets your complexity down to $\mathcal O(2^n p(n))$, where $p$ is some manageable polynomial. That's still very expensive for $100 \times 100$, though. $\endgroup$ Aug 7, 2018 at 9:14

1 Answer 1

3
$\begingroup$

Translating your problem into "How do I pick $k$ elements such that I have one element from each row and one element from each column with maximal sum?" (i.e. focus on the diagonal elements, not the off-diagonal elements), we see that this becomes the assignment problem.

There are algorithms for solving this, for instance the Hungarian algorithm, which are polynomial time and thus scale a lot better than the brute force algorithm. The Hungarian algorithm specifically, is $O(k^4)$ if implemented naively, but it may be optimised to $O(k^3)$. You can read more about both implementations here.

PS. Note that assignment problems are usually phrased as trying to minimize, rather than maximize, the diagonal sum. So you will have to keep that in mind as you implement the algorithms.

$\endgroup$
1
  • $\begingroup$ Great observation, I've actually used the Hungarian algorithm before in an unrelated task. I'll mark this as the answer if no others come in soon. $\endgroup$ Aug 7, 2018 at 9:26

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.