Circulant matrix

In linear algebra, a circulant matrix is a Toeplitz matrix in which each row is cyclicly right-shifted from its predecessor. Thus, a $m\times n$ circulant matrix is of form

C={\begin{bmatrix}c_{0}&c_{1}&c_{2}&\dots &c_{n-1}\\c_{n-1}&c_{0}&c_{1}&&c_{n-2}\\c_{n-2}&c_{n-1}&c_{0}&&c_{n-3}\\\vdots &&&\ddots &\vdots \\c_{1}&c_{2}&c_{3}&\dots &c_{0}\end{bmatrix}}

Circulant matrices are usually square matrices.

Properties

Circulant matrices is an algebra, since for any two given circulant matrices A and B, the sum A+B and product AB are also circulant.

The eigenvectors of a (square) circulant matrix of given size is fixed, that is, the eigenmatrix of a circulant matrix is the Fourier transform matrix of the same size. Consequently, the eigenvalues of a circulant matrix can be readily calculated by the Fast Fourier transform.