Relation between eigenvectors and powers of a matrix for finding out if a graph is disconnected

Question

I'm looking for a quick way to find out whether a graph is disconnected or not. It is if the sum of powers of it's adjacency matrices is a nonzero matrix. To speed up the process of calculating powers, I want to diagonalize the adjacency matrix and calculate powers of the eigenvalues. If eigenvectors of the adjacency a matrix contain 0 in them, could I assume that the consecutive powers of the matrix will not be nonzero?

Answer 1

This is probably not an ideal strategy for checking if a graph is connected, for a couple of reasons.

First, checking if an $n$-vertex graph is connected by a depth-first search will take $O(n^2)$ time when the graph is stored as an adjacency matrix. This is probably better than you're going to do finding eigenvalues or computing matrix powers.

Second, if you're going to be finding eigenvalues of some matrix, find the eigenvalues of the Laplacian matrix $L_G$ instead. More precisely, find the multiplicity of the $0$ eigenvalue: this tells you the number of connected components $G$ has. This can be done just by row-reducing $L_G$ to put it in row-echelon form, then counting the number of zero rows.

Gaussian elimination takes $O(n^3)$ arithmetic operations, so this is still worse than a non-algebraic approach. However, it is better to do this than to implement a strategy where you have to find all the eigenvalues and then do some more work with them.