PS: I don't know how to reduce the size of the second matrix below so that it fits in the page, someone please help
I'm reading the paper Beyond Homophily in Graph Neural Networks: Current Limitations and Effective Designs by Zhu et. al. In one of their proofs, the authors mention the following:
$[(A+I)X]_{T_{S,:}} = \begin{bmatrix}
hd +1 & \frac{1-h}{|Y|-1}d & \frac{1-h}{|Y|-1}d & \dots & \frac{1-h}{|Y|-1}d\\
\frac{1-h}{|Y|-1}d & hd +1 & \frac{1-h}{|Y|-1}d & \dots & \frac{1-h}{|Y|-1}d\\
\vdots & \vdots & \vdots & \ddots & \vdots\\
\frac{1-h}{|Y|-1}d & \frac{1-h}{|Y|-1}d & \dots & \frac{1-h}{|Y|-1}d & hd +1\\
\end{bmatrix}_{|Y|\times|Y|}$
Note that $[(A+I)X]_{T_{S,:}}$ is a circulant matrix, therefore its inverse exists. Using the Sherman-Morrison formula, we can find its inverse as:
$([(A+I)X]_{T_{S,:}})^{-1} = \frac{1}{(d+1)(|Y|-1+(|Y|h-1)d)}\begin{bmatrix}
(|Y|−1) + (|Y|−2 +h)d & (h-1)d & (h-1)d & \dots & (h-1)d\\
(h-1)d & (|Y|−1) + (|Y|−2 +h)d & (h-1)d & \dots & (h-1)d\\
\vdots & \vdots & \vdots & \ddots & \vdots\\
(h-1)d & (h-1)d & \dots & (h-1)d & (|Y|−1) + (|Y|−2 +h)d\\
\end{bmatrix}_{|Y|\times|Y|}$
I don't quite understand how they got this from the Sherman-Morrison formula, which according to Wikipedia:
"Suppose $A\in\mathbb{R}^{n\times n}$ is an invertible square matrix and $u,v\in\mathbb{R}^n$ are column vectors. Then $A + uv^\textsf{T}$ is invertible iff $1 + v^\textsf{T} A^{-1}u \neq 0$. In this case,
$\left(A + uv^\textsf{T}\right)^{-1} = A^{-1} – {A^{-1}uv^\textsf{T}A^{-1} \over 1 + v^\textsf{T}A^{-1}u}$"
Best Answer
For applying the Sherman-Morrison formula to calculate the inverse of the matrix you mentioned, $\mathbf{A}, \mathbf{u}$ and $\mathbf{v}$ in the formula can be set as $$ \mathbf{A} = \left((hd+1)-\frac{(1-h)}{|Y|-1}d\right)\mathbf{I}_{|Y|} = \frac{d (h |Y|-1)+|Y|-1}{|Y|-1}\;\mathbf{I}_{|Y|} $$ $$ \mathbf{u} = \begin{bmatrix} 1 & 1 & \cdots & 1 \end{bmatrix}_{|Y|}^{\textsf{T}} $$ $$ \mathbf{v} = \frac{(1-h)}{|Y|-1}d \cdot \begin{bmatrix} 1 & 1 & \cdots & 1 \end{bmatrix}_{|Y|} $$ From here the inverse of the matrix can be obtained by a straightforward application of the formula.