# Non-backtracking closed walks and the Ihara zeta function (Updated with partial attempt)

For a connected $d$-regular graph $G=(V,E)$ with adjacency matrix $A$, we defined a sequence of matrices $$A_0,A_1,A_2,A_3,\dots$$ defined using powers of $A$ inductively as follows: $$A_0=I$$ $$A_1=A$$ $$A_2=A^2-dI$$ For $k \geq 3$, $$A_{k}=A_{k-1}A-(d-1)A_{k-2}$$ Just like $(A^k)_{v,w}$ counts the number of walks on $G$ from $v$ to $w$, the value $(A_k)_{v,w}$ counts the number of walks on $G$ from $v$ to $w$ without backtracking. The recurrence relation above can be used to easily show that the ordinary (matrix) generating function for the above sequence is $$\sum \limits_{k=0}^{\infty} t^k A_k = (1- t^2)I. \left( I-tA + (d-1)t^2 I \right)^{-1}$$ With some abuse of notation, we can rewrite this generating function as $$\frac{1-t^2}{I-At+(d-1)t^2}$$

On the other hand, the Ihara zeta function of the graph $G$ is given by $$\zeta_G(t) = exp \left( \sum \limits_{k=1}^{\infty} N_k \frac{t^k}{k} \right)$$ where $N_k$ is the number of closed non-backtracking walks on $G$ of length $k$. It is known that $\zeta_G(t)$ has an alternate expression using determinants as $$\zeta_G(t) = \frac{(1-t^2)^{|V|-|E|}}{det(I-At+(d-1)t^2)}$$

My question is: can the determinant formula for the Ihara zeta function be derived from the generating function for the matrices $A_k$? What exactly is the relationship between $A_k$ and $N_k$?

A similar question has been asked here How to get from Chebyshev to Ihara? and I have also been trying out ideas from here Proof of 2 Matrix identities (Traces, Logs, Determinants) But I am not interested in the Chebychev polynomial connection here: just whether the generating function can be manipulated using logarithms and traces to obtain the expression for the zeta function. Thanks.

UPDATE: Here's a partial attempt of mine. Using Chebychev polynomials of the second kind defined as $$U_0(x)=1$$ $$U_1(x) = 2x$$ and for $k \geq 2$, $$U_k(x) = U_{k-1}(x)U_1(x) - U_{k-2}(x)$$ and with generating function $$\sum \limits_{k=0}^{\infty} U_k(x)t^k = \frac{1}{1-2xt+t^2}$$ we can express the matrix $A_k$ as $$A_k = (d-1)^{k/2} U_k \left( \frac{A}{2 \sqrt{d-1}} \right) - (d-1)^{k/2-1} U_{k-2} \left( \frac{A}{2 \sqrt{d-1}} \right)$$ and so $$Tr(A_k) = (d-1)^{k/2} \sum \limits_{i=0}^{n-1} U_k \left( \frac{\mu_i}{2 \sqrt{d-1}} \right) - (d-1)^{k/2-1} \sum \limits_{i=0}^{n-1} U_{k-2} \left( \frac{\mu_i}{2 \sqrt{d-1}} \right)$$ where $$d=\mu_0 \geq \mu_1 \geq \dots \geq \mu_{n-1} \geq d$$ are the $n$ eigenvalues of the adjacency matrix $A$. Thus we have an expression for the trace of $A_k$ as a polynomial in the eigenvalues of $A$.

