3
$\begingroup$

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$
  • 1
    $\begingroup$ Well, there is still the good old way: check that $Cv_j=w_jv_j$ directly. $\endgroup$ – Julien Feb 8 '13 at 0:26
  • $\begingroup$ @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$. $\endgroup$ – user14108 Feb 8 '13 at 0:37
  • 1
    $\begingroup$ Note that the eigenvalues are given here, for instance: en.wikipedia.org/wiki/Circulant_matrix $\endgroup$ – Julien Feb 8 '13 at 0:39
  • 2
    $\begingroup$ 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 $\endgroup$ – Julien Feb 8 '13 at 0:41
  • 1
    $\begingroup$ 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$. $\endgroup$ – Julien Feb 8 '13 at 0:45
3
$\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$
  • $\begingroup$ Awesome solution! :D Thanks Aspect! :) $\endgroup$ – AIM_BLB May 30 '15 at 17:01
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$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy