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

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?

• Hint: square the matrix, cube the matrix etc... to power of matrix to number of nodes Jan 16 '15 at 16:24

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!

• In what text would someone find a result such as this? Jan 16 '15 at 17:09
• @PaulSundheim By googling "spectral graph theory book" I found this book by Fan Chung math.ucsd.edu/~fan/cbms.pdf
– Max
Jan 16 '15 at 20:56
• Sorry, but this doesn't quite answer my question. I would like to find the actual connected components, not just how many there are. Thank you, though! Jan 18 '15 at 23:43
• @user2073068 I think slightly better can be done. My memory is failing me, so I can't remember specifics (which is why I didn't explain above), but I think you can find the connected components easily from the Laplacian. Maybe by checking the eigenbasis corresponding to the eigenvalue 0? If I have time to check I will augment my answer.
– Max
Jan 18 '15 at 23:56
• Wow, this is super cool! Thank you so much. To complete the task I was looking at, I ended up just using SciPy's connected_component function, but its interesting to know this anyway. Jan 23 '15 at 3:44

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.

• Hate to necro an old thread, but I think the high power of $M$ is pretty easily computable in $O(n^3 \log n)$ time. Just perform repeated squaring of $M$ for $\lceil \log_2 n\rceil$ iterations.
– MSha
Oct 11 at 17:39
• I did say it could be made workable. Oct 12 at 13:56

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.