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
