# Circulant matrix : eigenvector

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), \; 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$.

-
Well, there is still the good old way: check that $Cv_j=w_jv_j$ directly. – 1015 Feb 8 '13 at 0:26
@julien For linear independence, I didn't realized the eigenvalues were distinct, thanks. For the good old way, say the first row of $w_jv_j$, I don't see how to show: $c_0+\sum_{x=1}^{n-1}c_{n-x}w_j^x=w_j$. – Nicolas Essis-Breton Feb 8 '13 at 0:37
Note that the eigenvalues are given here, for instance: en.wikipedia.org/wiki/Circulant_matrix – 1015 Feb 8 '13 at 0:39
My previous comment was irrelevant, sorry, I deleted it (the eigenvaluews are not necessarily pairwise distinct without further information on the $c_k$'s). To prove linear independence, you can use VanderMonde determinant, for instance: en.wikipedia.org/wiki/Vandermonde_matrix – 1015 Feb 8 '13 at 0:41
The eigenvalue of $v_j$ is $c_0+c_{n-1}w_j+\ldots+c_1w_j^{n-1}$. To check that, all you have to do is compute $Cv_j$ and factor out $w_j$ on the second coordinate, $w_j^2$ on the third coordinate and so on... Using of course that $w_j^n=1$. – 1015 Feb 8 '13 at 0:45

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.