Q:

Directed acyclic graph and adjacency matrix

How can I prove that a directed graph is acyclic if and only if the vertices can be sorted in such a way that the adjacency matrix has upper triangular form with only zeros in the diagonal?
I know that a graph is acyclic as long $A^n$ has zeroes along the diagonal for every $n \geq 1$. How can I prove the above statement?

A:

If the graph is acyclic, then the topological sort algorithm produces the required ordering of vertices. Conversely, suppose the vertices can be sorted so all edges go from lower-numbered vertices to higher-numbered vertices; it's clear there cannot be a cycle.

