Eigenvectors of a circulant matrix
Show that for the circulant matrix
$$C = \begin{bmatrix} c_0 & c_{n-1} & \dots & c_{2} & c_{1} \\ c_{1} & c_0 & c_{n-1} & & c_{2} \\ \vdots & c_{1}& c_0 & \ddots & \vdots \\ c_{n-2} & & \ddots & \ddots & c_{n-1} \\ c_{n-1} & c_{n-2} & \dots & c_{1} & c_0 \\ \end{bmatrix}$$
the eigenvectors are
$$v_j = \left(1,w_j,w_j^2,...w_j^{n-1}\right), \qquad j=0,1,..,n-1,$$
where $$w_j = \exp\left(2\pi i j/n\right)$$ is the $n$-th root of unity. Show that the $\left(v_j\right)$ are linearly independent.
To show that the $v_j$ are eigenvector the only way I know is to solve the difference equation associated to the characteristic polynomial of $C$ to get a unique eigenvalue $\lambda$. Then find $\text{ker}\left(C-\lambda I\right)$. Is there an another way?
As for linear independence, I don't see how to reduce the matrix $\{v_j\}$ whose column are the eigenvector $v_j$.
$\endgroup$ 62 Answers
$\begingroup$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.
$\endgroup$ 1 $\begingroup$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.)
$\endgroup$
