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?
$\begingroup$
$\endgroup$
3
-
2$\begingroup$ Do you want to "rearrange" the matrix by a permutation or by a change of basis? $\endgroup$– Christian ClasonMar 9, 2013 at 21:20
-
1$\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$– MachineMar 10, 2013 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 ThomaMar 31, 2017 at 15:24
Add a comment
|
2 Answers
$\begingroup$
$\endgroup$
1
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.
answered Mar 9, 2013 at 22:53
-
$\begingroup$ Thanks! Assume the matrix is sparse and symmetric (hermitian). $\endgroup$– MachineMar 10, 2013 at 4:12
$\begingroup$
$\endgroup$
4
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.
answered Mar 9, 2013 at 18:24
-
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$ Mar 9, 2013 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$ Mar 9, 2013 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$ Mar 10, 2013 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$ Mar 10, 2013 at 8:27