DFT matrix
Encyclopedia
A DFT matrix is an expression of a discrete Fourier transform
(DFT) as a matrix
multiplication.
, where 
is the original input signal, and 
is the DFT of the signal.
The transformation
of size 
can be defined as 
, or equivalently:
where
is a primitive 
th root of unity in which 
.
This is the Vandermonde matrix for the roots of unity, up to the normalization factor.
Note that the normalization factor in front of the sum (
) and the sign of the exponent in ω are merely conventions, and differ in some treatments. All of the following discussion applies regardless of the convention, with at most minor adjustments. The only important thing is that the forward and inverse transforms have opposite-sign exponents, and that the product of their normalization factors be 1/N. However, the 
choice here makes the resulting DFT matrix unitary, which is convenient in many circumstances.
Fast Fourier Transform
algorithms utilize the symmetries of the matrix to reduce the time of multiplying a vector by this matrix, from the usual
. Similar techniques can be applied for multiplications by matrices such as Hadamard matrix
and the Walsh matrix
.
The first row performs the sum, and the second row performs the difference.
The factor of
is to make the transform unitary (see below).
where
The following image depicts the DFT as a matrix multiplication, with elements of the matrix depicted by samples of complex exponentials:
The real part (cosine wave) is denoted by a solid line, and the imaginary part (sine wave) by a dashed line.
The top row is all ones (scaled by
for unitarity), so it "measures" the DC component
in the input signal. The next row is eight samples of negative one cycle of a complex exponential, i.e., a signal with a fractional frequency of −1/8, so it "measures" how much "strength" there is at fractional frequency +1/8 in the signal. Recall that a matched filter
compares the signal with a time reversed version of whatever we're looking for, so when we're looking for fracfreq. 1/8 we compare with fracfreq. −1/8 so that is why this row is a negative frequency
. The next row is negative two cycles of a complex exponential, sampled in eight places, so it has a fractional frequency of −1/4, and thus "measures" the extent to which the signal has a fractional frequency of +1/4.
The following summarizes how the 8-point DFT works, row by row, in terms of fractional frequency:
Equivalently the last row can be said to have a fractional frequency of +1/8 and thus measure how much of the signal has a fractional frequency of −1/8. In this way, it could be said that the top rows of the matrix "measure" positive frequency content in the signal and the bottom rows measure negative frequency component in the signal.
, so that the energy in the physical domain will be the same as the energy in the Fourier domain, i.e., to satisfy Parseval's theorem
. (Other, non-unitary, scalings, are also commonly used for computational convenience; e.g., the convolution theorem
takes on a slightly simpler form with the scaling shown in the discrete Fourier transform
article.)
article.
If we make a very large matrix with complex exponentials in the rows (i.e., cosine real parts and sine imaginary parts), and increase the resolution without bound, we approach the kernel of the Fredholm integral equation of the 2nd kind, namely the Fourier operator
that defines the continuous Fourier transform. A rectangular portion of this continuous Fourier operator can be displayed as an image, analogous to the DFT matrix, as shown at right, where greyscale pixel value denotes numerical quantity.
Discrete Fourier transform
In mathematics, the discrete Fourier transform is a specific kind of discrete transform, used in Fourier analysis. It transforms one function into another, which is called the frequency domain representation, or simply the DFT, of the original function...
(DFT) as a matrix
Matrix (mathematics)
In mathematics, a matrix is a rectangular array of numbers, symbols, or expressions. The individual items in a matrix are called its elements or entries. An example of a matrix with six elements isMatrices of the same size can be added or subtracted element by element...
multiplication.
Definition
An N-point DFT is expressed as an N-by-N matrix multiplication as, where is the original input signal, and is the DFT of the signal.The transformation
of size can be defined as , or equivalently:where
is a primitive th root of unity in which .This is the Vandermonde matrix for the roots of unity, up to the normalization factor.
Note that the normalization factor in front of the sum (
) and the sign of the exponent in ω are merely conventions, and differ in some treatments. All of the following discussion applies regardless of the convention, with at most minor adjustments. The only important thing is that the forward and inverse transforms have opposite-sign exponents, and that the product of their normalization factors be 1/N. However, the choice here makes the resulting DFT matrix unitary, which is convenient in many circumstances.Fast Fourier Transform
Fast Fourier transform
A fast Fourier transform is an efficient algorithm to compute the discrete Fourier transform and its inverse. "The FFT has been called the most important numerical algorithm of our lifetime ." There are many distinct FFT algorithms involving a wide range of mathematics, from simple...
algorithms utilize the symmetries of the matrix to reduce the time of multiplying a vector by this matrix, from the usual
. Similar techniques can be applied for multiplications by matrices such as Hadamard matrixHadamard matrix
In mathematics, an Hadamard matrix, named after the French mathematician Jacques Hadamard, is a square matrix whose entries are either +1 or −1 and whose rows are mutually orthogonal...
and the Walsh matrix
Walsh matrix
In mathematics, a Walsh matrix is a specific square matrix, with dimensions a power of 2, the entries of which are +1 or −1, and the property that the dot product of any two distinct rows is zero. The Walsh matrix was proposed by Joseph Leonard Walsh in 1923...
.
Two-point
The two-point DFT is a simple case, in which the first entry is the DC (sum) and the second entry is the AC (difference).The first row performs the sum, and the second row performs the difference.
The factor of
is to make the transform unitary (see below).Four-point
The four-point DFT matrix is as follows:Eight-point
The first non-trivial integer power of two case is for 8 points:where
The following image depicts the DFT as a matrix multiplication, with elements of the matrix depicted by samples of complex exponentials:
The real part (cosine wave) is denoted by a solid line, and the imaginary part (sine wave) by a dashed line.
The top row is all ones (scaled by
for unitarity), so it "measures" the DC componentDC bias
When describing a periodic function in the frequency domain, the DC bias, DC component, DC offset, or DC coefficient is the mean value of the waveform...
in the input signal. The next row is eight samples of negative one cycle of a complex exponential, i.e., a signal with a fractional frequency of −1/8, so it "measures" how much "strength" there is at fractional frequency +1/8 in the signal. Recall that a matched filter
Matched filter
In telecommunications, a matched filter is obtained by correlating a known signal, or template, with an unknown signal to detect the presence of the template in the unknown signal. This is equivalent to convolving the unknown signal with a conjugated time-reversed version of the template...
compares the signal with a time reversed version of whatever we're looking for, so when we're looking for fracfreq. 1/8 we compare with fracfreq. −1/8 so that is why this row is a negative frequency
Negative frequency
The concept of negative and positive frequency can be as simple as a wheel rotating one way or the other way. A signed value of frequency indicates both the rate and direction of rotation...
. The next row is negative two cycles of a complex exponential, sampled in eight places, so it has a fractional frequency of −1/4, and thus "measures" the extent to which the signal has a fractional frequency of +1/4.
The following summarizes how the 8-point DFT works, row by row, in terms of fractional frequency:
- 0 measures how much DC is in the signal
- −1/8 measures how much of the signal has a fractional frequency of +1/8
- −1/4 measures how much of the signal has a fractional frequency of +1/4
- −3/8 measures how much of the signal has a fractional frequency of +3/8
- −1/2 measures how much of the signal has a fractional frequency of +1/2
- −5/8 measures how much of the signal has a fractional frequency of +5/8
- −3/4 measures how much of the signal has a fractional frequency of +3/4
- −7/8 measures how much of the signal has a fractional frequency of +7/8
Equivalently the last row can be said to have a fractional frequency of +1/8 and thus measure how much of the signal has a fractional frequency of −1/8. In this way, it could be said that the top rows of the matrix "measure" positive frequency content in the signal and the bottom rows measure negative frequency component in the signal.
Unitary transform
The DFT is (or can be, through appropriate selection of scaling) a unitary transform, i.e., one that preserves energy. The appropriate choice of scaling to achieve unitarity is, so that the energy in the physical domain will be the same as the energy in the Fourier domain, i.e., to satisfy Parseval's theoremParseval's theorem
In mathematics, Parseval's theorem usually refers to the result that the Fourier transform is unitary; loosely, that the sum of the square of a function is equal to the sum of the square of its transform. It originates from a 1799 theorem about series by Marc-Antoine Parseval, which was later...
. (Other, non-unitary, scalings, are also commonly used for computational convenience; e.g., the convolution theorem
Convolution theorem
In mathematics, the convolution theorem states that under suitableconditions the Fourier transform of a convolution is the pointwise product of Fourier transforms. In other words, convolution in one domain equals point-wise multiplication in the other domain...
takes on a slightly simpler form with the scaling shown in the discrete Fourier transform
Discrete Fourier transform
In mathematics, the discrete Fourier transform is a specific kind of discrete transform, used in Fourier analysis. It transforms one function into another, which is called the frequency domain representation, or simply the DFT, of the original function...
article.)
Other properties
For other properties of the DFT matrix, including its eigenvalues, connection to convolutions, applications, and so on, see the discrete Fourier transformDiscrete Fourier transform
In mathematics, the discrete Fourier transform is a specific kind of discrete transform, used in Fourier analysis. It transforms one function into another, which is called the frequency domain representation, or simply the DFT, of the original function...
article.
In the limit: The Fourier operator
 |
 |
If we make a very large matrix with complex exponentials in the rows (i.e., cosine real parts and sine imaginary parts), and increase the resolution without bound, we approach the kernel of the Fredholm integral equation of the 2nd kind, namely the Fourier operator
Fourier operator
The Fourier operator is the kernel of the Fredholm integral of the first kind that defines the continuous Fourier transform.It may be thought of as a limiting case for when the size of the discrete Fourier transform increases without bound while its spatial resolution also increases without bound,...
that defines the continuous Fourier transform. A rectangular portion of this continuous Fourier operator can be displayed as an image, analogous to the DFT matrix, as shown at right, where greyscale pixel value denotes numerical quantity.