We have that $C_n\in\mathbb{C}^{n\times n}$ is a circulant matrix of order n. So we have $$ C_n = \begin{bmatrix} \alpha_0 & \alpha_{n-1} & \dots & \alpha_{2} & \alpha_{1} \\ \alpha_{1} & \alpha_0 & \alpha_{n-1} & & \alpha_{2} \\ \vdots & \alpha_{1}& \alpha_0 & \ddots & \vdots \\ \alpha_{n-2} & & \ddots & \ddots & \alpha_{n-1} \\ \alpha_{n-1} & \alpha_{n-2} & \dots & \alpha_{1} & \alpha_0 \\ \end{bmatrix}$$

Now we need to determine $Q_n$ and $\Gamma_n$ such that $$C_n = Q_n\Gamma_n Q_n^{H}$$ where $Q_n\in\mathbb{C}^{n\times n}$ is a unitary matrix and $\Gamma_n\in\mathbb{C}^{n\times n}$ is a diagonal matrix.

It seems to me that since $Q_n$ is a unitary matrix, then isn't $Q_n Q_n^{H}$ just equal to the identity matrix? If that is the case then we just need to find a diagonal matrix $\Gamma_n$?

I am not sure on this, any suggestions is greatly appreciated.

  • $\begingroup$ Note that the columns of $Q$ must be (left) eigenvectors of $C_n$. Note that we are diagonalizing the matrix $C_n$. $\endgroup$ – Omnomnomnom Jan 15 '16 at 21:55
  • $\begingroup$ The real trick here is that we can set $Q$ to be the DFT matrix (or possibly it's $Q^H$ that's the DFT matrix; haven't checked which). $\endgroup$ – Omnomnomnom Jan 15 '16 at 21:57
  • $\begingroup$ How would you know which one is which? Since you are asked to find $Q_n$ $\endgroup$ – Wolfy Jan 16 '16 at 1:28

It comes down to the following: set $Q_n$ equal to $F_n$, the DFT matrix (as you defined it here).

Note: for the rest of the question, I stop using the subscript $n$, so $Q_n$ is just $Q$. Also, I continue to use notation from the original question.

First, notice that when $C = Z$, we indeed find that $Z = F\Gamma_Z F^H$, where $$ \Gamma_Z = \pmatrix{1 \\ & \omega \\ && \ddots \\ &&& \omega^{n-1}} $$ Now, for an arbitrary circulant $C$, let $f_C(x) = \sum_k \alpha_k x^k$ denote the associated polynomial of $C$. We note that $C = f_C(Z)$. A neat consequence of this is that $$ C = f_C(Z) = f_C(F\Gamma_Z F^H) = \sum_k \alpha_k (F\Gamma_Z F^H)^k = \\ \sum_k \alpha_k F\Gamma_Z^k F^H = F\left(\sum_k \alpha_k \Gamma_Z^k \right)F^H = \\ Ff_C(\Gamma_Z)F^H $$ Moreover, because $\Gamma_Z$ is diagonal, we have the neat result $$ f_C(\Gamma_Z) = \pmatrix{f_C(1) \\ & f_C(\omega) \\ && \ddots \\ &&& f_C(\omega^{n-1})} $$ So, setting $Q$ equal to $F$ diagonalizes any circulant matrix $C$.

As for part iii of your original query, $C$ is non-singular if and only if $f_C(\omega^k)\neq 0$ for $k=0,1,\dots,n-1$.

There are more efficient, equivalent ways to check this condition assuming your $C_n$ is a real matrix, but this certainly does the job.

  • $\begingroup$ By the way, I am not sure if you know how to do this. But have you ever worked with C++ and initialized a complex matrix before? $\endgroup$ – Wolfy Jan 17 '16 at 1:25
  • $\begingroup$ I have not... I know numpy handles that stuff pretty easily though. $\endgroup$ – Omnomnomnom Jan 17 '16 at 1:26
  • $\begingroup$ So we first set $Q_n = F_n$ and notice that $C_n = Z_n$ and we found in another problem that $Z_n = F_n\Lambda_n F_n^{H}$ where $\Lambda_n$ is also a diagonal matrix. So, essentially we see that $\Gamma_n = \Lambda_n$ why do we have to continue after this? $\endgroup$ – Wolfy May 11 '16 at 10:43
  • $\begingroup$ @Wolfy I think that if that were all that I had said, you would have been pretty confused. The trick here is unpacking what "$\Gamma_n$ is essentially the same as $\Lambda_n$" is supposed to mean. $\endgroup$ – Omnomnomnom May 11 '16 at 14:23
  • $\begingroup$ I am not sure if I understand your statement. What do you mean? $\endgroup$ – Wolfy May 11 '16 at 14:28

Your Answer

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

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