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
:

![$\displaystyle \underbrace{
\left[\begin{array}{c}
X(\omega_0) \\
X(\omega_1) ...
...
x(2) \\
\vdots \\
x(N-1)
\end{array}\right]
}_{\displaystyle\underline{x}}
$](http://www.dsprelated.com/josimages_new/mdft/img1089.png)
![$\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]
$](http://www.dsprelated.com/josimages_new/mdft/img1090.png)

![$ \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)
![\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*}](http://www.dsprelated.com/josimages_new/mdft/img1093.png)
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
is the inner
product of the
th DFT sinusoid with
, or
, 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
Since the forward DFT is



This equation succinctly states that the columns of




![\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*}](http://www.dsprelated.com/josimages_new/mdft/img1105.png)
The normalized DFT matrix is given by





When a real matrix
satisfies
, then
is said to be
orthogonal.
``Unitary'' is the generalization of ``orthogonal'' to
complex matrices.
Next Section:
DFT Problems
Previous Section:
The Length 2 DFT