0
$\begingroup$

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].

$\endgroup$
0
$\begingroup$

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.

The conclusion follows.

$\endgroup$
  • $\begingroup$ Thank you, but regarding your second argument I think that topological ordering of the vertices does not generally means that the adjacency matrix would be triangular. Consider for example the simple case 2--> 1--> 3. $\endgroup$ – Catherine56 May 17 '16 at 6:58
  • $\begingroup$ I'm saying that we relabel the vertices in topological order. By definition, your case would then be $1\to 2\to 3$. $\endgroup$ – Omnomnomnom May 17 '16 at 11:30
  • $\begingroup$ What I'm saying at the end is that if the adjacency matrix is nilpotent under some relabeling, then this holds regardless of the order in which one labels the vertices. So, the adjacency matrix with respect to the original ordering must also be nilpotent. $\endgroup$ – Omnomnomnom May 17 '16 at 11:34

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.