I have a sparse square non-symmetrix $n \times n$ matrix $A$ with entries $$A_{ij} \in \left\{ 0, \frac12, 1, 2 \right\}$$ I am interested in applying a permutation $\sigma \in S_n$ to give elements $A_{\sigma(i) \sigma(j)}$ in such a way that I "maximally block-diagonalise" $A$.
What I mean by this is something like the following. Firstly, block-diagonalise where possible. This problem appears to me to be well-defined and I think it should have an algorithmic solution. Is this true? What is the name of the algorithm?
I guess this would be a part of such an algorithm, but is there a straightforward way for me to check, given such a matrix is it block-diagonalisable by permutation?
So now after applying such an algorithm I would have a set of block matrices that $A$ decomposes into. So let's reuse my original definition, and now assume that $A$ still has zeros, but is no longer block diagonalizable by permutation. I'm interested in going further, and making this $A$ to be "as block diagonal as possible". For example, suppose I could decompose this $A$ so that it is almost block diagonal, but there is a single $1$ in one of the elements of the off-diagonal blocks that are normally all $0$. Then I would say that this matrix is "more block diagonal" than if that element were a $2$, or if there were two or more such elements equal to $1$.
Is there an algorithm to produce a "maximally block diagonalised" form for a matrix that cannot be completely block diagonalised, as I have described? Would it be necessary to choose a metric to describe which matrices are more block diagonal than which others, or is there some canonical definition?