# Rearranging columns of an "almost diagonal" matrix

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

• 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. Aug 7, 2018 at 9:14

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.