Circulant

Circulant is a term used in mathematics to describe objects with cyclic symmetry, most commonly a circulant matrix or a circulant graph. In linear algebra, a circulant matrix is an n by n matrix where each row is obtained from the previous one by a cyclic (wrap-around) shift. A standard form is determined by its first row [c0, c1, ..., c_{n-1}]; the second row is [c_{n-1}, c0, c1, ..., c_{n-2}], and each subsequent row is a right cyclic shift of the row above it. For example, with first row [a0, a1, a2], the 3×3 circulant matrix is

[a0, a1, a2;

a2, a0, a1;

a1, a2, a0].

Circulant matrices have several notable properties. They form an n-dimensional commutative algebra: any linear combination or product of circulant matrices is circulant. They are diagonalizable by the discrete Fourier transform: if ω = exp(−2π i / n) and v_j has components [1, ω^j, ω^{2j}, ..., ω^{(n−1)j}]^T, then the eigenvalues are λ_j = ∑_{k=0}^{n−1} c_k ω^{jk}. Consequently, the determinant is the product of the eigenvalues, and the inverse exists exactly when none of the eigenvalues is zero. The inverse, when it exists, is itself circulant.

A key application is circular convolution: multiplying a circulant matrix by a vector corresponds to circular convolution of the first column with the vector. The Fourier basis diagonalizes circulant matrices, enabling fast computation via the fast Fourier transform.

Circulant can also describe circulant graphs, whose adjacency matrices are circulant. Such graphs on n vertices are defined by a symmetric generating set and are vertex-transitive; their spectra are given by sums of roots of unity and depend only on n and the chosen jumps. Circulant structures appear in signal processing, numerical analysis, and combinatorics.