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)

    “In necessary things, unity; in disputed things, liberty; in all things, charity.”
    —Variously Ascribed.

    The formulation was used as a motto by the English Nonconformist clergyman Richard Baxter (1615-1691)