## Cyclic Convolution Matrix

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)
[84]^{F.3}). However, the FFT computes
*cyclic convolution* unless sufficient zero padding is used
[84]. The matrix representation of cyclic (or ``circular'')
convolution is a *circulant matrix*, *e.g.*,

^{F.4}For example, the eigenvectors of an circulant matrix are the DFT sinusoids for a length DFT [84]. 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 [84]. 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

*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

**Next Section:**

Inverse Filters

**Previous Section:**

General LTI Filter Matrix