Take the 2-minute tour ×
MathOverflow is a question and answer site for professional mathematicians. It's 100% free, no registration required.

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?

share|improve this question
4  
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
1  
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

1 Answer 1

up vote 5 down vote accepted

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.

share|improve this answer
    
A good resource for this sort of thing is the section on the incidence algebra in chapter 3 of Enumerative Combinatorics, Volume 1, by Richard Stanley. The overall topic of chapter 3 is partially ordered sets. You might also read there about linear extensions of partially ordered sets. –  Patricia Hersh Oct 27 '12 at 12:48
    
great! thanks for the answer. thanks also @Mariano. –  user27571 Oct 29 '12 at 9:34

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

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