In a similar way, working backwards fro the definition of the Ihara zeta function, we can define another matrix sequence $B_k$ as follows: $$B_1=A$$ $$B_2 = A^2-dI$$ and for $k \geq 3$, $$B_k = \begin{cases} B_{k-1}A - (d-1)B_{k-2} - (d-2)A & \text{ if k is odd}\\ B_{k-1}A - (d-1)B_{k-2} + d(d-2)I & \text{ if k is even} \end{cases}$$ Just like $A_k$ could be expressed in terms of Chebychev polynomials $U_k$ of the second kind, the matrices $B_k$ can be expressed using Chebychev polynomials $T_k$ of the first kind defined by the recurrence $$T_0(x)=1$$ $$T_1(x)=x$$ and for $k \geq 2$, $$T_k(x)=2xT_{k-1}(x)-T_{k-2}(x)$$ The expression for $B_k$ is $$B_k=\begin{cases} 2(d-1)^{k/2}T_k \left( \frac{A}{2\sqrt{d-1}} \right) & \text{ if k is odd}\\ 2(d-1)^{k/2}T_k \left( \frac{A}{2\sqrt{d-1}} \right)+(d-2)I & \text{ if k is even} \end{cases}$$

All this is simply by reverse engineering the expression for the Ihara zeta function to obtain $N_k$ as the trace of some matrix. My question now, modulo correctness of my calculations, is whether the matrices $B_k$ as defined above have any natural interpretation in terms of walks on the graph.

• Glad you started a chatroom. The rest of is conversation has been moved to this chat in response to a system flag due to a large number of comments. – Jyrki Lahtonen Apr 8 '17 at 8:59
• Did you try recursion on vertices or edges ? I'd say the $\det$ comes from this. – reuns Apr 9 '17 at 2:51
• @user1952009 I have updated the question with a corrected re-attempt. But now it keeps getting uglier and seems hopeless. Do have a look and share your insights. Thanks. – BharatRam Apr 10 '17 at 9:31
• Hi @user1952009 I would say the recursion is done on vertices since you use the vertex adjacency matrix. How do you bring in det by any of them? – draks ... Apr 10 '17 at 17:36
• Link to chat... – draks ... Apr 23 '17 at 20:32

A matrix generating function is a matrix over a ring (of power series). Trace and determinant are defined for matrices of arbitrary commutative rings, and so they can be used freely in this context.

• Hello Prof.Godsil. Thanks for clearing that up. But the bigger question is still looming: can the Bass determinant formula for the Ihara zeta function be derived simply by manipulating the matrix generating function above? I wouldn't want to waste your time by asking for a detailed calculation but please do guide me with a hint on whether the two are related in a straightforward way that I am missing.I have been trying out the calculations to no avail. The $|E|-|V|$ in the exponent is particularly intriguing in its origin. Thanks. – BharatRam Apr 5 '17 at 9:38
• Hello Prof.Godsil. I have updated the question with my partial calculations, which almost seem right except for the $1-t^2$ factor. Please do have a look at it. – BharatRam Apr 6 '17 at 16:59

This is not an answer, but I thought it too long for the chat room.

The formula $$\exp \left( \sum \limits_{k=1}^{\infty} \text{Tr}\,A_k \frac{t^k}{k} \right) = \frac{1}{\det(I-At+(d-1)t^2)}$$ cannot be correct, as it does not work when you try it on a particular example. Consider the $4$-regular graph consisting of a single vertex with two loops. We have $d=4$, $A=[4]$, and $A_k=\left[4\cdot3^{k-1}\right]$. So the left side reduces to $$\exp\left(\frac{4}{3}\sum_{k=1}^\infty\frac{(3t)^k}{k}\right)=\exp\left(-\frac{4}{3}\log(1-3t)\right)=(1-3t)^{-4/3},$$ which is not equal to the right hand side, $(1-4t+3t^2)^{-1}$. In fact, the left hand side is not even a rational function of $t$, although it is algebraic.

