# Circulant matrix equivalent to a unitary and diagonal matrix

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.

• Note that the columns of $Q$ must be (left) eigenvectors of $C_n$. Note that we are diagonalizing the matrix $C_n$. – Omnomnomnom Jan 15 '16 at 21:55
• 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). – Omnomnomnom Jan 15 '16 at 21:57
• How would you know which one is which? Since you are asked to find $Q_n$ – Wolfy Jan 16 '16 at 1:28

## 1 Answer

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.

• 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? – Wolfy Jan 17 '16 at 1:25
• I have not... I know numpy handles that stuff pretty easily though. – Omnomnomnom Jan 17 '16 at 1:26
• 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? – Wolfy May 11 '16 at 10:43
• @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. – Omnomnomnom May 11 '16 at 14:23
• I am not sure if I understand your statement. What do you mean? – Wolfy May 11 '16 at 14:28