1
$\begingroup$

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?

$\endgroup$
  • $\begingroup$ What do you mean by "indexes"? $\endgroup$ – José Carlos Santos Jan 28 at 21:37
  • $\begingroup$ corresponding elements of column vectors $\endgroup$ – wklm Jan 28 at 21:37
  • $\begingroup$ I still don't get it. Perhaps that you might try to edit the question and to express yourself more clearly. $\endgroup$ – José Carlos Santos Jan 28 at 21:39
  • $\begingroup$ I'll do it, sorry $\endgroup$ – wklm Jan 28 at 21:40
  • $\begingroup$ The Eigenvectors of a matrix are also Eigenvectors of its powers. $\endgroup$ – Yves Daoust Jan 28 at 21:42
1
$\begingroup$

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.

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.