6
$\begingroup$

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.

$\endgroup$
  • $\begingroup$ 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. $\endgroup$ – Jyrki Lahtonen Apr 8 '17 at 8:59
  • $\begingroup$ Did you try recursion on vertices or edges ? I'd say the $\det$ comes from this. $\endgroup$ – reuns Apr 9 '17 at 2:51
  • $\begingroup$ @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. $\endgroup$ – BharatRam Apr 10 '17 at 9:31
  • $\begingroup$ 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? $\endgroup$ – draks ... Apr 10 '17 at 17:36
  • $\begingroup$ Link to chat... $\endgroup$ – draks ... Apr 23 '17 at 20:32
2
$\begingroup$

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.

$\endgroup$
  • $\begingroup$ 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. $\endgroup$ – BharatRam Apr 5 '17 at 9:38
  • $\begingroup$ 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. $\endgroup$ – BharatRam Apr 6 '17 at 16:59
2
+50
$\begingroup$

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?

$\endgroup$
  • $\begingroup$ 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. $\endgroup$ – BharatRam Apr 9 '17 at 16:10
  • $\begingroup$ 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! $\endgroup$ – BharatRam Apr 10 '17 at 9:22
  • $\begingroup$ 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. $\endgroup$ – BharatRam Apr 10 '17 at 9:24
  • $\begingroup$ +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... $\endgroup$ – draks ... Apr 10 '17 at 17:40
  • $\begingroup$ 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|)$ ... $\endgroup$ – draks ... Apr 10 '17 at 18:24

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.