Characteristic Polynomial of transition matrix of $n$-cycle

Question

Let $P$ be the transition matrix of the deterministic random walk on the cycle $C_n$, i.e. $P \in \{0,1\}^{n \times n}$ with

$$P_{i,j}=1\quad \text{ iff }\quad j=i+1 \mod n.$$

My guess is that the characteristic polynomial is given by

$$det(P-I x)=\begin{cases} x^n-1, & n \text{ even}\\1-x^n, & n \text{ odd}\end{cases},$$

but I have no idea how to derive it and also no idea how to prove it. How would one do this?

Answer 1

You want to compute the determinant
$$ \begin{vmatrix} -x & 1 & & \\ & -x & \ddots & \\ & & \ddots & 1 \\ 1 & & & -x \end{vmatrix} $$ I suggest you expand along the first column (I gave it some thought ; no induction needed here). Feel free to ask for details if you need more.

Hope that helps,