2
$\begingroup$

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.

  1. Would this process generate all possible DAGs with positive probability?
  2. 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,

Best regards

$\endgroup$
1
$\begingroup$

For question 2 the first answer is "yes": if $M$ is a $0-1$-nilpotent matrix, then it is the adjacency matrix of some digraph. Now $M^k_{i,j}$ is well-known to be the number of paths of length $k$ between vertices $i$ and $j$. Meanwhile, there exists some integer $\nu$ such that $M^k=0$ for $k \ge \nu$, so there are no paths of size greater than $\nu$ in the graph, in particular there cannot be any oriented cycle, hence the graph is a DAG.

For the rest of your questions, I have a mixed answer: indeed your going to get all adjacency matrices (as you're saying, this is just shuffling the topological order) ; and since the set of strictly upper triangular $0-1$-matrices of size $n$ along with the set of permutations of $n$ elements, each DAG of order $n$ will appear with positive probability.

Now I'm guessing what you want is that this probability is greater than some bound for any $n$, and this seems doubtful. Take for instance the path of size $n$, up to relabeling there are $n!$ of them. But there are $2^{(n-2)n \over 2}$ strictly upper triangular $0-1$-matrices of size $n$ and $n!$ way to shuffle each of them, so the probability of getting a path goes to $0$ exponentially fast.

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

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