This paper gives a procedure for counting redundant paths (which I will refer to as walks) in a graph using its adjacency matrix. As an exercise, I want to count only the walks of the form $i \rightarrow \color{blue}j \rightarrow k \rightarrow \color{blue}j \rightarrow l \rightarrow \color{blue}j$ from node $i$ to node $j$, with $ i \neq j \neq k \neq l$. Also see this post.
Let $A$ be the adjacency matrix. The notation I use below is: "$\cdot$" for usual matrix multiplication, "$\odot$" for element-wise matrix product, "d$(A)$" for the matrix with the same principal diagonal as $A$ and zeros elsewhere, and $S = A \odot A^T$.
The matrix for $i \rightarrow \color{blue}j \rightarrow k \rightarrow \color{blue}j \rightarrow l \rightarrow \color{blue}j$ will have its $i$, $j$ entry: $a_{ij}\cdot a_{jk}\cdot a_{kj}\cdot a_{jl}\cdot a_{lj}$. I have found this to be: $$ A \cdot (d(A^2))^2 $$
However, $i \rightarrow \color{blue}j \rightarrow k \rightarrow \color{blue}j \rightarrow l \rightarrow \color{blue}j$ also includes the following walks which repeat undesired nodes and should be subtracted: $$ \color{red}i \rightarrow j \rightarrow \color{red}i \rightarrow j \rightarrow l \rightarrow j \tag{1} $$ $$ \color{red}i \rightarrow j \rightarrow k \rightarrow j \rightarrow \color{red}i \rightarrow j \tag{2} $$ $$ i \rightarrow j \rightarrow \color{red}k \rightarrow j \rightarrow \color{red}k \rightarrow j \tag{3} $$ $$\color{red}i \rightarrow j \rightarrow \color{red}i \rightarrow j \rightarrow \color{red}i \rightarrow j \tag{4} $$
My calculations for $(1) - (4)$ are: $$ S \cdot \text{d}(A^2) \tag{1} $$ $$ \text{d}(A^2) \cdot S \tag{2} $$ $$ A \cdot \text{d}(A^2) \tag{3} $$ $$ S \tag{4} $$
Every time one of $(1) - (3)$ is subtracted, $(4)$ is subtracted as well, since it is included in all three. Since it is not desired in the end, it is added back 2 times. Overall: $$ A \cdot (d(A^2))^2 - S \cdot \text{d}(A^2) - \text{d}(A^2) \cdot S - A \cdot \text{d}(A^2) + 2S$$
However, this is wrong and gives incorrect counts, even negatives. What am I missing here?
I think I have found the problem. The approach and formulas seem to be correct. What I did not consider is that they work for directed graphs, so $(i, j) \neq (j, i)$. This means that the matrix for each term has to be added to its transpose. Each terms also counts pattern $(4)$ twice, so it needs to be added $4$ times, not $2$. At the end, the matrix is divided by two.
If we have $$ \text{sym}(M) = M + M^T $$
Then the formula I ended up with is: $$ [\text{sym}(A \cdot d(A^2)^2) - \text{sym}(S \cdot \text{d}(A^2)) - \text{sym}(\text{d}(A^2) \cdot S) - \text{sym}(A \cdot \text{d}(A^2)) + 4S] \div 2 $$ (sym can be moved to the outside)