# Identify coupled rows in a symmetric block diagonal matrix

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.

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 = SparseArrayStronglyConnectedComponents[A]
A[[Join@@p,Join@@p]]

{{10, 17, 18}, {8, 14, 13}, {5, 12, 6}, {4, 7, 9}, {2, 15, 3}, {1, 16, 11}} • Thanks. SparseArrayStronglyConnectedComponents is just what I was looking for. Mar 4, 2018 at 0:58
• Glad to be of help! Mar 4, 2018 at 1:02