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
1  
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
1  
Note that the eigenvalues are given here, for instance: en.wikipedia.org/wiki/Circulant_matrix –  1015 Feb 8 '13 at 0:39
2  
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
1  
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

1 Answer 1

up vote 2 down vote accepted

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 & 0 & 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.

share|improve this answer
    
Awesome solution! :D Thanks Aspect! :) –  CSA May 30 at 17:01

Your Answer

 
discard

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

Not the answer you're looking for? Browse other questions tagged or ask your own question.