## § Number of paths in a DAG

Given the adjacency matrix $A$ of a DAG, this must be nilpotent. This is because
$A^k[i][j]$ will tell us the number of paths from $i$ to $j$ with $k$ 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 $|V| - 1$, when the DAG is a straight line. Thus,
we must have that $A^|V| = 0$.
- Let $A^n = 0$.
- Now, we know that $(I - A)^{-1} = I + A + A^2 + \dots$which will terminate as a finite sum, with $(I - A)^{-1} = I + A + A^2 + \dots + A^{n-1}$.
- But note that $(I + A + A^2 + \dots A^{n-1})[i][j]$ will count number of paths from $i$ to $j$ with $0$ edges, $1$ edge, $2$ edges, etc. so we will get the
*total* number ofpaths from $i$ to $j$!.