# Mathematical method for separating non-overlapping rows/columns in a symmetric matrix

I have a matrix that is effectively a non-directed adjacency matrix for a graph. My problem is to find all disconnected subgraphs. I know this can be done computationally by first creating a graph representation and then performing a flood fill algorithm to find the subgraphs, however, I was hoping there might be a mathematical way to do this on just the matrix.

For example, I have the following symmetric adjacency matrix: $$\begin{bmatrix} 1 & 1 & 0 & 0 & 1 & 0 \\ 1 & 1 & 0 & 0 & 0 & 0 \\ 0 & 0 & 1 & 1 & 0 & 0 \\ 0 & 0 & 1 & 1 & 0 & 0 \\ 1 & 0 & 0 & 0 & 1 & 1 \\ 0 & 0 & 0 & 0 & 1 & 1 \\ \end{bmatrix}$$

Where each row $i$ and columns $j$ correspond to whether there is an edge between node $i$ and node $j$ represented by $1$ if there is an edge, $0$ if not.

This particular matrix represents a graph with two disconnected subgraphs, that is: $$n_2 \leftrightarrow n_1 \leftrightarrow n_5 \leftrightarrow n_6 \textrm{ and } n_3 \leftrightarrow n_4$$

Every node is connected to itself although this can be changed if necessary.

If I could find a way to separate out any rows/columns that do not overlap using some matrix operations, the resulting subgraphs could be extracted computationally.

Is this possible? Or am I stuck using a computational method on a graph?

• I'm pretty sure that any algorithm using matrix operations will be essentially equivalent to the graph theory algorithms that find components. Maybe someone's answer will surprise both of us. – Ethan Bolker Aug 23 '17 at 16:28
• Start with an identity matrix and keep right multiplying it with the adjacency matrix (maybe binary multiplication would be better). You'll end with a matrix whose independent rows are the nodes in the connected subgraphs. – N74 Aug 23 '17 at 19:29
• It should be enough to raise the adjacency matrix to its dimension. – N74 Aug 24 '17 at 5:29
• You could find the kernel of the Laplacian matrix, which can be computed from the adjacency matrix $A$ via $L=D-A=\operatorname{diag}(A\mathbf 1)-A$. Surprisingly to me, computing matrix powers appears to be more efficient, at least for the graphs that I tried. – amd Aug 29 '17 at 8:01
• I expected it to be more efficient, too, but when I tested a few methods in Mathematica with your matrix and some slightly larger ones, computing $A^N$ and then extracting the unique rows/columns (which is basically a flood fill) always turned out to be faster. If the graph is highly connected, the matrix powers will likely stabilize after only a few iterations, and, as you say, computing powers of sparse matrices has optimization opportunities. I’m reluctant to make any conclusions about which is more efficient without a broader test. – amd Aug 29 '17 at 18:22

You can do what’s effectively a parallel flood fill by computing powers of the incidence matrix $A$ until the zero entries stabilize. Each of the linearly independent rows/columns of the result represents a connected component of the graph, with nonzero entries in positions that correspond to the nodes in that component.
This will require $d-1$ iterations, where $d$ is the diameter of the graph. However, the process is guaranteed to stabilize in at most $n-1$ iterations, where $n$ is the order of the matrix, so instead of testing each iteration for changes, you could simply compute the $(n-1)$th power of the adjacency matrix. At first glance this seems like it might not scale well, but for your example computing $A^6$ and extracting unique rows turned out the be faster in Mathematica than other methods.
Another approach is to compute the null space of the graph’s Laplacian matrix $L$, which is easily derived from the adjacency matrix: $L=D-A=\operatorname{diag}(A\mathbf 1)-A$. Here, $D$ is the degree matrix, a diagonal matrix with entries equal to the degree of each node, and $\mathbf 1$ is the vector of all $1$s. $A\mathbf 1$ is thus just the vector of row sums of $A$. The null space is spanned by a set of mutually exclusive (orthogonal) incidence vectors, one for each connected component of the graph.
To illustrate with your adjacency matrix $A$, using binary multiplication we have $$A^3=A^4=\begin{bmatrix}1&1&0&0&1&1\\1&1&0&0&1&1\\0&0&1&1&0&0\\0&0&1&1&0&0\\1&1&0&0&1&1\\1&1&0&0&1&1\end{bmatrix}.$$ The unique rows are $(1,1,0,0,1,1)$ and $(0,0,1,1,0,0)$, which correspond to the two connected subgraphs you identify in your question.
The degree matrix is $\operatorname{diag}(3,2,2,2,3,2)$, so the Laplacian is $$L=\left[\begin{array}{r} 2&-1&0&0&-1&0 \\ -1&1&0&0&0&0 \\ 0&0&1&-1&0&0 \\ 0&0&-1&1&0&0 \\ -1&0&0&0&2&-1 \\ 0&0&0&0&-1&1 \end{array}\right].$$ Row-reduction results in $$\left[\begin{array}{r} 1&0&0&0&0&-1 \\ 0&1&0&0&0&-1 \\ 0&0&1&-1&0&0 \\ 0&0&0&0&1&-1 \\ 0&0&0&0&0&0 \\ 0&0&0&0&0&0 \end{array}\right]$$ from which we can read the kernel basis vectors $(1,1,0,0,1,1)^T$ and $(0,0,1,1,0,0)^T$.