Take the 2-minute tour ×
Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. It's 100% free, no registration required.

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$.

share|improve this question
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
show 1 more comment

Your Answer


By posting your answer, you agree to the privacy policy and terms of service.

Browse other questions tagged or ask your own question.