8
$\begingroup$

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?

$\endgroup$
  • 1
    $\begingroup$ Do you want to "rearrange" the matrix by a permutation or by a change of basis? $\endgroup$ – Christian Clason Mar 9 '13 at 21:20
  • $\begingroup$ I originally meant to permute the basis which I think is easy to carry out. The case of changing basis can be done by taking some physical argument if the matrix is a Hamiltonian but for some general matrix, it would be quite hard. $\endgroup$ – Machine Mar 10 '13 at 4:11
  • $\begingroup$ You might be interested in How can I restructure matrices to have non-zero elements close to the diagonal? $\endgroup$ – Martin Thoma Mar 31 '17 at 15:24
7
$\begingroup$

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.

$\endgroup$
  • $\begingroup$ Thanks! Assume the matrix is sparse and symmetric (hermitian). $\endgroup$ – Machine Mar 10 '13 at 4:12
3
$\begingroup$

Every matrix is block-diagonal in a wise choice of basis - this is called the Jordan normal form, and the basis is made up of its generalized eigenvectors. If the matrix is symmetric, this basis is made up of eigenvectors, and you can compute it using, e.g., the QR algorithm. SciPy provides the module linalg.qr to compute the necessary QR decompositions. Otherwise, you could use the singular value decomposition, which can be computed using linalg.svd.

$\endgroup$
  • 2
    $\begingroup$ Using the Jordan normal form is a really bad idea because it is numerically unstable. A better choice would be a Schur decomposition, which is numerically stable, at the cost of rearranging your matrix into one that is upper triangular. $\endgroup$ – Geoff Oxberry Mar 9 '13 at 19:25
  • $\begingroup$ Of course, and I did not suggest to compute it except for symmetric matrices, where it coincides with the Schur decomposition (and it can be stably computed using the QR algorithm). For general nonsymmetric matrices, I don't know of a better approach to diagonalize a matrix than the SVD. $\endgroup$ – Christian Clason Mar 9 '13 at 21:19
  • 2
    $\begingroup$ And that is a good point. I would not say that SVD "diagonalizes" a matrix. While it does yield a decomposition that contains a diagonal matrix, diagonalization is traditionally used to refer to a similarity transformation (or a decomposition based on such a transformation/basis change) that results in a diagonal (or block diagonal) matrix. SVD is not a similarity transformation, although it is an exceptionally useful decomposition. $\endgroup$ – Geoff Oxberry Mar 10 '13 at 1:06
  • $\begingroup$ Point taken (and in that sense not every matrix is diagonalizable). I would also point out that diagonalization by a non-unitary similarity transform can be very unstable. $\endgroup$ – Christian Clason Mar 10 '13 at 8:27

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.