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

Question

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.

Answer 1

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}. $$