The adjacency matrix of an acyclic graph is known to be a nilpotent matrix (all eigenvalues are zero). I am interested in sampling DAG adjacency matrices or equivalently sample random nilpotent matrices (the equivalence is a question in fact) and so far I have simplified the process to the following:
- step 1. randomly permute the nodes
- step 2. sample a strictly upper triangular matrix (zero diagonal)
the first step is required to make sure we shuffle the topological ordering roots and step 2 is constructing a random topological ordering. The matrix is nilpotent as by construction the eigenvalues are zero.
I'm interested in an answer to either question 1 or 2.
- Would this process generate all possible DAGs with positive probability?
- Are all nilpotent matrices adjacency matrices of DAGs AND would the process above generate with positive probability every nilpotent matrix?
Any pointers or hints will be greatly appreciated,