How can prove that inverse of transition matrix shows path equations between digraph's nodes?

Question

If matrix T represents transitions between all nodes in digraph G, how can prove that the inverse of T represents path equation of digraph G?

For example, consider following transition matrix:

$$ T= \left( \begin{array}{ccc} 0 & a & b & 0\\ 0 & 0 & 0 & c \\ 0 & 0 & 0 & d \\ 0 & 0 & 0 & 0 \end{array} \right) \rightarrow T^{-1} = \sum\limits_{i=0}^n T^i = \left( \begin{array}{ccc} 0 & a & b & ac+bd\\ 0 & 0 & 0 & c \\ 0 & 0 & 0 & d \\ 0 & 0 & 0 & 0 \end{array} \right) $$

Element(1,4) of inverse of T represents path equation from node 1 to node 4. We need prove mentioned example in general.

Thanks a lot.

Answer 1

$T$ is all the connections of length 1 (ie edge connections). $T^2$ is all the connections of length two. In general $T^n$ is all the connections of length $n$. Adding these together gives all the connections from 1 to $n$.

$T^{-1}=\sum^{\infty}_{n=1}T^n$ is then the sum of all possible path lengths connecting the various point pairs.