# How to tell if a directed graph is acyclic from the adjacency matrix?

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?

• 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|$ – Thomas Andrews May 17 '13 at 21:26

## 1 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$).