<p>For question 2 the first answer is &quot;yes&quot;: if <span class="math-container">$M$</span> is a <span class="math-container">$0-1$</span>-nilpotent matrix, then it is the adjacency matrix of some digraph.
Now <span class="math-container">$M^k_{i,j}$</span> is well-known to be the number of paths of length <span class="math-container">$k$</span> between vertices <span class="math-container">$i$</span> and <span class="math-container">$j$</span>. Meanwhile, there exists some integer <span class="math-container">$\nu$</span> such that <span class="math-container">$M^k=0$</span> for <span class="math-container">$k \ge \nu$</span>, so there are no paths of size greater than <span class="math-container">$\nu$</span> in the graph, in particular there cannot be any oriented cycle, hence the graph is a DAG.</p>
<p>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 <span class="math-container">$0-1$</span>-matrices of size <span class="math-container">$n$</span> along with the set of permutations of <span class="math-container">$n$</span> elements, each DAG of order <span class="math-container">$n$</span> will appear with positive probability.</p>
<p>Now I'm guessing what you want is that this probability is greater than some bound for any <span class="math-container">$n$</span>, and this seems doubtful. Take for instance the path of size <span class="math-container">$n$</span>, up to relabeling there are <span class="math-container">$n!$</span> of them. But there are <span class="math-container">$2^{(n-2)n \over 2}$</span>  strictly upper triangular <span class="math-container">$0-1$</span>-matrices of size <span class="math-container">$n$</span> and <span class="math-container">$n!$</span> way to shuffle each of them, so the probability of getting a path goes to <span class="math-container">$0$</span> exponentially fast.</p>

CC BY-SA 4.0
2021-02-20T12:28:56.177Z
2021-02-20T12:28:56.177Z
thibo
<p>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:</p>
<ul>
<li><strong>step 1.</strong> randomly permute the nodes</li>
<li><strong>step 2.</strong> sample a strictly upper triangular matrix (zero diagonal)</li>
</ul>
<p>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.</p>
<p>I'm interested in an answer to either question 1 or 2.</p>
<ol>
<li>Would this process generate all possible DAGs with positive probability?</li>
<li>Are all nilpotent matrices adjacency matrices of DAGs <strong>AND</strong> would the process above generate with positive probability every nilpotent matrix?</li>
</ol>
<p>Any pointers or hints will be greatly appreciated,</p>
<p>Best regards</p>

<graph-theory><directed-acyclic-graph>
random sampling DAGs via nilpotent matrix sampling
ptigas
# random sampling DAGs via nilpotent matrix sampling

(Asked by: username_0 on 2021-02-12)

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

**Tags:** graph-theory, directed-acyclic-graph


---

## 1 answers

### Answer by username_1 on 2021-02-20. Score: 1

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.


---

