Circulants and DFT: properties and computations

Circulants: Eigenvalues, DFT, and Algebraic Structure

Circulants are square matrices where each row after the first is a right cyclic shift of the previous one. For order n, the circulant C(a₀,…,aₙ₋₁) looks like this:

C(a_0,\ldots,a_{n-1})=\begin{pmatrix} a_0 & a_1 & a_2 & \ldots & a_{n-2} & a_{n-1} \\  a_{n-1} & a_0 & a_1 & \ldots & a_{n-3} & a_{n-2} \\ a_{n-2} & a_{n-1} & a_0 & \ldots & a_{n-4} & a_{n-3} \\ \ldots & \ldots & \ldots & \ldots & \ldots & \ldots \\ a_2 & a_3 & a_4 & \ldots & a_0 & a_1 \\ a_1 & a_2 & a_3 & \ldots & a_{n-1} & a_0 \end{pmatrix}

All computations are over ℂ. Key notation: χ_A(t) — characteristic polynomial, μ_A(t) — minimal polynomial, Sp(A) — spectrum, A* = \overline{A}^⊤ — Hermitian adjoint.

Consider the cyclic permutation matrix M of order 4:

M=\begin{pmatrix} 0 & 1 & 0 & 0 \\ 0 & 0 & 1 & 0 \\ 0 & 0 & 0 & 1 \\ 1 & 0 & 0 & 0 \end{pmatrix}

Its powers: M², M³, M⁴ = I. Minimal polynomial μ_M(t) = t⁴ - 1, since {I, M, M², M³} are linearly independent. Spectrum Sp(M) = {±1, ±i}.

Any circulant is a polynomial in M: C(a,b,c,d) = f(M), where f(t) = a + bt + ct² + dt³.

Algebraic Properties and Diagonalization

Circulants form a commutative subalgebra of M_n(ℂ):

• Product of circulants is a circulant: f(M)g(M) = h(M), h(t) = f(t)g(t).
• Spectrum: Sp(C) = {f(λ) | λ ∈ Sp(M)}.
• Determinant: det C(a,b,c,d) = (a+b+c+d)(a-b+c-d)(a+bi-c-di)(a-bi-c+di).
• All circulants are diagonalizable in a common basis; the circulant algebra is isomorphic to ℂ⁴.

Eigenvectors of M for λ ∈ Sp(M) solve:

\begin{pmatrix} p\\q\\r\\s \end{pmatrix} \overset{M}{\longmapsto} \begin{pmatrix} q\\r\\s\\p \end{pmatrix}=\lambda\begin{pmatrix} p\\q\\r\\s \end{pmatrix}

For λ=1: p=q=r=s. For λ=i: q=ip, r=iq=-p, s=ir=-ip.

M is unitary (M* = M⁻¹), so diagonalizable in an orthonormal basis. The normalized matrix U (1/2 F, where F is the DFT matrix) gives:

U^{-1}MU = \begin{pmatrix} 1 & 0 & 0 & 0 \\ 0 & i & 0 & 0 \\ 0 & 0 & -1 & 0 \\ 0 & 0 & 0 & -i \end{pmatrix}, \quad U=\dfrac{1}{2} \begin{pmatrix} 1 & 1 & 1 & 1 \\  1 & i & -1 & -i \\ 1 & -1 & 1 & -1 \\ 1 & -i & -1 & i\end{pmatrix}

Connection to the Discrete Fourier Transform

The matrix F transforms the first row of the circulant (a,b,c,d) into the eigenvalue vector:

F\begin{pmatrix} a \\ b\\c\\d\end{pmatrix}=\begin{pmatrix} a+b+c+d\\a+bi-c-di\\a-b+c-d\\a-bi-c+di\end{pmatrix}

Generalizing to order n: Sp(M) = {1, ω, …, ω^{n-1}}, ω = e^{2πi/n}. DFT F computes f(ω^k) for polynomial f(t) = Σ a_k t^k.

FFT reduces complexity from O(n²) to O(n log n). For n=4:

• E₀ = a+c, E₁ = a-c, O₀ = b+d, O₁ = b-d.
• f(1) = E₀ + O₀, f(i) = E₁ + iO₁, f(-1) = E₀ - O₀, f(-i) = E₁ - iO₁.

FFT applications:

• Circulant-vector multiplication: F⁻¹(FA · FB).
• Circulant-circulant multiplication: first row of result is F⁻¹(FA · FB)^⊤.

The unitary DFT matrix U = F/√n has spectrum on the unit circle. U² is a reflection matrix with eigenvalues {1 (⌈(n+1)/2⌉ times), -1 (⌊(n-1)/2⌋ times)}.

Gaussian Sums and the Spectrum of U

The trace of U involves the quadratic Gaussian sum:

tr U = (1 + ω + ω⁴ + … + ω^{(n-1)²}) / √n.

Gauss's formula:

| n mod 4 | tr U |

|---------|------|

| 0 | 1+i |

| 1 | 1 |

| 2 | 0 |

| 3 | i |

The spectrum of U is determined by multiplicities of 1, -1, i, -i via tr U.

Key Takeaways:

• Circulants are polynomials in the permutation matrix M, diagonalizable in the DFT basis.
• The circulant algebra is isomorphic to ℂ[t]/(tⁿ-1), hence commutative.
• DFT efficiently computes the circulant spectrum; FFT speeds up operations.
• The spectrum of the unitary DFT matrix U ties into Gaussian sums.
• Applications: fast convolutions, polynomial multiplication modulo tⁿ-1.

— Editorial Team