Directed graph and cycles

Question

Reading this article on graph cycles, then we have that for a (undirected?) graph G, given A as adjacency matrix

$trace(A^i) \ne 0 \iff $ exists a cycle of lenght i in G

Does the same applies to a directed graph (digraph) D?

Answer 1

Yes it does. From wikipedia

If $A$ is the adjacency matrix of the directed or undirected graph $G$, then the matrix $A^n$ (i.e., the matrix product of $n$ copies of $A$) has an interesting interpretation: the element $(i, j)$ gives the number of (directed or undirected) walks of length $n$ from vertex $i$ to vertex $j$.

for example, that the number of triangles in an undirected graph $G$ is exactly the trace of $A^3$ divided by $6$.

Answer 2

The trace of $A^n$ can be written as $\sum_{i_1,\dots, i_{n}} A_{i_1,i_2}A_{i_2,i_3}\dots A_{i_{n},i_{1}} $

As the adjacency matrix has no negative entries, this is nonzero if and only if one of the term in the sum is nonzero. If that is the case, then the corresponding indices $(i_1,\dots, i_{n})$ do form a cycle of length $n$ in $G$.

And more precisely, as stated on Wikipedia, as non zero terms are all equal to $1$ (if we forbid multiple edges), the trace counts for the exact number of cycles in the graph (note that if a cycle exists with both orientations, it is counted twice. Also, cycles here has a "beginning". Each one is counted $n$th times if you forget the starting point... ). Note that this in fact is also true if multiple edges are allowed.