Algebraic characterisation of directed acyclic graphs

Question

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?

Answer 1

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.