Circulant matrix

In linear algebra, a circulant matrix is a special kind of Toeplitz matrix where each row vector is rotated one element to the right relative to the preceding row vector. In numerical analysis, circulant matrices are important because they are diagonalized by a discrete Fourier transform, and hence linear equations that contain them may be quickly solved using a fast Fourier transform. They can be interpreted analytically as the integral kernel of a convolution operator on the cyclic group and hence frequently appear in formal descriptions of spatially invariant linear operations. In cryptography, a circulant matrix is used in the MixColumns step of the Advanced Encryption Standard.