Q:

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

A:

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 

