§ 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 of paths from $i$ to $j$!.