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

with sampled complex
sinusoidal sections

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

denotes the
DFT matrix
![$ \mathbf{S}^\ast_N[k,n]\isdef W_N^{-kn} \isdef
e^{-j2\pi k n/N}$](http://www.dsprelated.com/josimages_new/mdft/img1092.png)
,
i.e.,
The notation

denotes the
Hermitian transpose of the complex matrix

(transposition
and complex conjugation).
Note that the

th column of

is the

th DFT
sinusoid, so
that the

th row of the DFT matrix

is the
complex-conjugate of the

th
DFT sinusoid. Therefore, multiplying
the DFT matrix times a signal vector

produces a column-vector

in which the

th element
![$ \underline{X}[k]$](http://www.dsprelated.com/josimages_new/mdft/img1097.png)
is the inner
product of the

th DFT
sinusoid with

, or
![$ \underline{X}[k]=\underline{s}^\ast_k\underline{x}
= \left<\underline{x},s_k\right>$](http://www.dsprelated.com/josimages_new/mdft/img1098.png)
, as expected.
Computation of the DFT matrix in
Matlab is illustrated in §
I.4.3.
The
inverse DFT matrix is simply

. That is,
we can perform the inverse DFT operation as
 |
(6.2) |
Since the forward DFT is

,
substituting

from Eq.

(
6.2) into the forward DFT
leads quickly to the conclusion that
 |
(6.3) |
This equation succinctly states that the
columns of
are orthogonal, which, of course, we already knew.
I.e.,

for

, and

:
The
normalized DFT matrix is given by
and the corresponding
normalized
inverse DFT matrix
is simply

, so that Eq.

(
6.3) becomes
This implies that the columns of

are
orthonormal. Such a
complex matrix is said to be
unitary.
When a
real matrix

satisfies

, then

is said to be
orthogonal.
``Unitary'' is the generalization of ``orthogonal'' to
complex matrices.
Next Section: DFT ProblemsPrevious Section: The Length 2 DFT