Circulant matrix

This article is about the matrix class. For graphs whose adjacency matrices are circulant, see Circulant graph.

In linear algebra, a circulant matrix is a square matrix in which each row is a cyclic shift, by one position, of the row above it. Equivalently, its entries depend only on the difference of the row and column indices modulo the matrix size: if rows and columns are indexed from $0$ to $n-1$, the $(r,s)$ entry equals $c_{(r-s){\bmod {n}}}$, where $(c_{0},c_{1},\ldots ,c_{n-1})$ is a single generating vector. Circulant matrices are a special class of Toeplitz matrices.

Every complex circulant matrix is diagonalized by the discrete Fourier transform (DFT). As a consequence, circulant matrices form a commutative algebra of normal matrices; the eigenvalues of a circulant matrix are the DFT of its generating vector; and matrix–vector products and nonsingular linear systems involving a circulant matrix can be computed with a fast Fourier transform (FFT) in $O(n\log n)$ arithmetic operations. Algebraically, multiplication by a circulant matrix is circular convolution on the cyclic group $\mathbb {Z} /n\mathbb {Z}$.

Circulant matrices arise wherever a linear operation is invariant under cyclic shifts. They can be interpreted analytically as the integral kernel of a convolution operator on the cyclic group $C_{n}$, and hence appear in signal and image processing with periodic boundary conditions, in discretizations of translation-invariant problems on periodic domains, and in the study of stationary stochastic processes. In orthogonal frequency-division multiplexing, the cyclic prefix prepended to each transmitted block makes the effective channel matrix circulant, so that channel equalization can be carried out separately on each component in the frequency domain.

In cryptography, a circulant matrix is used in the MixColumns step of the Advanced Encryption Standard.