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.

  • $\begingroup$ An idea: did you try induction? (Disclaimer: I've no idea whether it'd help but I think it's worth a shot) $\endgroup$
    – DonAntonio
    Jan 6 '14 at 12:28
  • $\begingroup$ Is the last column $(1,0,\cdots,0)$ or is it $(1,0,\cdots,0,1,0)$? $\endgroup$
    – user114628
    Jan 6 '14 at 12:31
  • $\begingroup$ since vertix $n$ is a neighbor to $1$ and $n-1$ the last column is $(1,0,0,\cdots,0,1,0)$ $\endgroup$ Jan 6 '14 at 12:32
  • $\begingroup$ And yes I just tried induction...maybe there is a way but i didn't get anywhere. I cant see a correlation between case $n=k$ and $n=k+1$ $\endgroup$ Jan 6 '14 at 12:33

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.

  • 1
    $\begingroup$ In his case the eigenvalues are given by $2 \cos \frac{2k\pi}{n}$, $k=1,2,\cdots,n$ $\endgroup$
    – user114628
    Jan 6 '14 at 13:30
  • $\begingroup$ Note that the matrix in the paper linked to is not the one of this question, but rather the adjacency matrix of a linear graph. $\endgroup$ Jan 6 '14 at 14:55
  • $\begingroup$ So the matrix I wrote is wrong? $\endgroup$ Jan 6 '14 at 15:16
  • $\begingroup$ @Kuai: No you are wrong. The difference between the adjacency matrices of a linear (path) and of a cycle graph is only the entries at the extreme bottom-left and top-right, which are $1$ for the cycle, but $0$ for the path graph. The diagonal entries are $0$ in both cases. Oria Gruber, your matrix is correct. $\endgroup$ Jan 6 '14 at 15:40

As my friend has said we must find the characteristic polynomial as the product of factors and solve an inductive sequence and we will be done.


Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.