cycle in a directed graph Hi I saw in an R forum the answer: 
“If the graph has n nodes and is represented by an adjacency matrix, you can square the matrix (log_2 n)+1 times. Then you can multiply the matrix element-wise by its transpose. The positive entries in the 7th row will tell you all nodes sharing a cycle with node 7.  This assumes all edge weights are positive."
I’m a PhD student working on my research and I need to check for cycles in a directed graph to make sure it is a DAG. The answer given is extremely useful but I need the theorem statement, or a reference. Does anyone has a book reference where this is stated or a paper?
Thanks!
Daniela.
PS Unfortunately the people from the R forum didn't let me to ask the question there
 A: If $A$ is the adjacency matrix of a directed graph, it is easy to prove by induction that the $ij$ entry of $A^k$ counts the number of directed walks from $v_i$ to $v_j$ of lenght $k$.
Then, the following is an immediate consequence of this:
Lemma Let $D$ be a digraph with $n$ vertices. Then $D$ is acyclic if and only if 
$$tr(A)+tr(A^2)+...+tr(A^n)=0$$
Proof:
$\Rightarrow$. Assume by contradiction that $tr(A)+tr(A^2)+...+tr(A^n) \neq 0$. Then $tr(A^k) \neq 0$ for some $k$. This means that there exists an $i$ so that the $ii$ entry of $A^k$ is positive. 
Hence there are directed walks from $v_i$ to $v_i$.
This shows that $D$ has closed directed walks, and it is easy to prove that any minimal closed directed walk is a directed cycle. Contradiction.
$\Leftarrow$: Assume by contradiction that $D$ has a directed cycle. 
This cycle has length $k \leq n$. 
If $v_i$ is a vertex on the cycle, then the cycle is a directed walk from $v_i$ to $v_i$ of length $k$. This shows that the $ii$ entry of $A^k$ is at least $1$, and hence $tr(A^k) \geq 1$.
By non-negativity of the matrices, we get:
$$tr(A)+tr(A^2)+...+tr(A^n)\geq 1$$
contradiction.
P.S. I think it is also easy to prove that this is equivalent to $A$ being nilpotent, and hence to all eigenvalues of $A$ being $0$. 
A: Here is a simpler condition to check:
Lemma Let $D$ be a digraph with n vertices. Then $D$ is acyclic if and only if $A^{n}=0$.
Proof: Since $A$ is an $n \times n$ matrix, we have $A^{n+1}=0 \Rightarrow A$ is nilpotent $\Rightarrow A^n =0$. 
$\Rightarrow$. Assume by contradiction that $A^{n} \neq 0$. Then, by the above, $A^{n+1} \neq 0$. It therefore has an entry $ij$ which is non zero.
This implies that $D$ has a directed walk of lenght $n+1$. This walk must then contain repeated vertices (as we only have n vertices) and thus contains a smaller closed directed walk. As before, any graph which contains a closed directed walk automatically contains a directed cycle.
$\Leftarrow:$ Assume by contradiction that $D$ contains a directed cycle $v_1-> v_2 ->...-> v_k -> v_1 $.
Then by following the cycle around (multiple times if needed) we get a directed walk of lenght $n$:
$$v_1-> v_2 ->...-> v_k -> v_1 -> v_2-> v_2 -> ....-> v_?$$
This shows that the $1?$ entry of $A^n$ is non-zero, which contradicts $A^n \neq 0$.
