Take the 2-minute tour ×
Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. It's 100% free, no registration required.

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|improve this question
3  
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
add comment

1 Answer

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|improve this answer
add comment

Your Answer

 
discard

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.