In this example, it is not too hard to eliminate the walks with tails using inclusion-exclusion. By the recurrence for $A_k$, there are $4\cdot3^{k-1}$ walks of length $k$ that have no backtracking except for a possible tail. This can be easily understood by noting that each of the two loops may be traversed in either of two directions, for a total of four possible steps, but that no step may be the reverse of the one just taken. Let $s_1s_2\ldots s_k$ be the sequence of steps taken. The walk has a tail if $s_k=s_1^{-1}$. We want to subtract such walks A set containing all such walks with tails can be obtained by appending $s_1^{-1}$ to each of the $4\cdot3^{k-2}$ nonbacktracking walks of length $k-1$. Some of the walks obtained in this way contain backtracking, however, namely those in which $s_{k-1}=s_1$, and therefore should not have been included in the subtraction. So we add these back in. Such walks may be obtained by appending $s_1$ to one of the $4\cdot3^{k-3}$ nonbacktracking walks of length $k-2$. Some of these walks now contain backtracking, namely those in which $s_{k-2}=s_1^{-1}$. So we need to subtract these, and so on. The end result of these subtractions and additions is \begin{aligned} N_k&=4\cdot3^{k-1}-\sum_{j=1}^{\lfloor(k-1)/2\rfloor}(4\cdot3^{k-2j}-4\cdot3^{k-2j-1})\\ &=4\cdot3^{k-1}-3^{k-1}\left[1-\left(\frac{1}{3}\right)^{2\lfloor(k-1)/2\rfloor}\right]\\ &=4\cdot3^{k-1}-(3^{k-1}-3^{\epsilon_k})\\ &=3^k+3^{\epsilon_k}, \end{aligned} where $\epsilon_k=0$ for $k$ odd and $1$ for $k$ even.

Inserting this into the expression for the zeta function gives \begin{aligned} \exp \left( \sum \limits_{k=1}^{\infty} N_k \frac{t^k}{k} \right) &=\exp \left( \sum \limits_{k=1}^{\infty} \frac{(3t)^k}{k} +\sum \limits_{k=1}^{\infty} \frac{t^k}{k}+\sum \limits_{k=1}^{\infty} \frac{2t^{2k}}{2k}\right)\\ &=\exp\left(-\log(1-3t)-\log(1-t)-\log(1-t^2)\right)\\ &=\frac{(1-t^2)^{-1}}{1-4t+3t^2}\\ &= \frac{(1-t^2)^{|V|-|E|}}{\det(I-At+(d-1)t^2)}, \end{aligned} confirming the determinant formula for the Ihara zeta function in this example.

I have not tracked down what went wrong in your derivation of the expression for $$\exp \left( \sum \limits_{k=1}^{\infty} \text{Tr}\,A_k \frac{t^k}{k} \right),$$ but I'm not sure I follow even the first step, where an integration is performed. Can you elaborate on that?

• You're absolutely right! I wrongly assumed that the clumsy function that arises in the integral cancels out. It doesn't an thats the source of the error. Sorry for the hasty calculation. I corrected the mistake, but now the expression is far from elegant. Will update it nevertheless. – BharatRam Apr 9 '17 at 16:10
• So the "expression", if you can even call it that, for $\exp\left( \sum \limits_{k=1}^{\infty} Tr(A_k) t^k/k \right)$ is a total trainwreck! Apart from a non-integer power of $det(I-At+(d-1)T^2)$, there is an ugly sum over the eigenvalues of $A$ of a contorted function as seen in the update in the question (the cursed expression $C$). I am losing hope that anything remotely elegant can be salvaged from that dump. Its remarkable how the zeta function bypasses all this and ends up with such a neat determinant formula! – BharatRam Apr 10 '17 at 9:22
• Do you believe there is any connection between $N_k$ and $A_k$ in general? The inclusion-exclusion computation that you used in your example doesn't seem promising for an $n$-vertex graph. – BharatRam Apr 10 '17 at 9:24
• +1 your work out makes the impression that the sums in the exponent have to build up the logs we need to get down to the rational. Interesting... – draks ... Apr 10 '17 at 17:40
• And for every graph with fixed $V$ and $E$ we get something like $\exp \left( \sum \limits_{k=1}^{\infty} N_k \frac{t^k}{k} \right) = \exp\left(\dots +(|V|-|E|)\log(1-t^2)\right)$. Further for bipartite graphs all $N_k\neq 0$ for even $k$, then $N_k=\tilde N_k-(|V|-|E|)$ ... – draks ... Apr 10 '17 at 18:24