Discrete Fourier Transform (general) - Matrix Formulation

Matrix Formulation

Since the discrete Fourier transform is a linear operator, it can be described by matrix multiplication. In matrix notation, the discrete Fourier transform is expressed as follows:


\begin{bmatrix}f_0\\f_1\\\vdots\\f_{n-1}\end{bmatrix}
= \begin{bmatrix}
1&1&1&\cdots &1 \\
1&\alpha&\alpha^2&\cdots&\alpha^{n-1} \\
1&\alpha^2&\alpha^4&\cdots&\alpha^{2(n-1)}\\
\vdots&\vdots&\vdots&&\vdots\\
1&\alpha^{n-1}&\alpha^{2(n-1)}&\cdots&\alpha^{(n-1)(n-1)}\\
\end{bmatrix}
\begin{bmatrix}v_0\\v_1\\\vdots\\v_{n-1}\end{bmatrix}.

The matrix for this transformation is called the DFT matrix.

Similarly, the matrix notation for the inverse Fourier transform is


\begin{bmatrix}v_0\\v_1\\\vdots\\v_{n-1}\end{bmatrix}
= \frac{1}{n}\begin{bmatrix}
1&1&1&\cdots &1 \\
1&\alpha^{-1}&\alpha^{-2}&\cdots&\alpha^{-(n-1)} \\
1&\alpha^{-2}&\alpha^{-4}&\cdots&\alpha^{-2(n-1)}\\
\vdots&\vdots&\vdots&&\vdots\\
1&\alpha^{-(n-1)}&\alpha^{-2(n-1)}&\cdots&\alpha^{-(n-1)(n-1)}
\end{bmatrix}
\begin{bmatrix}f_0\\f_1\\\vdots\\f_{n-1}\end{bmatrix}.

Read more about this topic:  Discrete Fourier Transform (general)

Famous quotes containing the words matrix and/or formulation:

    As all historians know, the past is a great darkness, and filled with echoes. Voices may reach us from it; but what they say to us is imbued with the obscurity of the matrix out of which they come; and try as we may, we cannot always decipher them precisely in the clearer light of our day.
    Margaret Atwood (b. 1939)

    Art is an experience, not the formulation of a problem.
    Lindsay Anderson (b. 1923)