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?
Best Answer
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$).