§ Number of paths in a DAG
Given the adjacency matrix of a DAG, this must be nilpotent. This is because
will tell us the number of paths from to with edges in the path.
In a DAG, since there are no cycles, there is an upper bound on the number of edges
a path can have: the longest path is , when the DAG is a straight line. Thus,
we must have that .
- Let .
- Now, we know that which will terminate as a finite sum, with .
- But note that will count number of paths from to with edges, edge, edges, etc. so we will get the total number ofpaths from to !.