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