I need to calculate the characteristic polynomial and eigenvalues of the following matrix. It's been a long time since my linear algebra courses, so I have pretty much lost the ability to compute such things by hand. Can someone perhaps help me?
$$\left( \begin{array}{cc} r & p & 0 & & & & & &q\\ q & r & p & 0 \\ 0 & q & r & p & 0 \\ 0 & 0 & q & r & p & 0 \\ ... & & & ... & ... & ... \\ p & 0 & & & & & 0 & q & r \end{array} \right) $$
Call your matrix $A$ which is $pA_1 + qA_2 + rI$ where $A_1$ and $A_2$ are defined accordingly. You are lucky that $A_1 , A_2$ and $I$ have the same eigenvectors. The reason for this is $A_1$ and $A_2$ are adjacency matrices for isomorphic directed graphs. Indeed $A_1^{n-1} =A_2$.
Now let's see the eigenvalues of $A_1$. It's characteristic polynomial is $t^n -1$ (where $A$ is a $n \times n$ matrix), so the eigenvalues are the $n^{th}$ roots of unity! Now if $x$ is an eigenvector of $A_1$ with eigenvalue $\lambda$, then $$(pA_1 +qA_2 + rI)x = (pA_1 +qA_1^{n-1} + rI)x = p\lambda x + q \lambda^{n-1} x + rx = (p \lambda + q \lambda^{n-1} + r)x.$$
Let $\xi$ be any primitive $n^{th}$ root of unity. Then the eigenvalues are $$(p \lambda + q \lambda^{n-1} + r),$$ where $\lambda = \xi^i$ for $0 \leq i \leq n-1$.