Signal Processing Stack Exchange is a question and answer site for practitioners of the art and science of signal, image and video processing. It only takes a minute to sign up.
Sign up to join this community
Is there a simple or potentially intuitive explanation for, with the DFT, vector multiplication in one domain being equivalent to circular convolution of the transforms of the vectors in the other domain?
Since a DFT is just multiplication by a (special) square matrix, what about this matrix and matrix multiply allows the above duality?
As you correctly say, the DFT can be represented by a matrix multiplication, namely the Fourier matrix $\mathbf{F}$. On the other hand the DFT "transforms" a cyclic convolution in a multiplication (as all Fourier transform variant as DFT, DTFT, FT have a similar property of transforming convolution to multiplication) and vice versa.
To understand this in the matrix picture, note that also (circular) convolution with a certain sequence can be represented by a matrix multiplication. More specifically this is a circulant matrix, a special kind of a Toeplitz matrix.
so $\mathbf{y} = \mathbf{c} * \mathbf{x}$ with $*$ the cyclic convolution can be written as $\mathbf{y} = \mathbf{C}(\mathbf{c}) \mathbf{x}$ with $\mathbf{C}$ denoting the circulant matrix formed from entries of vector $\mathbf{c}$.
If we "transform" this equation with the DFT (i.e. multiplication by $\mathbf{F}$) we obtain
$\widehat{\mathbf{y}} = \mathbf{F} \, \mathbf{C}(\mathbf{c}) \,\mathbf{F}^H\, \widehat{\mathbf{x}}$
with $\widehat{\mathbf{y}} =\mathbf{F}\mathbf{y}$ and $\widehat{\mathbf{x}} =\mathbf{F}\mathbf{x}$ the respective DFTs (note $\mathbf{F}^H$ represents the IDFT).
The point is now that $\mathbf{F} \mathbf{C}(\mathbf{c}) \,\mathbf{F}^H$ is always a diagonal matrix, because all circulant matrices are diagonalized by the Fourier matrix. This means that the eigenvectors of circulant matrices are just given by the rows of the Fourier matrix.
This is of course consistent with the convolution picture, because the DFT transforms the convolution to an elementwide multiplication. Moreover the diagonal elements of this matrix are just the DFT of $\mathbf{c}$, or, eqivalently, the eigenvalues of the circulant matrix formed from $\mathbf{c}$.
Incidentally, DFT is the only bijective linear transformation that exchanges convolution and termwise multiplication (up to permutation of the coefficients, obviously). This is not difficult to prove, but I have found no reference on this result before I spelled it out in Music Through Fourier Space, Thm. 1.11 (Springer 2016). It is messier in the continuous case because one has to choose well the function spaces involved.
Perhaps this reciprocal could also be proved using circulating matrixes and simultaneous diagonalisation.
