On the walk-generating function

73 Views Asked by At

While I was reading Norman Biggs' Algebraic Graph Theory I came across the following (Page 12 2g) exercise/additional result:

Let $g_{ij}(r)$ denote the number of walks of length $r$ in $\Gamma$ from $v_i$ to $v_j$. If we write $\mathbf{G}(z)$ for the matrix $$ \mathbf{G}(z)_{ij}=\sum_{r=1}^{\infty} g_{ij}(r)z^r, $$ then $\mathbf{G}(z)=(\mathbf{I}-z \mathbf{A})^{-1}$, where $\mathbf{A}$ is the adjacency matrix of $\Gamma$. This may be regarded as a matrix over the ring of formal power series in $z$, or as a real matrix defined whenever $z^{-1} \notin \text{Spec}(\Gamma)$. From the formula for the inverse matrix and 2e, we obtain $$ \mathbf{G}(z)_{ii}=\frac{\chi(\Gamma_i;z^{-1})}{z\chi(\Gamma;z^{-1})}, \hspace{1cm}\text{tr}(\mathbf{G}(z))=\frac{\chi'(\Gamma;z^{-1})}{z \chi(\Gamma,z^{-1})}. $$

I was able to prove everything except the part where the matrix is real if $z^{-1} \notin \text{Spec}(\Gamma)$. The book has a typo, where instead of $z^{-1}$ it's written $z$, but according to the following paper it must be $z^{-1}$.

Paper: Walk generating functions and spectral measures of infinite graphs

Can someone give me some hints of why this happens?

Note: $\chi(\Gamma;\lambda)$ means the characteristic polynomial of $\Gamma$ and $\chi(\Gamma_i;\lambda)$ is the characteristic polynomial of the induced subgraph obtained from $\Gamma$ by removing the vertex $v_i$.