# DFT and the unitary matrix

Let $F_n\in\mathbb{C}^{n\times n}$ be the unitary matrix representing the discrete Fourier transform of length $n$ and so $F_n^{H}\in\mathbb{C}^{n\times n}$ is the inverse DFT of length $n$. For example, for $n = 4$ $$F_4 = \frac{1}{2} \left( \begin{array}{cccc} 1 & 1 & 1 & 1 \\ 1 & \mu & \mu^2 & \mu^3 \\ 1 & \mu^2 & \mu^4 & \mu^6 \\ 1 & \mu^3 & \mu^6 & \mu^9 \\ \end{array} \right) \ \ \text{and} \ \ F_4^{H} = \frac{1}{2} \left( \begin{array}{cccc} 1 & 1 & 1 & 1 \\ 1 & \omega & \omega^2 & \omega^3 \\ 1 & \omega^2 & \omega^4 & \omega^6 \\ 1 & \omega^3 & \omega^6 & \omega^9 \\ \end{array} \right)$$ where $\theta = 2\pi/n$, $\omega = e^{i\theta}$ and $\mu = e^{-i\theta}$.

Let $Z_n\in\mathbb{C}^{n\times n}$ be the permutation matrix of order $n$ such that $Zv$ represent the circulant "upshift" of the elements of the vector $v$, i.e., $$Z_n = \left(e_n \ \ e_1 \ \ e_2 \ \ \ldots \ \ e_{n-1}\right)$$ For example, for $n = 4$ $$Z_4 = \left( \begin{array}{cccc} 0 & 1 & 0 & 0 \\ 0 & 0 & 1 & 0 \\ 0 & 0 & 0 & 1 \\ 1 & 0 & 0 & 0 \\ \end{array} \right)$$ Let $C_n\in\mathbb{C}^{n\times n}$ be a circulant matrix of order $n$. The circulant matrix $C_n$ has $n$ parameters (either the first row or first column can be viewed as these parameters). It is a Toeplitz matrix (all diagonals are constant) with the additional constraint that each row (column) is a circulant shift of the previous row (column).

For example, for $n = 4$ and using the first row as the parameters we have $$C_4 = \left( \begin{array}{cccc} \alpha_0 & \alpha_1 & \alpha_2 & \alpha_3 \\ \alpha_3 & \alpha_0 & \alpha_1 & \alpha_2 \\ \alpha_2 & \alpha_3 & \alpha_0 & \alpha_1 \\ \alpha_1 & \alpha_2 & \alpha_3 & \alpha_0 \\ \end{array} \right)$$ Given a polynomial of degree $d$, a matrix polynomial is defined as follows $$P_d(\xi) = \delta_0 + \delta_1\xi + \delta_2\xi^2 + \ldots + \delta_d\xi^d$$ $$P_d(A) = \delta_0 I + \delta_1 A + \delta_2 A^2 + \ldots + \delta_d A^d$$ $$\xi\in\mathbb{C}, \delta_i\in\mathbb{C}, P_d(A),A\in\mathbb{C}^{n\times n}$$

Questions:

i.) Recall, that the set of $n\times n$ matrices is a vector space with dimension $n^2$. Show that the set of $n\times n$ circulant matrices, $C_n$, is a subspace of that vector space with dimension $n$.

ii.) Determine matrices $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.

iii.) Describe how you determine if $C_n$ is a nonsingular matrix.

Beginning solution of 1: 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}$$ The associated polynomial is $f(x) = \alpha_0 + \alpha_1 x + \ldots + \alpha_{n-1}x^{n-1}$

I am lost on how to begin these problems, any suggestions is greatly appreciated

• Your $Z_4$ is transposed from what it's supposed to be – Omnomnomnom Jan 14 '16 at 17:18
• Oh, never mind, you're using row-vectors! Everything is good. – Omnomnomnom Jan 14 '16 at 17:33

Hints:

• For i: note that as soon as you know the first row of a circular matrix, the entire matrix is determined. Use the first row, then, to construct a basis of $n$ matrices for the space of circulant matrices.

• Alternatively, note that the circulant matrices is exactly the matrices which can be written in the form $P_{n}(Z_n)$. You may notice that this is equivalent to the first hint. However, this version is more useful to the next step.

• For ii: By the previous hint, it suffices to find $Q_n$ such that $$Z_n = Q_n \Gamma_n Q_n^H$$

• For iii: Think polynomials, and think eigenvalues

• Thank you for the hints, but I am still stuck. For i.), do I need to show that: 1. $C_n$ is nonempy, 2. If $x,y\in C_n$ then $x+y\in C_n$, and 3. If $\alpha\in\mathbb{C}$ and $x\in C_n$, then $\alpha x\in C_n$? – Wolfy Jan 14 '16 at 18:58
• @MorganWeiss I suppose that is one option. However, I would say that all of these properties follow quickly from the second hint. Whether this is a sufficient explanation or not depends on your instructor. – Omnomnomnom Jan 14 '16 at 20:07
• I see, could you go further with your second hint so I can understand it more, sort of struggling still with this. – Wolfy Jan 14 '16 at 20:44
• @Morgan try plugging $Z_3$ into a few polynomials and see what happens. The coefficients of the polynomials should become the entries – Omnomnomnom Jan 14 '16 at 20:50
• Do you mean $C_3$? – Wolfy Jan 14 '16 at 21:32