This paper offers a process for counting redundant paths (which I’ll discuss with as *walks*) in a graph utilizing its adjacency matrix. As an train, I wish to depend solely the walks of the shape $i rightarrow shade{blue}j rightarrow ok rightarrow shade{blue}j rightarrow l rightarrow shade{blue}j$ from node $i$ to node $j$, with $ i neq j neq ok neq l$. Additionally see this put up.

Let $A$ be the adjacency matrix. The notation I take advantage of under is: “$cdot$” for normal matrix multiplication, “$odot$” for element-wise matrix product, “d$(A)$” for the matrix with the identical principal diagonal as $A$ and zeros elsewhere, and $S = A odot A^T$.

The matrix for $i rightarrow shade{blue}j rightarrow ok rightarrow shade{blue}j rightarrow l rightarrow shade{blue}j$ can have its $i$, $j$ entry: $a_{ij}cdot a_{jk}cdot a_{kj}cdot a_{jl}cdot a_{lj}$. I’ve discovered this to be:

$$

A cdot (d(A^2))^2

$$

Nonetheless, $i rightarrow shade{blue}j rightarrow ok rightarrow shade{blue}j rightarrow l rightarrow shade{blue}j$ additionally consists of the next walks which repeat undesired nodes and needs to be subtracted:

$$

shade{crimson}i rightarrow j rightarrow shade{crimson}i rightarrow j rightarrow l rightarrow j tag{1} $$

$$ shade{crimson}i rightarrow j rightarrow ok rightarrow j rightarrow shade{crimson}i rightarrow j tag{2} $$

$$ i rightarrow j rightarrow shade{crimson}ok rightarrow j rightarrow shade{crimson}ok rightarrow j tag{3} $$

$$shade{crimson}i rightarrow j rightarrow shade{crimson}i rightarrow j rightarrow shade{crimson}i rightarrow j tag{4} $$

My calculations for $(1) – (4)$ are:

$$ S cdot textual content{d}(A^2) tag{1} $$

$$ textual content{d}(A^2) cdot S tag{2} $$

$$ A cdot textual content{d}(A^2) tag{3} $$

$$ S tag{4} $$

Each time one in all $(1) – (3)$ is subtracted, $(4)$ is subtracted as effectively, since it’s included in all three. Since it’s not desired ultimately, it’s added again 2 occasions. General:

$$ A cdot (d(A^2))^2 – S cdot textual content{d}(A^2) – textual content{d}(A^2) cdot S – A cdot textual content{d}(A^2) + 2S$$

Nonetheless, that is fallacious and provides incorrect counts, even negatives. What am I lacking right here?