FT AS AN INVERTIBLE MATRIX

A Fourier sum may be written

$$B(\omega) \eq \sum_t \ b_t \ e^{i\omega t} \eq \sum_t \ b_t \ Z^t$$ (1)

where the complex value Z is related to the real frequency $\omega$ by $Z=e^{i\omega}$.This Fourier sum is a way of building a continuous function of $\omega$from discrete signal values b_t in the time domain. In this chapter we will study the computational tricks associated with specifying both time and frequency domains by a set of points. Begin with an example of a signal that is nonzero at four successive instants, ( b₀, b₁, b₂, b₃). The transform is

$$B(\omega) \eq b_0 + b_1 Z + b_2 Z^2 + b_3 Z^3$$ (2)

The evaluation of this polynomial can be organized as a matrix times a vector, such as  

$$\left[ \begin{array} {c} B_0 \ B_1 \ B_2 \ B_3 \end{a... ...gin{array} {c} b_0 \ b_1 \ b_2 \ b_3 \end{array} \right]$$ (3)

Observe that the top row of the matrix evaluates the polynomial at Z=1, a point where also $\omega=0$.The second row evaluates $B_1=B(Z=W=e^{i\omega_0})$,where $\omega_0$ is some base frequency. The third row evaluates the Fourier transform for $2\omega_0$,and the bottom row for $3\omega_0$.The matrix could have more than four rows for more frequencies and more columns for more time points. I have made the matrix square in order to show you next how we can find the inverse matrix. The size of the matrix in (3) is N=4. If we choose the base frequency $\omega_0$ and hence W correctly, the inverse matrix will be  

$$\left[ \begin{array} {c} b_0 \ b_1 \ b_2 \ b_3 \end{a... ...gin{array} {c} B_0 \ B_1 \ B_2 \ B_3 \end{array} \right]$$ (4)

Multiplying the matrix of (4) with that of (3), we first see that the diagonals are +1 as desired. To have the off diagonals vanish, we need various sums, such as 1+W +W²+W³ and 1+W²+W⁴+W⁶, to vanish. Every element (W⁶, for example, or 1/W⁹) is a unit vector in the complex plane. In order for the sums of the unit vectors to vanish, we must ensure that the vectors pull symmetrically away from the origin. A uniform distribution of directions meets this requirement. In other words, W should be the N-th root of unity, i.e.,  

$$W \eq \sqrt[N]{1} \eq e^{2\pi i/N}$$ (5)

The lowest frequency is zero, corresponding to the top row of (3). The next-to-the-lowest frequency we find by setting W in (5) to $Z=e^{i\omega_0}$.So $\omega_0=2\pi /N$; and for (4) to be inverse to (3), the frequencies required are  

$$\omega_k \eq { (0, 1, 2, \ldots , N- 1) \, 2\pi \over N}$$ (6)