0
$\begingroup$

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.

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

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Browse other questions tagged or ask your own question.