Circulant matrix

A matrix built from one sequence, where every row is the row above it, shifted and wrapped around.

A circulant matrix $C$ is built from one length- $N$ sequence $c_0,\dots,c_{N-1}$ by setting $C_{jk}=c_{(j-k)\bmod N}$ : every row is the row above it, shifted one slot to the right, with whatever falls off the end wrapping back to the front. Multiplying a vector by a circulant matrix produces exactly a circular convolution, and the DFT basis diagonalizes every circulant matrix of a given size at once.

Examples

The matrix with rows $(4,1,0,1)$ , $(1,4,1,0)$ , $(0,1,4,1)$ , $(1,0,1,4)$ is circulant: each row is the previous one shifted with wraparound.