§ Number of paths in a DAG

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