How to find a permutation matrix to turn a general hermitian matrix into a block diagonal one?
조회 수: 11(최근 30일)
Christine Tobler 2022년 5월 18일
First, we should keep in mind that the task is really to find a representation of A with as small blocks on the diagonal as possible. After all, we can always treat a matrix as block diagonal with one big block that's just the whole matrix.
One way you can think about this is to treat the matrix as an undirected graph: if A(i, j) is non-zero, there is an edge connecting node i and node j. We can then get the connected components of this graph (two nodes are in the same component only if there is a path connecting them). The nodes in each connected components represent the rows / columns of one diagonal block:
H = [1, 0, -1i;
0, 1, 0;
1i, 0, 1];
g = graph(H ~= 0);
nodeToComponent = conncomp(g) % nodeToComponent(i) gives component number of node i
Why is there this mapping? If we try to split up a connected component into smaller blocks, this isn't possible because there is always an edge connecting a node in proposed new component A with another node in proposed new component B. In terms of diagonal blocks, that would mean that H(i, j) ~=0 for i in proposed diagonal block A and j in proposed diagonal block B - so this couldn't be seen as a diagonal block.
You can get a permutation vector from
[nodeToComponentSorted, p] = sort(nodeToComponent)