# Counting a walk $i \rightarrow j \rightarrow k \rightarrow j \rightarrow l \rightarrow j$ in a graph

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)