Start with a complete graph $K_n$ and assign each edge a direction or delete the edge. Then consider the 4th and 5th powers of the adjacency matrix $A$.
Am I correct in thinking that the trace of $A^4$ is a multiple of $4$ and the trace of $A^5$ is a multiple of $5$? My thinking is that all non-zero elements in the trace have originated from a 4-cycle or 5-cycle.
Also is there a way to find the cycle from the powers of the adjacency matrix.
Best Answer
Your hypothesis is essentially correct. $A^k_{u,v}$ gives the number of (directed) walks from $u$ to $v$ of length $k$. Therefore, the trace is the number of (directed) closed walks if you consider the origin and terminus of the closed walk. So the "same" set of four arcs would be counted as four different closed walk.
(This isn't part of your question, but one thing we need to be careful of is whether all of those closed walks are cycles. For instance, a diagonal entry in $A^6$ might represent a cycle of length $6$, and it could also represent a cycle of length $3$ that was traversed twice. But, since your underlying graph is simple, you should be able to convince yourself that this won't be an issue for $A^4$ and $A^5$.)
I'm going to say that pulling the cycles out of the powers of the adjacency matrix is not possible. Matrix multiplication pulls together so many terms that you're just not going to want to put that toothpaste back in the tube. To be clear, you could, but it's just tracking each entry of each matrix multiplication. Modifying Dijkstra's algorithm would be a better strategy.