Let $G$ be a simple graph on $n$ vertices, and let $\lambda_1\ge \lambda_2 \ge \dots \ge \lambda_n$ be the eigenvalues of its adjacency matrix $A$. Given a matrix $M$ of size $n \times n$, the trace of a matrix $tr(M)=\sum_{i=1}^n M(i,i)$. Let $A^k=A \times A \times A \times \dots \times A$ (here, the matrix is multiplied with itself $k$ times).
Assume you are given the following identity for any symmetric matrix $M$ of size $ n \times n$ (you don't need to prove this): $ tr(M)= \sum_{i=1}^n \lambda_i (M),$ where $\lambda_i(M)$ is the $i$th largest eigenvalue of $M$. Then, prove that $$\text{Number of closed walks in G of length exactly }k = \sum_{i=1}^n \lambda_i^k. $$
Best Answer
Assumption: $A_{i,j} = 1$ if $i\sim j$ and otherwise $A_{i,j}=0$.
Let $\Gamma_k$ denote the set of sequences in $V$ of length $k$. An element $\overline{v}\in \Gamma_k$ is of the form $\overline{v} = (v_1,\dots,v_k)$.
A path of length $k$ is an element in $\Gamma_k$ satisfying $v_{i+1} \sim v_i$ for $i=1,\dots,k-1$. A path from $i$ to $j$ of length $k$ is a path with $v_1=i$ and $v_k=j$.
A loop of length $k$ is a path of length $k$ satisfying $v_1=v_k$.
Next, by definition of matrix multiplication
$$A^k_{i,j} =\sum_{\overline{v}\in \Gamma_k:v_1=i,v_k=j}A_{v_1,v_2}A_{v_2,v_3}\dots A_{v_{k-1},v_k}$$
Also, the product on the RHS is nonzero if and only if $\overline{v}$ is a path from $i$ to $j$ of length $k$, and in this case, the product is equal to $1$.
Therefore,
$$A^k_{i,j}=\# \{\mbox{paths from }i\mbox{ to }j\mbox{ of length }k\}.$$
As a result, $\sum_{i} A^k_{i,i}$ is the number of loops of length $k$.