I have H obtained from an even cycle $C2k$ for $k>=2$ by adding edges joining vertices at a distance two in $C2k$.
I need to show that $A(H)=A(C2k)^2+A(C2k)-2I$ where $A=A(G)$ denotes the adjacency matrix of a graph G. Also, I need to find the eigenvalues of H in terms of the eigenvalues of C2k.
Can anyone help please?
First, let $A$ denote the adjacency matrix of a graph $G$. What is $A^2$? Well, in general $(A^k)_{uv}$ counts the number of walks of length $k$ starting at $u$ and ending at $v$. If I give you two vertices $u,v\in V(C_{2k})$, how many walks of length $2$ are there from $u$ to $v$? Well, if $u=v$, then there are $2$ and if $u\neq v$, then there is exactly $1$ if $\text{dist}(u,v)=2$ and $0$ otherwise! Therefore, $A(C_{2k})^2-2I$ has a $1$ in position $uv$ if and only if $\text{dist}(u,v)=2$. Also, $A(C_{2k})$ has a $1$ in position $uv$ if and only if $\text{dist}(u,v)=1$ and $A(H)$ has a $1$ in position $uv$ if and only if $\text{dist}(u,v)\in\{1,2\}$, so what can we conclude?
As for eigenvalues, recall from linear algebra that if $\lambda$ is an eigenvalue of a matrix $A$, then $a_m\lambda^m+a_{m-1}\lambda^{m-1}+\dots+a_1\lambda+a_0$ is an eigenvalue of $a_mA^m+a_{m-1}A^{m-1}+\dots+a_1A+a_0I$.