Determining the number of walks in a special matrix

Question

We are given that $G = (V,E)$ is a graph with $|V| < \infty, V = \{(i,j) | 1 \leq i \leq n, 0 \leq j \leq 1\}$ where $n \geq 3$. Next we are given that if we have two vertices $x,y$ where $x = (a,b), y = (c,d)$, then $E(x,y) = 0 \ \text{if} \ b = d$, $E(x,y) = 1 \ \text{if} \ a = c, b \neq d$, and $E(x,y) = 2 \ \text{otherwise}$. We are asked to give a formula for the number of walks of length $l, l \geq 1$ from $x \in V$ to $y \in V$. I know that we can raise the adjancency matrix to the power of $l$ for walks of length $l$, but I am having a trouble discerning the pattern that happens with the entries when doing so for this specific matrix.

Answer 1

Hint: This is a combinatorial approach: Suppose you visit vertices $x_1,x_2,\cdots ,x_k$ with $x_1=x,x_k=y,$ and $x_i\neq x_j$ for any $i\neq j.$ Then you need to know how many times you stay in each vertex and so you are interested in $(\alpha _1,\cdots ,\alpha _k)\in \mathbb{Z}^{\geq 0}$ such that $\sum _{i=1}^k\alpha _i=\ell.$ You can do this in $\binom{\ell -1}{k-1}$ ways. now, every time that you change vertex you paid $2$ and you have $n-1$ options. Can you add over this possibilities of $k$? Notice that you have to distinguish the second component, so the formula depends in if $\ell$ is even or odd and if we start with $b=d$ or not.

Edit: What i wrote was very incomplete. I am sorry for the inconvenience.

Now, fix $x$ as the vertex and fix a number $k\leq \ell,$ we would like to factor the path as follows: $$P=(x,a_1,\cdots ,a_{k})$$ apriori, forget that we want $a_{k}=y,$ but assume $a_{k}\neq x$ Then, this is like counting the number of closed paths in the complete graph starting and ending at $x$ of length $k +1$ which can be counted or found using the eigenvalues to be $$\frac{(n-1)^{k +1}-(n-1)(-1)^{k}}{n},$$

Now, we are allowing cycles(so notice that the $a_i$ are paths in between elements with the same first coordinate), and so we want to stay in each vertex $a_k$ a time, say $\alpha _i\geq 1.$ So we have a vector $(\alpha _0,\alpha _1,\cdots ,\alpha _k)\in \mathbb{Z}^{>0}$ such that $\sum _{i=0}^k\alpha _i=\ell+1$ as said before, this can be counted in $\binom{\ell }{k}$ ways. Now, any time that we switch vertex we have $2$ options as the graph has two edges in between these kind of vertices, so we have to pay $2^k.$ Now, by symmetry, going to any of the vertices $\neq x$ should have the same number of paths, and so adding all the possible $k$ we get $$\frac{1}{n}\sum _{k=1}^\ell \binom{\ell}{k}2^k((n-1)^k-(-1)^k)$$ Here i am assuming that the first components of $x$ and $y$ are different. Now we have to take care of the parity and the case in which $x,y$ have same first component. Can you do it?