Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. Join them; it only takes a minute:

Sign up
Here's how it works:
  1. Anybody can ask a question
  2. Anybody can answer
  3. The best answers are voted up and rise to the top

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?

share|cite|improve this question
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
up vote 2 down vote accepted

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

share|cite|improve this answer

Your Answer


By posting your answer, you agree to the privacy policy and terms of service.

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