An infinite Toeplitz matrix implements, in principle, acyclic convolution (which is what we normally mean when we just say ``convolution''). In practice, the convolution of a signal and an impulse response , in which both and are more than a hundred or so samples long, is typically implemented fastest using FFT convolution (i.e., performing fast convolution using the Fast Fourier Transform (FFT) F.3). However, the FFT computes cyclic convolution unless sufficient zero padding is used . The matrix representation of cyclic (or ``circular'') convolution is a circulant matrix, e.g.,
As in this example, each row of a circulant matrix is obtained from the previous row by a circular right-shift. Circulant matrices are thus always Toeplitz (but not vice versa). Circulant matrices have many interesting properties.F.4 For example, the eigenvectors of an circulant matrix are the DFT sinusoids for a length DFT . Similarly, the eigenvalues may be found by simply taking the DFT of the first row.
The DFT eigenstructure of circulant matrices is directly related to the DFT convolution theorem . The above circulant matrix , when multiplied times a length 6 vector , implements cyclic convolution of with . Using the DFT to perform the circular convolution can be expressed as
where ` ' denotes circular convolution. Let denote the matrix of sampled DFT sinusoids for a length DFT: . Then is the DFT matrix, where ` ' denotes Hermitian transposition (transposition and complex-conjugation). The DFT of the length- vector can be written as , and the corresponding inverse DFT is . The DFT-eigenstructure of circulant matrices provides that a real circulant matrix having top row satisfies diag , where is the length DFT of , and diag denotes a diagonal matrix with the elements of along the diagonal. Therefore, diag . By the DFT convolution theorem,
Premultiplying by the IDFT matrix yields
Thus, the DFT convolution theorem holds if and only if the circulant convolution matrix has eigenvalues and eigenvectors given by the columns of (the DFT sinusoids).