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$
  • $\begingroup$ What you write about powers of matrices is vague and incomplete, so it's hard to know what you want. For example, you write "$a_{li} \cdot a_{ik}$ and $a_{kj} \cdot a_{jl}$ are both of the form $A^2$", which doesn't have much meaning. What's actually true, for example, is that for each $j,k,l$ the expression $a_{kj} \cdot a_{jl}$ is just one term of the summation expression for the $(k,l)$ entry of $A^2$, namely $\sum_j a_{kj} \cdot a_{jl}$ where $j$ is the summation variable. Your question won't make much sense until you can express it with more mathematical precision. $\endgroup$ – Lee Mosher May 20 at 12:11
  • $\begingroup$ @LeeMosher I tried to improve the clarity of the question. I find some things confusing (hence the question) and this is reflected in what you pointed out. As I understand, the focus is on one element ($(i, j)$ above) since any entry which fits the pattern will be incremented. $\endgroup$ – Michael May 20 at 13:13

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.