Matrix Formulation of the DFT

The DFT can be formulated as a complex matrix multiply, as we show in this section. (This section can be omitted without affecting what follows.) For basic definitions regarding matrices, see Appendix H.

The DFT consists of inner products of the input signal $\underline{x}$ with sampled complex sinusoidal sections $\sv_k$ :

$\displaystyle X(\omega_k) \isdef \left<\underline{x},\sv_k\right> \isdef \sum_{n=0}^{N-1}\underline{x}(n) e^{-j 2\pi n k/N}, \quad k=0,1,2,\ldots,N-1$

By collecting the DFT output samples into a column vector, we have

$\displaystyle \underbrace{ \left[\begin{array}{c} X(\omega_0) \\ X(\omega_1) ... ... x(2) \\ \vdots \\ x(N-1) \end{array}\right] }_{\displaystyle\underline{x}}$

$\displaystyle \underline{X}= \mathbf{S}^\ast_N \underline{x} = \left[\begin{arr... ...\ [2pt] \vdots \\ [2pt] \left<\underline{x},\sv_{N-1}\right>\end{array}\right]$

where $\mathbf{S}^\ast_N$ denotes the DFT matrix $\mathbf{S}^\ast_N[k,n]\isdef W_N^{-kn} \isdef e^{-j2\pi k n/N}$ , i.e.,

$\begin{eqnarray*} \mathbf{S}^\ast_N &\!\!\isdef \!\!& \left[\begin{array}{cccc}... ...-1)/N} & \cdots & e^{-j 2\pi (N-1)(N-1)/N} \end{array}\!\right]. \end{eqnarray*}$

The notation $A^\ast\isdef \overline{A^{\hbox{\tiny T}}}$ denotes the Hermitian transpose of the complex matrix (transposition and complex conjugation).

Note that the th column of $\mathbf{S}_N$ is the th DFT sinusoid, so that the th row of the DFT matrix $\mathbf{S}^\ast_N$ is the complex-conjugate of the th DFT sinusoid. Therefore, multiplying the DFT matrix times a signal vector $\underline{x}$ produces a column-vector $\underline{X}=\mathbf{S}^\ast_N\underline{x}$ in which the th element $\underline{X}[k]$ is the inner product of the th DFT sinusoid with $\underline{x}$ , or $\underline{X}[k]=\underline{s}^\ast_k\underline{x} = \left<\underline{x},s_k\right>$ , as expected.

Computation of the DFT matrix in Matlab is illustrated in §I.4.3.

The inverse DFT matrix is simply $\mathbf{S}_N/N$ . That is, we can perform the inverse DFT operation as

$\displaystyle \underline{x}= \frac{1}{N} \mathbf{S}_N \underline{X}. \protect$

(6.1)

Since the forward DFT is $\underline{X}=\mathbf{S}^\ast_N\underline{x}$ , substituting $\underline{x}$ from Eq. $\,$ (6.1) into the forward DFT leads quickly to the conclusion that

$\displaystyle \mathbf{S}^\ast_N \mathbf{S}_N = N\cdot \mathbf{I}. \protect$

(6.2)

This equation succinctly states that the columns of $\mathbf{S}_N$ are orthogonal, which, of course, we already knew. I.e., $\left<\sv_k,\sv_n\right>=0$ for $k\ne n$ , and $\left<\sv_k,\sv_k\right>=N$ :

$\begin{eqnarray*} \mathbf{S}^\ast_N \mathbf{S}_N &\!\!=\!\!& \left[\!\begin{arr... ...0 & 0 & 0 & \cdots & N \end{array}\!\right] = N\cdot \mathbf{I}. \end{eqnarray*}$

The normalized DFT matrix is given by

$\displaystyle \tilde{\mathbf{S}}^\ast_{N} \isdef \frac{1}{\sqrt{N}} \mathbf{S}^\ast_{N}$

and the corresponding normalized inverse DFT matrix is simply $\tilde{\mathbf{S}}_N$ , so that Eq. $\,$ (6.2) becomes

$\displaystyle \tilde{\mathbf{S}}^\ast_N \tilde{\mathbf{S}}_N = \mathbf{I}.$

This implies that the columns of $\tilde{\mathbf{S}}_N$ are orthonormal. Such a complex matrix is said to be unitary.

When a real matrix $\mathbf{Q}$ satisfies $\mathbf{Q}^{\!\hbox{\tiny T}}\mathbf{Q}= \mathbf{I}$ , then $\mathbf{Q}$ is said to be orthogonal. ``Unitary'' is the generalization of ``orthogonal'' to complex matrices.

Order a Hardcopy of Mathematics of the DFT

Previous: The Length 2 DFT
Next: DFT Problems

written by Julius Orion Smith III
Julius Smith's background is in electrical engineering (BS Rice 1975, PhD Stanford 1983). He is presently Professor of Music and Associate Professor (by courtesy) of Electrical Engineering at Stanford's Center for Computer Research in Music and Acoustics (CCRMA), teaching courses and pursuing research related to signal processing applied to music and audio systems. See http://ccrma.stanford.edu/~jos/ for details.

Sign in

Search Online Books

Free Online Books

Sponsor

Chapters

See Also

Mathematics of the DFT
Derivation of the Discrete Fourier Transform (DFT)
Matrix Formulation of the DFT