# Algebraic characterisation of directed acyclic graphs

Any characterization based on the adjacency matrix for directed acyclic graphs (DAG)? An undirected graph could be simply characterized by saying that its adjacency matrix is symmetric. What about a DAG?

-
The adjacency matrix is nilpontent. – Mariano Suárez-Alvarez Oct 26 '12 at 18:32
@Mariano: I decided to delete my answer since yours is so much more succinct. – Patricia Hersh Oct 26 '12 at 18:57
Ah! But yours was an explanation! – Mariano Suárez-Alvarez Oct 27 '12 at 0:06
@Mariano: Ok, I'll put it back. – Patricia Hersh Oct 27 '12 at 1:18

Given a finite, directed graph, it will be a DAG if and only if you can conjugate its adjacency matrix $A$ by a permutation matrix to get an upper triangular matrix. The idea is to index the rows and likewise the columns of $A$ by the vertices of the graph. Conjugating by a permutation matrix amounts to simultaneously permuting rows and columns in the same way, i.e. choosing a new ordering on the vertices of the graph. A finite directed graph is acyclic if and only if you can put a total order on its vertices such that the directed edges always go from the earlier vertex to the later vertex. This is equivalent to the adjacency matrix with respect to this vertex ordering being upper triangular.
Alternatively, one can simply raise the adjacency matrix to powers. Having no directed cycles is equivalent to $(A^i)^1_{j,j} = (A_{j,j})^i$ for all $i,j\le |V|$. (Note: the redundant exponent of 1 was inserted to get latex to work.)
Edit: Mariano sums this up well in his comment, saying that $A$ is nilpotent.