Eigenvectors of a circulant matrix

I can give you a brief outline of an alternative way to do it.

Consider the following matrix. $$ \quad Q= \begin{pmatrix} 0 & 0 & \dots & 1 \\ 1 & 0 & \dots & 0 \\ 0 & 1 & \dots & 0 \\ \vdots & \vdots & \vdots & \vdots \\ 0 & 0 & \dots & 0\\ \end{pmatrix} $$

First show that $$ p(Q)= c_{0}Q^{0} + c_{1}Q^{1} + c_{2}Q^{2} + \dots + c_{n-1}Q^{n-1}= C$$

Then using the DFT matrix F, it can be shown that : $$ FQ^{m}F^{-1}= \begin{pmatrix} 1 & 0 & \dots & 0 \\ 0 & \xi^{(m \ modn)} & \dots & 0 \\ 0 & \vdots & \xi^{2(m \ modn)} & 0 \\ \vdots & \vdots & \vdots & \vdots \\ 0 & \dots & \dots & \xi^{(n-1)(m \ modn)}\\ \end{pmatrix} = D_{m} \\ \\ $$ The final step is: $$ Fp(Q)F^{-1} = \quad \quad \begin{pmatrix} p(1) & 0 & \dots & 0 \\ 0 & p( \xi) & \dots & 0 \\ 0 & \vdots & p( \xi^{2}) & 0 \\ \vdots & \vdots & \vdots & \vdots \\ 0 & \dots & \dots & p( \xi^{(n-1)})\\ \end{pmatrix} =FCF^{-1} $$ The circulant is diagonalized by the DFT matrix.

As a brief follow-up on Aspect's response (As this thread still appears to get quite a few views), if you don't want to use the language of Fourier analysis, you can also note that as Aspect pointed out $\displaystyle C = \sum_{i=0}^{n-1} c_iQ^{i}$. Therefore, it is sufficient to show that the $v_j$ vectors are eigenvectors of $Q$ (say with eigenvalues $\lambda_j$), as then we find that

$$Cv_j = \sum_{i=0}^{n-1} c_iQ^{i}v_j = \left(\sum_{i=0}^{n-1} c_i\lambda_j^{i}\right)v_j.$$ Note that this actually shows more, as we now have found an explicit formula for the eigenvalues in terms of the entries of the circulant matrices and the eigenvalues of the matrix $Q$. (It is a straight-forward exercise to show that the eigenvalues of $Q$ are the n$^{th}$ roots of unity.)