Can I find the connected components of a graph using matrix operations on the graph's adjacency matrix?

Question

If I have an adjacency matrix for a graph, can I do a series of matrix operations on the adjacency matrix to find the connected components of the graph?

Answer 1

Yes! Perhaps the easiest way is to obtain the Laplacian matrix and find a basis of its kernel.

In words, call $A$ your adjacency matrix. Obtain the diagonal matrix $D$ of the degrees of each vertex. Set $L=D-A$. Now $\dim \ker L = $ number of connected components. Moreover, the kernel of $L$ is spanned by vectors constant on each connected component.

For example, a block diagonal matrix $A=diag(A_1,\dots,A_n)$, with blocks representing the connected components of your graph, will have an associated Laplacian matrix $L$ with kernel spanned by vectors $v_i=(0,\dots,0,1,\dots,1,0,\dots,0)$ where the string of ones is as long as the number of vertices in $A_i$, and specifically in the entries corresponding to the vertices of that connected component.

EDIT: Edited to more directly answer the original question. Sorry that I misread it earlier!

Answer 2

If the graph is regular, the multiplicity of the largest eigenvalue of the adjacency matrix will provide the same result. Let $X_{1}, ..., X_{n}$ be the connected components of the graph. Then these are the diagonal submatrices of the adjacency matrix. And so $p_{G}(\lambda) = \prod_{i=1}^{n} p_{X_{i}}(\lambda)$, where $p_{G}(\lambda)$ is the characteristic polynomial of $\lambda$.

Since $G$ is $k$-regular, $\lambda = k$ is the dominant eigenvalue of each component as well as of $G$. And so $k$ appears $n$ times.

If $G$ is not regular, then you should use the Laplacian method as described above.

Answer 3

If you want use the adjacency matrix and you need the actual components, not just their number, then a brute force approach is as follows. Suppose the graph has adjacency matrix $A$ and $n$ vertices. Compute $M=(A+I)^n$. Now define vertices $u$ and $v$ to be equivalent if $M_{u,v} \ne 0$. The equivalence classes of this relation are the connected components of the graph.

This works because $M_{u,v}$ is positive if and only if there is a walk of length at most $n-1$ from from $u$ to $v$, and if two vertices are in the same component they are joined by a walk of length at most $n$.

It is not practical because no-one in their right mind would compute such a large power of $A$. It could be made workable, but there are other methods for finding components, e.g., find a spanning forest.