An circulant matrix is defined by parameters, the elements in the first row, and each subsequent row is a cyclic shift forward of the one above:
Circulant matrices have the important property that they are diagonalized by the discrete Fourier transform matrix
which satisfies , so that is a unitary matrix. ( is a Vandermonde matrix with points the roots of unity.) Specifically,
Hence circulant matrices are normal (). Moreover, the eigenvalues are given by , where is the first unit vector.
Note that one particular eigenpair is immediate, since , where is the vector of ones.
The factorization (1) enables a circulant linear system to be solved in flops, since multiplication by can be done using the fast Fourier transform.
A particular circulant matrix is the (up) shift matrix , the version of which is
It is not hard to see that
Since powers of commute, it follows that any two circulant matrices commute (this is also clear from (1)). Furthermore, the sum and product of two circulant matrices is a circulant matrix and the inverse of a nonsingular circulant matrix is a circulant matrix.
One important use of circulant matrices is to act as preconditioners for Toeplitz linear systems. Several methods have been proposed for constructing a circulant matrix from a Toeplitz matrix, including copying the central diagonals and wrapping them around and finding the nearest circulant matrix to the Toeplitz matrix. See Chan and Ng (1996) or Chan and Jin (2017) for a summary of work on circulant preconditioners for Toeplitz systems.
An interesting circulant matrix is
anymatrix('core/circul_binom',n) in the Anymatrix collection, which is the circulant matrix whose first row has th element . The eigenvalues are , , where . The matrix is singular when is a multiple of 6, in which case the null space has dimension 2. Example:
>> n = 6; C = anymatrix('core/circul_binom',n), svd(C) C = 1 6 15 20 15 6 6 1 6 15 20 15 15 6 1 6 15 20 20 15 6 1 6 15 15 20 15 6 1 6 6 15 20 15 6 1 ans = 6.3000e+01 2.8000e+01 2.8000e+01 1.0000e+00 2.0244e-15 7.6607e-16
A classic reference on circulant matrices is Davis (1994).
- Raymond Chan and Michael Ng, Conjugate Gradient Methods for Toeplitz Systems, SIAM Rev. 38(3), 427–482, 1996.
- Raymond Chan and Xiao-Qing Jin, An Introduction to Iterative Toeplitz Solvers, Society for Industrial and Applied Mathematics, Philadelphia, PA, USA, 2007.
- Philip Davis, Circulant Matrices, Second edition, Chelsea, New York, 1994.
- Nicholas J. Higham and Mantas Mikaitis, Anymatrix: An Extendable MATLAB Matrix Collection, Numer. Algorithms, 90:3, 1175-1196, 2021.
This article is part of the “What Is” series, available from https://nhigham.com/category/what-is and in PDF form from the GitHub repository https://github.com/higham/what-is.