Is there an algorithm to rearrange a matrix into block diagonal form, given that the matrix is block diagonal in nature but randomized with an unwise choice of basis?In particular, are there any python modules for this?
Rearrange an ordinary matrix to block diagonal form
matrices;python
Is the matrix sparse or dense? Is it symmetric?I'm assuming by rearrange you mean permute the entries, rather than apply some more general similarity transformation to the matrix. In that case, you can think of an $n\times n$ matrix $A$ as graph; two vertices $i$, $j$ of this graph are connected if $A_{ij} \neq 0$. If the matrix is not symmetric, then the edges are directed, but it's the same idea.The fact that your matrix is (up to a reordering) block diagonal means that the graph isn't connected, and finding which vertices should be in a block together amounts to finding the connected components of the graph. You can do this with a breadth-first search. Since the reverse Cuthill-McKee ordering of a matrix is essentially a breadth-first search, you can probably find someone's Python code for the RCM ordering and use it directly or modify it for your purposes.