Suppose you have an adjacency matrix $A$ for a directed graph $G=\{V,E\}$, so $A_{ij} = 1$ if $V_i\rightarrow V_j \in E$, and $A_{ij}=0$ otherwise. Many properties of the graph can be derived from this adjacency matrix. For instance, $(A^n)_{ij}$ tells you the number of paths of length $n$ going from $V_i$ to $V_j$, and for an undirected graph the number of connected components is equal to the number of eigenvalues of $A$ equal to zero.

Is there a nice linear-algebraic quantity that can tell you whether or not this graph has cycles?

My gut says that $A^* = I + A + A^2 + A^3 + \ldots = (I-A)^{-1}$ being finite (that is, $I-A$ being nonsingular) is a necessary and sufficient condition, because it means there are a finite number of paths of arbitrary length between any two vertices. Is this correct?

  • 3
    $\begingroup$ Being acyclic means that there can be no paths of length $n+1$ where $n=|G|$. On the other hand, if there is a cycle, then there are paths of arbitrary length. So you just need to check $A^{n+1}$ where $n=|G|$ $\endgroup$ – Thomas Andrews May 17 '13 at 21:26

It's necessary but not sufficient. $G$ has no directed cycles iff $A$ is nilpotent. This is a stronger condition than $A$ not having an eigenvalue of $1$ (most graphs don't have eigenvalue $1$).


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.