부산대학교 도서관

The paper under review gives a variant of the trace formula for regular graphs. The authors' motivation comes from the study of quantum walks on graphs, although they do not give an application of the obtained formula. \par The {\it Ihara zeta function} of $G$ is defined by the following Euler product: $$ Z(G, u) = \prod_{[C]} \left(1 - u^{|C|}\right)^{-1}, $$ where the product is over all equivalence classes of prime, reduced cycles of $G$. \par For regular graphs $G$, Ihara developed a formula for $Z(G, u)$ in terms of the eigenvalues of the adjacency matrix $A_G$. (Recall that in this matrix $a_{ij} = 1$ if $i$ and $j$ are adjacent in $G$ and 0 otherwise.) Let $\lambda_j$, $j = 1, \ldots, n$, be the eigenvalues of $A_G$, where $G$ is a ${(q+1)}$-regular graph on $n$ vertices. Then, Ihara's formula says that $$ \align \frac{1}{Z(G, u)} &= (1 - u^2)^{(q - 1)n/2}\det[(1 + qu^2)I - u A_G]\\ &=(1 - u^2)^{(q - 1)n/2} \prod_{j = 1}^n (1 - \lambda_j u + q u^2). \endalign $$ \par This formula and the definition of the zeta function can be used to derive the trace formula. (This formula is an analogue of the celebrated Selberg trace formula.) It can be formulated as follows. Let $h(\theta)$ be a complex-valued even $2\pi$-periodic function on $\Bbb{R}$, which can be analytically continued to the region $\Im \theta < \log(\sqrt q) + \epsilon$, with $\epsilon > 0$, and let $\widehat h(k)$, $k \in \Bbb Z$, be its Fourier transform. \par Let $\lambda_1, \ldots , \lambda_l$ be the eigenvalues of $A_G$ such that $1 - \lambda_j u + q u^2 = 0$ has an imaginary root. These roots are necessarily on the circle of radius $1/\sqrt q$ and we write $\theta_j \in (0, \pi)$ for the argument of the root corresponding to $\lambda_j$, $j = 1, \ldots, l$. \par Then, the trace formula for graphs says that $$ \align \sum_{j = 1}^l h(\theta_j) =& \frac{2 n q (q + 1)}{\pi}\int_0^\pi \frac{\sin^2 \theta}{(q + 1)^2 - 4 q \cos^2 \theta} h(\theta) \, d\theta\\ &+ \sum_{[C]} \sum_{m = 1}^\infty |C| q^{-m |C|/2}\, \widehat h(m |C|), \endalign $$ where the sum is over all equivalence classes of prime, reduced cycles of $G$ [cf. G. Ahumada, C. R. Acad. Sci. Paris Sér. I Math. {\bf 305} (1987), no.~16, 709--712; MR0920048; M.~D. Horton, D.~B. Newland and A.~A. Terras, in {\it The ubiquitous heat kernel}, 265--293, Contemp. Math., 398, Amer. Math. Soc., Providence, RI, 2006; MR2218022]. \par These formulas can be generalized to the case of weighted graphs which are not necessarily regular (see the references in the paper under review). \par Next, the Grover matrix of a graph $G$ arises in the study of quantum walks on graphs as the transition matrix of a quantum walk. By definition, it is a $2m\times 2m$ matrix $U$ whose rows and columns correspond to the oriented edges of $D(G)$ and $$ U_{ef} = \cases \frac{2}{d_t(f)}, & \text{if } t(f) = o(e) \text{ and } f \ne e^{-1},\\ \frac{2}{d_t(f)} - 1, & \text{if } f = e^{-1},\\ 0, & \text{otherwise}. \endcases $$ \par The zeta function of the graph $G$ with respect to the Grover matrix $U$ can be defined as an inverse of the characteristic polynomial of $U$ (up to multiplication by a power of~$u$): $$ \overline Z(G, u)^{-1} = \det[I_{2m} - u U]. $$ One can show that the eigenvalues of $U$ are closely related to the generalized eigenvalues of $A_G$. Namely (Theorem 4.2 and Corollary 4.2 in the paper), $$ \overline Z(G, u)^{-1} = \frac{(1 - u^2)^{m - n} \det[ (1 + u^2) D - 2 u A_G]}{\prod_{i = 1}^n d_i}, $$ where $D$ is the diagonal matrix $(d_1, d_2, \dots, d_n)$, with $d_i$ denoting the degree of the $i$-th vertex. \par This relation resembles the weighted version of Ihara's formula and suggests that one can write a corresponding trace formula. For regular graphs, this is done in Theorem~5.1 of the paper under review.