I've come across the statement that the adjacency matrices of directed acyclic digraphs can always be permuted in such a way that we get a triangular matrix. Although I think I kind of get why, I am unsure how to prove the statement formally.
I have seen the following post: Directed acyclic graph and adjacency matrix Unfortunately it's still not clear to me.
Does anyone have a tipp for me?
Because the graph is a DAG, there exists a topological ordering on the vertices. After relabelling the vertices with this ordering, we have labelled vertices $v_1, v_2, \cdots, v_n$ such that if $v_i v_j$ is a directed edge, then $i < j$.
Now, entry $A_{ij}$ of the adjacency matrix is nonzero when there is an edge from $v_i$ to $v_j$. We want to show that $A$ is an (upper) triangular matrix. Formally, this means its entries below the main diagonal are zero. Moreover, entries $A_{ij}$ below the main diagonal are precisely the elements with $i > j$. Can you put it all together now?