# Counting a walk $i \rightarrow k \rightarrow l \rightarrow i \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 k \rightarrow l \rightarrow i \rightarrow k \rightarrow j \rightarrow l \rightarrow 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 (when using matrices, otherwise the normal number product), "$$\odot$$" for element-wise matrix product, "diag$$(A)$$" for the matrix with the same principal diagonal as $$A$$ and zeros elsewhere, and $$S = A \odot A^T$$.

The idea is to find a matrix expression giving the desired walk. I will include 3 examples from the paper. These seem straightforward, but I do not know how to infer a general rule.

(First example)

$$i \rightarrow \color{red}j \rightarrow k \rightarrow l \rightarrow \color{red}j \tag{1}$$

In this case, the desired matrix has its $$(i, j)$$ entry the product: $$a_{ij} \cdot a_{jk} \cdot a_{kl} \cdot a_{lj}$$

In this case, the matrix that has entries $$a_{jk} \cdot a_{kl} \cdot a_{lj}$$ is diag$$(A^3)$$ and $$a_{ij}$$ is given just by $$A$$. Overall, the expression for this walk is $$A \cdot \text{diag}(A^3)$$.

(Second example)

$$\color{blue}i \rightarrow \color{red}j \rightarrow k \rightarrow \color{blue}i \rightarrow \color{red}j \tag{2}$$

In this case, the desired matrix has its $$(i, j)$$ entry the product: $$a_{ij} \cdot a_{jk} \cdot a_{ki} \cdot a_{ij}$$

One thing to note is that $$a_{ij}$$ is included 2 times and $$a_{ij} \cdot a_{ij} = a_{ij}$$, so the expression simplifies to: $$a_{jk} \cdot a_{ki} \cdot a_{ij}$$

Here, $$a_{jk} \cdot a_{ki}$$ is the $$(i, j)$$ entry in $$(A^2)^T$$, so overall the desired matrix is given by $$A \odot (A^2)^T$$.

(Third example) $$\color{blue}i \rightarrow \color{orange}k \rightarrow \color{blue}i \rightarrow \color{orange}k \rightarrow j \tag{3}$$

Here, the $$(i, j)$$ entry in the matrix is given by: $$a_{ik} \cdot a_{ki} \cdot a_{ik} \cdot a_{kj}$$

One $$a_{ik}$$ can again be removed, leaving: $$a_{ik} \cdot a_{ki} \cdot a_{kj}$$

The argument here is that $$a_{ik} \cdot a_{ki}$$ is the $$(i, k)$$ entry of $$S = A \odot A^T$$ and $$a_{kj}$$ is the $$(k, j)$$ of $$A$$ so the summation is with regards to $$k$$, giving $$S \cdot A$$.

(Problem at hand)

However, I can't seem to make any progress on $$\color{blue}i \rightarrow \color{orange}k \rightarrow l \rightarrow \color{blue}i \rightarrow \color{orange}k \rightarrow \color{red}j \rightarrow l \rightarrow \color{red}j$$. The $$(i, j)$$ entry is given by:

$$a_{ik} \cdot a_{kl} \cdot a_{li} \cdot a_{ik} \cdot a_{kj} \cdot a_{jl} \cdot a_{lj}.$$

I do not fully understand the rules. Here, it would seem that for multiplication the summation has to be done over different indices, like $$k$$ and $$l$$. Another source of confusion is if it is allowed to do operations on elements which are not adjacent, like at position 1 ($$a_{ik}$$) and 5 ($$a_{kj}$$) above. Since they are factors of multiplication, the position shouldn't matter.

• Sorry, what's the question? – Pål GD May 20 at 23:00