TAOCP 4.6.4 Exercise 13
Let the general discrete Fourier transform (37) be f(s_1,\ldots,s_n) = \sum_{t_1=0}^{m_1-1} \cdots
Section 4.6.4: Evaluation of Polynomials
Exercise 13. [M23] Find the inverse of the general discrete Fourier transform (37), by expressing $F(t_1, \ldots, t_n)$ in terms of the values of $f(s_1, \ldots, s_n)$. [Hint: See Eq. 1.2.9–(13).]
Verified: yes
Solve time: 1m16s
Solution
Let the general discrete Fourier transform (37) be
$$ f(s_1,\ldots,s_n) = \sum_{t_1=0}^{m_1-1} \cdots \sum_{t_n=0}^{m_n-1} F(t_1,\ldots,t_n) , \omega_1^{,s_1t_1} \cdots \omega_n^{,s_nt_n}, \tag{37} $$
where
$$ \omega_j=e^{2\pi i/m_j}, \qquad 0\le s_j,t_j<m_j . $$
We seek an expression for $F$ in terms of the values of $f$.
Multiply both sides of (37) by
$$ \omega_1^{-s_1u_1}\cdots \omega_n^{-s_nu_n}, $$
and sum over all $s_1,\ldots,s_n$:
$$ \sum_{s_1=0}^{m_1-1}\cdots \sum_{s_n=0}^{m_n-1} f(s_1,\ldots,s_n) \omega_1^{-s_1u_1}\cdots \omega_n^{-s_nu_n} $$
$$= \sum_{t_1,\ldots,t_n} F(t_1,\ldots,t_n) \prod_{j=1}^n \left( \sum_{s_j=0}^{m_j-1} \omega_j^{,s_j(t_j-u_j)} \right).$$
By the root-of-unity identity of Eq. 1.2.9-(13),
$$ \sum_{s_j=0}^{m_j-1} \omega_j^{,s_j(t_j-u_j)} = \begin{cases} m_j,& t_j=u_j,\ 0,& t_j\ne u_j. \end{cases} $$
Hence every term on the right vanishes except the term with
$$ t_1=u_1,\ldots,t_n=u_n. $$
Therefore
$$ \sum_{s_1=0}^{m_1-1}\cdots \sum_{s_n=0}^{m_n-1} f(s_1,\ldots,s_n) \omega_1^{-s_1u_1}\cdots \omega_n^{-s_nu_n} = (m_1\cdots m_n), F(u_1,\ldots,u_n). $$
Solving for $F(u_1,\ldots,u_n)$ gives the inverse transform:
$$ F(u_1,\ldots,u_n) = \frac1{m_1\cdots m_n} \sum_{s_1=0}^{m_1-1}\cdots \sum_{s_n=0}^{m_n-1} f(s_1,\ldots,s_n) \omega_1^{-s_1u_1} \cdots \omega_n^{-s_nu_n}. $$
Replacing $u_j$ by $t_j$, we obtain
$$ \boxed{ F(t_1,\ldots,t_n) = \frac1{m_1\cdots m_n} \sum_{s_1=0}^{m_1-1}\cdots \sum_{s_n=0}^{m_n-1} f(s_1,\ldots,s_n) \omega_1^{-s_1t_1} \cdots \omega_n^{-s_nt_n} }. $$
This is the inverse of the general discrete Fourier transform (37). ∎