Let n, uj, and zk be defined as in Exercise 36. If Fn is the n n Fourier matrix, then

Chapter 5, Problem 37

(choose chapter or problem)

Let \(\omega_{n}, u_{j}\), and \(z_{k}\) be defined as in Exercise 36. If \(F_{n}\) is the \(n \times n\) Fourier matrix, then its (j,s) entry is

\(f_{j s}=\omega_{n}^{(j-1)(s-1)}=u^{s-1}\)

Let \(G_{n}\) be the matrix defined by

\(\begin{array}{rr}
g_{s k}=\frac{1}{f_{s k}}=\omega^{-(s-1)(k-1)}=z_{k}^{s-1}, & 1 \leq s \leq n, \\
& 1 \leq k \leq n
\end{array}\)

Show that the the (j, k) entry of \(F_{n} G_{n}\) is

\(1+u_{j} z_{k}+\left(u_{j} z_{k}\right)^{2}+\cdots+\left(u_{j} z_{k}\right)^{n-1}\)