Circulant Matrices

Circulant Matrices: Shifted Rows and Fourier Eigenvectors

A circulant matrix is a special type of matrix where each row is a right cyclic shift of the row above it. It is completely defined by its first row. Every 3×3 circulant matrix shares the same set of complex eigenvectors, which form the discrete Fourier basis.

Worked example: Multiplying a vector

Let the first row of a circulant matrix C be c = [1, 2, 3]. The subsequent rows are formed by cyclically shifting the elements to the right. Let the input vector be x = [1, 0, -1]^T.

Constructing the matrix and computing Cv
Row index	Row entries (shifted right)	Dot product with x
0	[1, 2, 3]	1(1) + 2(0) + 3(-1) = -2
1	[3, 1, 2]	3(1) + 1(0) + 2(-1) = 1
2	[2, 3, 1]	2(1) + 3(0) + 1(-1) = 1

The resulting vector is Cv = [-2, 1, 1]^T.

For c = [0,1,0], the matrix cyclically shifts the coordinates: [1,2,3] → [2,3,1] → [3,1,2] → [1,2,3]. Thus C³ = I. To reproduce each complete application, enter its input vector and use Finish; one Step alone reveals only one output row.

The eigenvalues corresponding to the Fourier modes k = 0, 1, 2 are computed using the formula λ_k = c₀ + c₁ω^k + c₂ω^2k, where ω = exp(2πi/3) = -1/2 + i√3/2.

For mode 0 (k=0): λ₀ = 1 + 2(1) + 3(1) = 6.
For mode 1 (k=1): λ₁ = 1 + 2ω + 3ω² = 1 + 2(-0.5 + i√3/2) + 3(-0.5 - i√3/2) = 1 - 1 - 1.5 + i√3 - i1.5√3 = -1.5 - i√3/2 ≈ -1.5 - 0.866i.
For mode 2 (k=2): λ₂ = 1 + 2ω² + 3ω = 1 + 2(-0.5 - i√3/2) + 3(-0.5 + i√3/2) = 1 - 1 - 1.5 - i√3 + i1.5√3 = -1.5 + i√3/2 ≈ -1.5 + 0.866i.

Observe eigenvalues in the complex plane

Open Circulant Matrices. The module computes the matrix-vector product step-by-step and plots the selected eigenvalue.

Set the first row: c0 = 0, c1 = 1, c2 = 0. Set the input vector: x1 = 1, x2 = 2, x3 = 3.
Click Step three times. The resulting vector is [2, 3, 1]^T, which is a cyclic permutation of the input.
Observe the complex plane. With "Fourier mode" set to 0, the eigenvalue is exactly 1 + 0i.
Change "Fourier mode" to 1. The eigenvalue is now -0.5 + 0.866i, which corresponds to ω.
Change "Fourier mode" to 2. The eigenvalue becomes -0.5 - 0.866i, which is ω².
Click Reset, then change c to [2, 0, 0] and x to [1, -1, 2]. Click Finish. The output is [2, -2, 4]^T, and all eigenvalues are exactly 2 for all modes, because C = 2I.

Model limitations

This module visualizes only 3×3 circulant matrices. Larger matrices follow the same principles but require more dimensions for their input vectors and have more Fourier modes. Eigenvalues are displayed to three decimals; the complex residual is evaluated from unrounded components and displayed in scientific notation. The plot auto-fits the selected eigenvalue; compare numeric coordinates across settings. Step reveals one row dot product; only three revealed rows form the complete product. Input edits, including Fourier mode, rewind that trace, while Reset preserves inputs. Complex vectors cannot be entered into the UI, so we calculate the dot products using real values, while the eigenvalues are shown in their full complex form.

References and Further Reading

The continuous cyclic structure and the Fourier matrix decomposition are deeply connected. The diagonalization of a circulant matrix always uses the same Fourier matrix regardless of the specific row entries.

Nicholas J. Higham. What Is a Circulant Matrix? (2022). This article details the structure of circulant matrices, their connection to cyclic convolutions, and their diagonalization by the discrete Fourier transform matrix.