I found an interesting problem based on a project I'm working on at my job. I'd like to share and see if anyone either knows if it is well-known or if anyone has any algorithms or techniques for approaching it:
Let $M$ be an $n \times n$ square matrix. It suffices to consider $M$ to have entries of $0$ and $1$ only and for it to be fairly sparse.
Let's further suppose that $M$ is block-diagonal and that the blocks are $B_1, B_2, \cdots, B_k$, where each block matrix $B_i$ is a $m_i \times m_i$ square matrix. We define the "diagonality" of $M$ to be the smallest sum $\sum_{i = 1}^k m_i^2$ we can achieve
We have to choose the "smallest" such value since we usually have some choice with the size of the $B_i$'s. A $2 \times 2$ identity matrix, for instance, can be viewed as having either one $2 \times 2$ block or two $1 \times 1$ blocks, giving scores of $2^2 + 2^2 = 8$ and $1^2 = 1$ respectively. And so we choose $1$ in this case.
So a diagonal matrix will always have diagonality $n$ while a matrix of all $1$'s will have a diagonality of $n^2$. The nontrivial upper triangular $2 \times 2$ matrix will have diagonality $4$. Etc.
My question is then this: Starting with a fixed matrix $M$, I suppose I am allowed to permute the rows and columns at whim. Equivalently, I am allowed to pre- or post-multiply by any permutation matrix. In doing this, how would I go finding the permutations of the rows and/or columns that minimize the diagonality of the resulting matrix?
For instance, let's take the $3 \times 3$ matrix
$$ \begin{bmatrix} 1 & 0 & 1 \\ 0 & 1 & 0 \\ 0 & 0 & 1 \\ \end{bmatrix} $$
This starts off having diagonality $9$.
I could permute row $1$ and row $2$ to get:
\begin{bmatrix} 0 & 1 & 0 \\ 1 & 0 & 1 \\ 0 & 0 & 1 \\ \end{bmatrix}
And then I can permute column $1$ and column $2$ to get:
\begin{bmatrix} 1 & 0 & 0 \\ 0 & 1 & 1 \\ 0 & 0 & 1 \\ \end{bmatrix}
And the result now has diagonality $5$ rather than $9$.
Obviously, the setup here is my own, so I imagine that if this kind of thing has been explored, it's been explored in greater generality. I'd love to know if anyone can lend me some insight into how I might go about minimizing this quantity.
Here is one approach for a solution. It will require some experience with matrix vectorization and abstraction maturity but it is very powerful.
We search for a permutation matrix $P$, we want this permutation matrix to fulfil a similarity: $PAP^{-1} = C$, where $C$ is a matrix with more punished entries the further from diagonal we come.
$$\min_{P,D}\{\|PAP^{-1}-C\|+\|Wvec(C)\|\}$$
Where $W$ is a diagonal matrix encoding the off-diagonal-cost for each entry. We can enforce a weaker version of the $P$ being permutation matrix to force both it's row sums and column sums to be 1: $$\|S_rvec(P)-1\| , \|S_cvec(P)-1\|$$ Where we assume $S_r,S_c$ are the matrices which perform summing on rows and columns respectively (over our vectorization).
The term $\|PAP^{-1}-C\|$ may look frightening (does not look linear, right?) but remember we can rewrite it to: $\|PA - CP\|$ by multiplying both sides with $P$ from the right.
If we add all of them up and choose norm 2 we can solve this with iterated linear least squares. (I've solved many other similar problems like this so I'm sure it works.)
(Now we have $P$ all over our problem, better book a laundromat, LOL!)