This question has also been posted on mathSE here: https://math.stackexchange.com/questions/2215888/non-backtracking-paths-and-the-ihara-zeta-function

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$$ For $k \geq 2$, $$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)^{|E|-|V|}}{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$? After all, $$N_k = Tr(A_k)$$ and the expressions for the generating function and zeta function involve the same matrix expressions.

However, I am not clear what taking the determinant of a generating function intuitively gives us, nor is it clear if matrix operations like taking trace or determinant are even well-defined when applied on such generating functions. A similar question has been asked here https://math.stackexchange.com/questions/583883/how-to-get-from-chebyshev-to-ihara?noredirect=1&lq=1 and I have also been trying out ideas from here https://math.stackexchange.com/questions/154776/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.


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.