circulant matrix

A circulant matrix is one multiplication denotes circular convolution.

The matrix is defined exactly by a sequence \(c\) as

\begin{bmatrix} c_0 & c_{n-1} & \cdots & c_2 & c_1 \\ c_1 & c_0 & c_{n-1} & & c_2 \\ \vdots & c_1 & c_0 & \ddots & \vdots \\ c_{n-2} & & \ddots & \ddots & c_{n-1} \\ c_{n-1} & c_{n-2} & \cdots & c_1 & c_0 \\ \end{bmatrix}

Essentially, we fix the first element, and flip the rest for the first row. Every next row shifts to the right, wrapping around to the beginning if it goes off the end.

All circulant matrices are toeplitz.

A circulant matrix is full rank (so invertible) iff the discrete fourier transform has no 0s.

The eigenvectors of any circulant matrix are the columns of the fourier matrix with size equal to the size of the defining sequence. This is an important property for linear time invariant system, and the proof is included in that article.

As an extremely fundamental and famous result of the convolution theorem, any circulant matrix is diagonalizable in the fourier basis. That is,

\begin{equation} FDF^H = C \end{equation}

If \(C\) is circulant. This is tightly related to the idea that the eigenvectors of the matrix are the columns (or rows, because of symmetry) of the fourier matrix.