Closed Walks Generating Functions in Cospectral Graphs

Question

This question is about the first couple slides of this presentation. First, regarding the generating function for the number of closed walks on a graph $G$, how does one prove that $$\sum_{r\geq0}\text{tr}(A^r)t^r=\frac{t^{-1}\phi'(G,t^{-1})}{\phi(G,t^{-1})}$$ where $A$ is the adjacency matrix of $G$ and $\phi(G,t)$ is its characteristic polynomial in terms of t? Next, how does one prove that two graphs $G$ and $H$ are cospectral if and only if their generating functions for closed walks are equal? (I think that this second question may actually be easier to address).

Answer 1

For the first result you're asking about, Lemma 2.1 in Spectral Conditions for the Reproducibility of a Graph by Godsil and McKay gets you 90% of the way there, but the proof is rather terse, so let me expand on it.

We can write the matrix generating function $\sum_{r \ge 0} A^r t^r$ very simply as $$ \sum_{r \ge 0} A^r t^r = (I - At)^{-1} = t^{-1} (t^{-1}I - A)^{-1}.$$ By Cramer's rule, the $(i,i)$ entry of $(t^{-1}I - A)^{-1}$ is equal to $$\frac{\det(t^{-1}I - A_i)}{\det(t^{-1}I - A)}$$ where $A_i$ is the submatrix formed by deleting the $i^{\text{th}}$ row and $i^{\text{th}}$ column of $A$. Summing over all $i$, we get $$\sum_{r \ge 0} \text{tr}(A^r) t^r = \frac{t^{-1} \sum_{i=1}^n \det(t^{-1}I - A_i)}{\det(t^{-1}I - A)}.$$ Now, first of all, the denominator $\det(t^{-i}I - A)$ is just $(-1)^n \det(A - t^{-1} I) = (-1)^n \phi(G,t^{-1})$.

Second, and this is trickier to see (at least for me - I'm not used to cofactor manipulations) for any matrix $M$, the derivative of $\det(M)$ with respect to its $(i,i)^{\text{th}}$ entry is just $\det(M_i)$: in fact, $\det(M)$ is a linear function of its $(i,i)^{\text{th}}$ entry, and by the cofactor expansion rule for the determinant, $\det(M_i)$ is that entry's coefficient. Therefore $\phi'(G,x) = \frac{d}{dx}\det(A - xI)$, by the chain rule, is given by a sum $-\sum_{i=1}^n \det(A_i - xI)$.

So the numerator of the expression above is $$t^{-1} \sum_{i=1}^n \det(t^{-1}I-A_i) = (-1)^{n-1} t^{-1} \sum_{i=1}^n \det(A_i - t^{-1}I) = (-1)^n t^{-1} \phi'(G, t^{-1}).$$

Putting these together, we get the formula we wanted (the $(-1)^n$'s cancel): $$ \sum_{r \ge 0} \text{tr}(A^r) t^r = \frac{t^{-1} \phi'(G,t^{-1})}{\phi(G,t^{-1})}. $$

The answer to your second question is simply that two graphs are cospectral if and only if their characteristic polynomials are equal, the characteristic polynomials are equal if and only if the expressions $\frac{t^{-1} \phi'(G,t^{-1})}{\phi(G,t^{-1})}$ are equal, and as we've just proved this happens if and only if the closed walk generating functions are equal.

(To see the second step: in general, if $\frac{f'(x)}{f(x)} = \frac{g'(x)}{g(x)}$, then the derivative of $\frac{f(x)}{g(x)}$ is $0$, so $f(x) = cg(x)$. In this case, both leading coefficients of the characteristic polynomial are $1$, so the constant $c$ is also $1$.)