Tag Archives: trace formula

A simple trace formula for graphs

Posted on by

Let \Gamma=(V,E) be a simple, connected graph with vertices V={0,1,\dots, n-1} and n\times n adjacency matrix A. We start with the geometric series identity

\frac{1}{I-tA} = \sum_{\ell=0}^\infty t^\ell A^\ell,
where I=I_n is the n\times n identity matrix. Let P denote the orthonormal matrix of normalized eigenvectors, so that

PAP^{-1} = D_\Gamma, D_\Gamma = {diag}(\lambda_1,\dots,\lambda_n),
where diag(…) denotes the diagonal matrix with the given entries on the diagonal. Let the multi-set

Spec(\Gamma)={\lambda_0,\lambda_1\dots,\lambda_{n-1}}
denote the spectrum of \Gamma.

We can conjugate the above equation by P to write

\frac{1}{I-tD_\Gamma}= P\cdot [\sum_{\ell=0}^\infty t^\ell A^\ell]\cdot P^{-1}.
Taking the trace of each side gives

\sum_{j=0}^{n-1} \frac{1}{I-t\lambda_j} = \sum_{\ell=0}^\infty t^\ell tr(A^\ell).
If \Gamma has no eigenvalues equal to 0 (i.e., A is non-singular) then we may also write this as

\sum_{j=0}^{n-1} \frac{\lambda_j^{-1}}{\lambda_j^{-1}-t} = \sum_{\ell=0}^\infty t^\ell tr(A^\ell).

If we multiply both sides of the above equation by a fixed f\in C_c^\infty({\mathbb{R}})
and integrate over t in {\mathbb{R}}, we get,

\sum_{j=0}^{n-1} \lambda_j^{-1}H(f)(\lambda_j^{-1}) = {\frac{1}{\pi}}\sum_{\ell=0}^\infty tr(A^\ell) [M(f)(\ell+1)+(-1)^\ell M(f^*)(\ell+1)],
where H denotes the Hilbert transform

H(f)(z) = \frac{1}{\pi}P.V.\int_{-\infty}^\infty \frac{f(t)}{z-t}\, dt, and M is the Mellin transform

M(f)(z) = \int_{0}^\infty t^{z-1}f(t)\, dt,
and where f^* denotes the negation, f^*(t)=f(-t). Of course, if f is even then M(f)(\ell+1) = M(f^*)(\ell+1), for all \ell.

Note that tr(A^\ell) can be expressed in terms of the number of walks on the graph: If \Gamma is a connected graph and W_\ell=W_\ell(\Gamma) denotes the total number of walks of length \ell on \Gamma then

W_\ell = {\rm tr}(A^\ell)=\sum_{\lambda\in Spec(\Gamma)} \lambda^\ell.