1
$\begingroup$

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.

$\endgroup$

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.