A property of directed acyclic graph

Question

Suppose $A \in \mathbb{R}^p$ is the adjacency matrix of a weighted directed acyclic graph $D$ with vertex set $\left\{v_{1}, v_{2}, \ldots, v_{p}\right\}$, i.e. $$ a_{i j}=\left\{\begin{array}{lr} w\left(v_{i}, v_{j}\right), & \text { if there is an arc from } v_{i} \text { to } v_{j} \\ 0, & \text { otherwise } \end{array}\right. $$ What I want to know is that for a specific $x \in \mathbb{R}^p$, does there exists a explicit display for $$ \big[ (I_p - A)^{-1} x \big]_{-j} - (I_{p - 1} - A_{-j, -j})^{-1} x_{-j} $$ where $x_{-j} = (x_1, \ldots, x_{j - 1}, x_{j + 1}, \ldots, x_p)$, and $A_{-j, -j}$ is the $A$ dropping $j$-th row and column.

PS: I have tried that

If $A$ is just the adjacency matrix, there exists $m \in \mathbb{N}$ such that $$ (I_p - A)^{-1} = I + A + A^2 + \cdots + A^m $$ and the $a_{ij} \in \{ 0, 1\}$ will allow a simple display for $(I_p - A)^{-1} x$. However, now we allow $a_{ij} \in \mathbb{R}^+$. $A$ may not a nilpotent matrix. I do not know how to solve this problem.

Can anyone help me? Thanks in advance!

Answer 1

Preliminary definition. Let $\mathcal{S}$, $\mathcal{S}'$ be two complementary nonempty sets of indices, i.e., $\mathcal{S}\cup \mathcal{S}'=\left\{1,2,\ldots,p\right\}$ and $\mathcal{S}\cap \mathcal{S}'=\emptyset$.

Define $\mathcal{E}_{\mathcal{S}}\overset{\Delta}=\left[\left(I-A\right)^{-1}x\right]_{\mathcal{S}}-\left(I_{\mathcal{S}}-A_{\mathcal{S}}\right)^{-1}x_{\mathcal{S}}$, where $\left[y\right]_{\mathcal{S}}$ is the sub-vector indexed by $\mathcal{S}$. Remark that this conforms to a generalized form for the error term in your question where you assume $\mathcal{S}=\left\{1,2,\ldots,j-1,j+1,\ldots,p\right\}$ and $\mathcal{S}'=\left\{j\right\}$.

Preliminary remark. I will refer to $\mathcal{E}_{\mathcal{S}}$ as the error term since it is the error committed by commuting the projection $\left[\cdot\right]_{\mathcal{S}}$ with the underlying operations (product and matrix-inversion). In a sense, the question can be rephrased as: Does the error of commuting the projection $\left[\cdot\right]_{-j}$ with the underlying operations admit an amenable closed-form expression in terms of $A$ and $x$?

For the first term of $\mathcal{E}_{\mathcal{S}}$, observe that $\left[\left(I-A\right)^{-1}x\right]_{\mathcal{S}}=\left[x+Ax+A^2x+\ldots\right]_{\mathcal{S}}=\sum_{i=0}^{\infty} \left[A^ix\right]_{\mathcal{S}}=\sum_{i=0}^{\infty} \left[A^i\right]_{\mathcal{S}}x_{\mathcal{S}}+\left[A^i\right]_{\mathcal{S}\mathcal{S}'}x_{\mathcal{S}'}$.

For the second term of $\mathcal{E}_{\mathcal{S}}$, we have

$$\left(I_{\mathcal{S}}-A_{\mathcal{S}}\right)^{-1}x_{\mathcal{S}}=\sum_{i=0}^{\infty} \left(A_{\mathcal{S}}\right)^ix_{\mathcal{S}}.$$

Therefore, via combining the two terms, we have

$$\mathcal{E}_{\mathcal{S}}=\sum_{i=1}^{\infty} \left(\left[A^i\right]_{\mathcal{S}}-\left(A_{\mathcal{S}}\right)^i\right)x_{\mathcal{S}}+\sum_{i=0}^{\infty}\left[A^i\right]_{\mathcal{S}\mathcal{S}'}x_{\mathcal{S}'},$$

which yields

$$\mathcal{E}_{\mathcal{S}}=\left(\left[(I-A)^{-1}\right]_{\mathcal{S}}-(I_{\mathcal{S}}-A_{\mathcal{S}})^{-1}\right)x_{\mathcal{S}}+\left[(I-A)^{-1}\right]_{\mathcal{S}\mathcal{S}'}x_{\mathcal{S}'}.$$

In your particular case, where $\mathcal{S}=\left\{1,2,\ldots,j-1,j+1,\ldots,p\right\}$ and $\mathcal{S}'=\left\{j\right\}$, we can further simplify the above expression via the following inversion Lemma (e.g., Matrix Analysis, Horn):

$$\left(B_{\mathcal{S}}\right)^{-1}=\left[B^{-1}\right]_{\mathcal{S}}-\left[B^{-1}\right]_{\mathcal{S}\mathcal{S}'}\left(\left[B^{-1}\right]_{\mathcal{S}'}\right)^{-1}\left[B^{-1}\right]_{\mathcal{S}'\mathcal{S}} \,\,\,(\star).$$

Set $B:=\left(I-A\right)$ in the inversion Lemma $(\star)$, then

$$\mathcal{E}_{\mathcal{S}}=\frac{1}{\left(\left[\left(I-A\right)^{-1}\right]_{jj}\right)}\left(\left[\left(I-A\right)^{-1}\right]_{\mathcal{S}\mathcal{S}'}\left[\left(I-A\right)^{-1}\right]_{\mathcal{S}'\mathcal{S}}\right)x_{\mathcal{S}}+\left[(I-A)^{-1}\right]_{\mathcal{S}\mathcal{S}'}x_{j},$$

which under your notation goes by

$$\mathcal{E}_{\mathcal{S}}=\frac{1}{\left(\left[\left(I-A\right)^{-1}\right]_{jj}\right)}\left(\left[\left(I-A\right)^{-1}\right]_{-j,j}\left[\left(I-A\right)^{-1}\right]_{j,-j}\right)x_{-j}+\left[(I-A)^{-1}\right]_{-j,j}\,x_{j}.$$

Final remark. Interestingly, the error term $\mathcal{E}_{\mathcal{S}}$ does not depend on the entries of the $(p-1)\times (p-1)$ sub-matrix $\left[(I-A)^{-1}\right]_{-j,-j}$ -- which is the bulk of the $p\times p$ matrix $\left(I-A\right)^{-1}$.