Graph Eigenvalues

Linear-algebraic preliminaries

Let $M$ be $p\times p$ real symmetric matrix. $\lambda_1, \lambda_2, \cdots, \lambda_p$ are real eigenvalues.

Counting walks in graphs

Let $G$ graph (unoriented, loops and multiple edges are allowed) on the vertex set $\{ 1, 2, \cdots, p\}$. Let $A(G)$ be the adjacency matrix of $G$.

Key observation

Success Number of walks of length $l$ from $i$ to $j$ $= (M^l)_{ij}$.

Use multiplication rule we get

Success Number of marked closed walks of length $l$ in $G$ $=tr(M^l) = \sum_k \lambda_{k}^l$.