Is there a way to utilize the spectral mapping theorem to find the eigenvalues of a circulant matrix if eigenvectors of P are known?
From this wiki page, I know that $C=c_0I+c_1P+c_2P^2+...+c_{n-1}P^{n-1}$ (P is a shift matrix, it is shown in the link)
I think with the given equality, I can use the spectral mapping theorem to find the eigenvalues of $C$ but not quite sure how to get started.
$P$ is unitary and thus normal, and hence admits an orthonormal basis of eigenvectors. However, from the fact that $C$ is a polynomial of $P$, it would follow that each of these eigenvectors is also an eigenvector of $C$. Furthermore, we can easily calculate the coefficients $c_0, c_1, \cdots, c_{n - 1}$ by just inspecting the matrix $C$. (Hint: they are exactly the elements of the first column, from top to bottom. You can prove this iteratively by showing that the only contribution to the elements on the diagonal are $c_0 I$, the contribution to the elements right under the diagonal and in the top right corner are from the term $c_1 P$, and so on.)
It is helpful to note that the eigenvalues of the shift matrix are the $n$ roots of unity, where $n$ is the order of the matrix. So for example, if $\vec{v}$ is the vector such that $P \vec{v} = e^{2\pi i/ n} \vec{v} = \omega \vec{v}$, then $$C \vec{v} = (c_0 + c_1 \omega + c_2 \omega^2 + \cdots + c_{n - 1} \omega^{n - 1}) \vec{v}$$ Can you sort out the general case from here? (Another remark: if you want to efficiently calculate all eigenvalues, you can use the Fast Fourier transform to do this in $\Theta(n \log n)$ operations.)