Circulant matrix: Definition & Examples

A circulant matrix is a square matrix whose rows are successive cyclic shifts of its first row. The last entry wraps back to the first position. This structure turns a periodic linear filter into independent frequency calculations, giving quants a route to fast filtering and structured linear solves. The periodic boundary is part of the model: it must make sense for the data.

Here we shift each row one place to the right. For first row

(c_0,\ldots,c_{n-1})

and zero-based indices,

C_{ij}=c_{(j-i)\bmod n},\qquad i,j=0,\ldots,n-1.

A circulant is a special Toeplitz matrix: its diagonals are constant, with an additional cyclic constraint at the edges. Gray's review, Chapter 3, uses this first-row convention.

The wrap entry changes the calculation

Consider a deliberately simple, dimensionless cyclic filter:

C=\begin{pmatrix} 2&1&0\\ 0&2&1\\ 1&0&2 \end{pmatrix},\qquad \mathbf{x}=\begin{pmatrix}1\\2\\4\end{pmatrix},\qquad C\mathbf{x}=\begin{pmatrix}4\\8\\9\end{pmatrix}.

The rule is $y_i=2x_i+x_{(i+1)\bmod 3}$ . The last output is $2\times4+1=9$ : the filter comes back to the start. Replacing the lower-left entry by zero produces an upper-triangular Toeplitz filter with last output $8$ . That single corner entry encodes a different boundary assumption.

For chronological market observations, this particular rule already uses the next observation in its interior. It is an offline toy, not an implementable trading signal. Wrapping the last observation to the first also joins the endpoints of the sample; a causal filter over finite history needs its own time direction and boundary treatment.

A dimensionless cyclic filter with rows 2, 1, 0; 0, 2, 1; and 1, 0, 2 maps input (1, 2, 4) to (4, 8, 9). Removing its lower-left wrap entry changes the last output to 8. Its eigenvalues are 3 and 1.5 plus or minus 0.866i.

Original toy filter. The blue corner entry creates the wrap. The complex-plane plot uses equal scales and rounds the imaginary parts to three decimals.

Why Fourier modes work

Set

\omega=e^{-2\pi i/n}

, where

i^2=-1

. For

k=0,\ldots,n-1

, define the unit-length eigenvector and its eigenvalue by

v^{(k)}_j=\frac{\omega^{kj}}{\sqrt n},\qquad \lambda_k=\sum_{r=0}^{n-1}c_r\omega^{kr}.

To see the mechanism, substitute $j=i+r$ modulo $n$ into the matrix product. Periodicity gives

(C\mathbf{v}^{(k)})_i =\frac{\omega^{ki}}{\sqrt n}\sum_{r=0}^{n-1}c_r\omega^{kr} =\lambda_kv^{(k)}_i.

Thus the eigenvalues are the negative-exponent discrete Fourier transform of the first row. With

U

containing these vectors as columns,

C=U\operatorname{diag}(\lambda_0,\ldots,\lambda_{n-1})U^*,

where

U^*

is the conjugate transpose. All circulants of the same size share this basis. A system

C\mathbf{x}=\mathbf{b}

can therefore be solved in that basis by dividing each coordinate by its eigenvalue, provided every eigenvalue is nonzero. Small eigenvalue magnitudes can amplify input error during division. These statements follow from Gray's Fourier diagonalisation and Theorem 3.1.

For our matrix, $\lambda_k=2+\omega^k$ , so the ordered values are

\lambda_0=3,\qquad \lambda_1=\frac32-\frac{\sqrt3}{2}i,\qquad \lambda_2=\frac32+\frac{\sqrt3}{2}i.

The constant input $(1,1,1)^\mathsf{T}$ is multiplied by $3$ , the row sum. The other modes form a complex conjugate pair. Real inputs still give real outputs because $C$ itself has real entries.

Fast arithmetic needs the right convention

A fast Fourier transform computes the transforms in

O(n\log n)

operations, rather than a general dense matrix product's

O(n^2)

. A circulant only needs

n

stored coefficients. Multiplication is cyclic convolution, as explained in Strang's MIT lecture on circulants.

Check whether a formula or software routine takes a first row or first column: SciPy's circulant constructor takes a first column. For the conventional convolution rule

y_i=\sum_j a_jx_{(i-j)\bmod n}

, use the first column

a_j=c_{(-j)\bmod n}

. In this example that column is

(2,0,1)^\mathsf{T}

. Confusing it with

(2,1,0)

reverses the filter's direction. NumPy documents its negative-exponent DFT convention. Changing the exponent sign consistently reorders the modes; changing only one convention breaks the calculation.

Finally, circulant does not mean covariance. Our

C

is not symmetric and cannot be a real covariance matrix. For a real circulant covariance candidate, require symmetry,

c_r=c_{n-r}

for

r=1,\ldots,n-1

, and nonnegative eigenvalues: the positive semidefinite requirement. Fast diagonalisation does not validate a covariance model or justify joining a time series' endpoints.

For a finance application of the same transform machinery, Fourier Transform Pricing develops the DFT and FFT before option-pricing transforms. The full lesson requires membership; a public preview is available.

Sources

Robert M. Gray, Toeplitz and Circulant Matrices: A Review, Chapter 3, §§3.1–3.2: first-row definition, Fourier eigenvectors, diagonalisation and inversion.
Gilbert Strang, MIT OpenCourseWare, Lecture 31: Eigenvectors of Circulant Matrices: Fourier Matrix (2018): cyclic convolution and the shared Fourier basis.
SciPy documentation: scipy.linalg.circulant: first-column input convention.
NumPy documentation: Discrete Fourier Transform: exponent signs and inverse-transform normalisation.

The wrap entry changes the calculation

Why Fourier modes work

Fast arithmetic needs the right convention

Sources

Related terms

Eigenvalue

Eigenvector

Matrix

Positive semidefinite matrix