# Usefulness of the inverse of $I-A$ in a finite tree network

I am reading a paper which has some graph theory context as well. Specifically, there is a directed-tree $$T$$ with reversed-edges (i.e., an edge is from a child node to its parent node instead of parent node to the child node). There are nodes $$a$$ and $$b$$ and we want to find out if the node $$b$$ is along the path from the node $$a$$ to the root node of the tree which is labelled by $$r$$. The paper suggests the following.

• Compute the inverse $$M=(I-A)^{-1}$$ where $$A$$ is the adjacency-matrix.
• If $$M(a,b)>0$$, then $$T$$ has $$b$$ along the path from $$a$$ to $$r$$. Basically it says that for the $$i^{th}$$ row of $$M$$, all columns with a value greater than $$0$$ indicate the nodes that are visited on the directed path from node $$i$$ to the root $$r$$. This is something that I would like to get some intuition/comments on. Thank you.

The condition "$$T$$ has $$b$$ along the path from $$a$$ to $$r$$" is equivalent to the condition "there is a directed path from $$a$$ to $$b$$", because the only kind of directed path we can have in this tree is the path that walks up from a node to eventually reach $$r$$.
We can use the adjacency matrix to detect these paths: $$A^k(a,b) = 1$$ if there is a path of length $$k$$, and $$A^k(a,b) = 0$$ otherwise. (Normally, $$A^k$$ counts the number of directed walks, but your tree has no cycles, so that's the same thing.)
But we don't care about $$k$$, so we want to replace $$A^k$$ by the sum $$M = I + A + A^2 + A^3 + \dots + A^{n-1}$$. (We don't need to go past $$A^{n-1}$$, because the distance from $$a$$ to $$r$$ must be less than $$n$$.) In this matrix, we have $$M(a,b) = 1$$ if there is a path of any length from $$a$$ to $$b$$: exactly what you want.
Now, we do some simplification that's similar to the identity $$x^n-1 = (x-1)(x^{n-1} + x^{n-2} + \dots + x + 1)$$ you may be familiar with. If we multiply our sum $$I + A + A^2 + \dots + A^{n-1}$$ by $$I - A$$, then we get $$M(I-A) = (I + A + A^2 + \dots + A^{n-1}) - (A + A^2 + A^3 + \dots + A^n) = I - A^n.$$ Moreover, for this specific graph, $$A^n$$ is the zero matrix: $$A^n(a,b)$$ is only nonzero if there is a length-$$n$$ walk from $$a$$ to $$b$$, which is impossible, because any walk from $$a$$ reaches the root and stops in at most $$n-1$$ steps. Therefore multiplying $$I + A + A^2 + \dots + A^{n-1}$$ by $$I - A$$ gives $$I$$, which means $$(I - A)^{-1} = I + A + A^2 + \dots + A^{n-1}.$$