As I understand your question, you are starting with a regular graph of degree $4$ and adding a single edge, so that the graph is no longer regular and no longer a Cayley graph. In that case, if $n=5$, your graph on vertex set $\{0,1,2,3,4\}$ has 11 edges $01, 02, 12, 13, 23, 24, 34,30, 40,41$ and $03$ and the adjacency matrix you give is incorrect.
The regular graph (as Pat Devlin says) has real eigenvalues which are sums of roots of unity. (They are all of the form $2\cos(2c\pi/p)+2\cos(4c\pi/p)$ for integers $c$, $0 \le c \le (p-1)/2$.) It is not immediately clear what the single edge does to the spectrum; yes, it will "perturb" these real numbers into other real numbers, presumably numbers close to the original sums of roots of unity. I think a question about the perturbation of eigenvalues by adding just one edge is a good one.
