# A directed graph is acyclic iff the weight matrix of the graph is nilpotent.

I want to prove the above statement. Firstly, I saw many times the following statement:

"A DAG is acyclic iff the adjacency matrix is nilpotent"

but I cannot find anywhere this proof. I tried to prove it by using the fact that the powers of the adjacency matrix denote the length of the path from one vertex to another and then I constructed a topological ordering of the vertices (I know that a directed graph is acyclic iff its vertices have a topological order). Anyway, it would be useful if anybody could tell me if there is another way to prove this (or any book containing this proof). Secondly, how the above statement can be generalized if the "adjacency" matrix A is a weight matrix of the form: A_{i,j} = a_{i,j} if i and j are connected with an edge and A_{i,j} =0 otherwise, where a_{i,j} \in (0,1].

Let $n$ be the number of vertices.
If $A$ is nilpotent, then $A^n = 0$. In particular, this means that there are no paths of any kind of length $n$. However, if the graph had a cycle, we could produce a path of arbitrarily high length. So, the graph is acyclic.
On the other hand: if a graph is acyclic, consider the adjacency matrix under a topological ordering of the vertices. The resulting matrix is triangular with $0$s on the diagonal and is therefore nilpotent. Note that any other adjacency matrix of the same graph will be similar to this one and will therefore also be nilpotent.
• I'm saying that we relabel the vertices in topological order. By definition, your case would then be $1\to 2\to 3$. – Omnomnomnom May 17 '16 at 11:30