Short question im having a tad difficulty with.
I'm trying to find the characteristic polynomial of a graph that is just a circle with n vertices and n edges.
I think the adjacency matrix should look something like this:
$\begin{pmatrix} 0 & 1 & 0 & 0 & \cdots & 1 \\[2mm]
1 & 0 & 1 & 0 & \cdots & 0 \\[2mm]
0 & 1 & 0 & 1 & \cdots & 0 \\
0 & 0 & 1 & 0 & \ddots & \vdots\\
\vdots & \vdots & \vdots& \ddots& \ddots& 1 \\[2mm]
1 & 0 & 0 & \cdots& 1 & 0\end{pmatrix}$
How do I find the characteristic polynomial of this matrix? The determinant is very difficult to calculate.
Best Answer
Your question is answered here (proposition 4): http://www.math.cornell.edu/~levine/18.312/alg-comb-lecture-18.pdf
Instead of finding the determinant of the adjacency matrix of the cycle graph, we try to find the eigenvalues of the square matrix. To that end, we turn the problem into solving a linear recurrence.
Edit: Thanks to Marc's helpful comments, the notes linked considers the adjacency matrix of a path graph whereas the OP's looking at the adjacency matrix of a cycle graph. The method of using linear recurrences to find the eigenvalues, however, is the same in both cases.