5
$\begingroup$

Is there a function that identifies rows which are part of independent blocks of a symmetric (square) matrix?

For example, here is a symmetric matrix that is secretly a block-diagonal matrix under suitable exchanges of rows and columns.

mat = {{x2+x6, 0, 0, x6}, {0, x1+x4, x4, 0}, {0, x4, x3+x4, 0}, {x6, 0, 0, x5+x6}}

$$\left( \begin{array}{cccc} \text{x2}+\text{x6} & 0 & 0 & \text{x6} \\ 0 & \text{x1}+\text{x4} & \text{x4} & 0 \\ 0 & \text{x4} & \text{x3}+\text{x4} & 0 \\ \text{x6} & 0 & 0 & \text{x5}+\text{x6} \\ \end{array} \right)$$

Is there a function IdentifyRowsInIndependentBlocks that indicates that rows 1 and 4 are part of a block, and 2 and 3 are part of a block? An output would be something like

IdentifyRowsInIndependentBlocks[mat]
(* {{1,4}, {2,3}} *)

which works for arbitrarily large matrices.

$\endgroup$
5
$\begingroup$

A random block matrix in disguise:

n = 6;
m = 3;
a = Symmetrize /@ RandomReal[{-1, 1}, {n, m, m}];
A0 = ConstantArray[0, {n, n}];
Do[A0[[i, i]] = SparseArray@a[[i]], {i, 1, n}];
plist = PermutationList@RandomPermutation[n m];
A = ArrayFlatten[A0][[plist, plist]];

You are actually looking for the connected components of the graph whose undirected edges are given by A["NonzeroPositions"]. The fast way to compute it (without calling for Graph which has quite some initialization overhead) is somewhat hidden:

p = SparseArray`StronglyConnectedComponents[A]
A[[Join@@p,Join@@p]]

{{10, 17, 18}, {8, 14, 13}, {5, 12, 6}, {4, 7, 9}, {2, 15, 3}, {1, 16, 11}}

enter image description here

$\endgroup$
  • $\begingroup$ Thanks. SparseArray`StronglyConnectedComponents is just what I was looking for. $\endgroup$ – QuantumDot Mar 4 '18 at 0:58
  • $\begingroup$ Glad to be of help! $\endgroup$ – Henrik Schumacher Mar 4 '18 at 1:02

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.