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:
-
Determine a diagonal matrix $\Lambda_n\in\mathbb{C}^{n\times n}$ i.e., nonzero elements on the main diagonal, that satisfies $Z_n F_n^{H} = F_n^{H}\Lambda_n$.
-
Derive a relationship between $Z_n^{k}$ and $\Lambda_n^{k}$ for $0\leq k \leq n-1$ that expresses $Z_n^{k}$ as a factorization with three matrices of the form $Z_n^{k} = A_k\Lambda_n^{k}B_k$, i.e., determine $A_k\in\mathbb{C}^{n\times n}$ and $B_k\in\mathbb{C}^{n\times n}$
solution 1: For $n = 4$, we have $$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) \ \ \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) $$ We want to find a $\Lambda_4$ that satisfies $Z_4 F_4^{H} = F_4^{H}\Lambda_4$. So, $$Z_4F_4^{H} = \left( \begin{array}{cccc}
1/2 & \omega/2 & \omega^2/2 & \omega^3/2 \\
1/2 & \omega^2/2 & \omega^4/2 & \omega^6/2 \\
1/2 & \omega^3/2 & \omega^6/2 & \omega^9/2 \\
1/2 & 1/2 & 1/2 & 1/2 \\
\end{array} \right) = \left( \begin{array}{cccc}
1/2 & 1/2 & 1/2 & 1/2 \\
1/2 & \omega/2 & \omega^2/2 & \omega^3/2 \\
1/2 & \omega^2/2 & \omega^4/2 & \omega^6/2 \\
1/2 & \omega^3/2 & \omega^6/2 & \omega^9/2 \\
\end{array} \right)
\left( \begin{array}{cccc}
a & 0 & 0 & 0 \\
0 & b & 0 & 0 \\
0 & 0 & c & 0 \\
0 & 0 & 0 & d \\
\end{array} \right)$$
$$ = \left( \begin{array}{cccc}
a/2 & b/2 & c/2 & d/2 \\
a/2 & b\omega/2 & c\omega^2/2 & d\omega^3/2 \\
a/2 & b\omega^2/2 & c\omega^4/2 & d\omega^6/2 \\
a/2 & b\omega^3/2 & c\omega^6/2 & d\omega^9/2 \\
\end{array} \right) $$
There does seem to be a solution here, any suggestions is greatly appreciated.
solution 2: Now, we need to derive a relationship between $Z_n^{k}$ and $\Lambda_n^{k}$ for $0\leq k\leq n-1$ that expresses $Z_n^{k}$ as a factorization with three matrices of the form $Z_n^{k} = A_k\Lambda_n^{k}B_k$. Let $n = k = 4$, so we have $$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) = \left(\begin{array}{cccc}
a & b & c & d \\
e & f & g & h \\
i & j & k & l \\
m & n & o & p \\
\end{array} \right) \left( \begin{array}{cccc}
1 & 0 & 0 & 0 \\
0 & \omega & 0 & 0 \\
0 & 0 & \omega^2 & 0 \\
0 & 0 & 0 & \omega^3 \\
\end{array} \right)\left(\begin{array}{cccc}
a' & b' & c' & d' \\
e' & f' & g' & h' \\
i' & j' & k' & l' \\
m' & n' & o' & p' \\
\end{array} \right) $$
As an aside, if we take the matrix $F_n$ and the polynomial defined above we can get $A_k$ and $B_k$ but I fail to see this. So essentially, $$P_d(F_n) = \delta_0 + \delta_1 F + \delta_2 F + \ldots + \delta_d F^d$$ and I guess that by doing this we can supposedly get $A_k$ and $B_k$.
I am confused how to proceed further, any suggestions is greatly appreciated.
Best Answer
the $N$-discrete Fourier transform of $x$ is :
$$X(k) = \sum_{n=0}^{N-1} x(n) e^{-2 i \pi \textstyle\frac{n k}{N}}$$
think to $x(n)$ as a $N$-periodic signal $x(n) = x(n+N)$, so that for any $a \in \mathbb{Z}$ :
$$X(k) = \sum_{n=0}^{N-1} x(n+a) e^{-2 i \pi \textstyle\frac{(n+a) k}{N}}$$
that $N$-periodic point of view on $x$ is useful because $X(k)$ is itself $N$-periodic, as is the inverse discrete Fourier transform of $X(k)$.
also, a shifted version of $x$ can simply be written : $$y_a(n) = x(n+a)$$
thus the discrete Fourier transform of $y_a(n)$ is : $$Y_a(k) = \sum_{n=0}^{N-1} y(n) e^{-2 i \pi \textstyle\frac{n k}{N}} = \sum_{n=0}^{N-1} x(n+a) e^{-2 i \pi \textstyle\frac{n k}{N}} = e^{ 2 i \pi \textstyle\frac{a k}{N}} \sum_{n=a}^{N-1} x(n+a) e^{-2 i \pi \textstyle\frac{(n+a) k}{N}} = e^{2 i \pi \textstyle\frac{a k}{N}} X(k)$$