Circulantes y DFT: propiedades y computaciones

# Circulantes: Valores propios, DFT y estructura algebraica

Los circulantes son matrices cuadradas donde cada fila después de la primera es un desplazamiento cíclico a la derecha de la anterior. Para orden n, el circulante C(a₀,…,aₙ₋₁) se ve así:

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}

Todos los cálculos se realizan sobre ℂ. Notación clave: χ_A(t) — polinomio característico, μ_A(t) — polinomio mínimo, Sp(A) — espectro, A* = \overline{A}^⊤ — adjunto hermitiano.

Considera la matriz de permutación cíclica M de orden 4:

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

Sus potencias: M², M³, M⁴ = I. Polinomio mínimo μ_M(t) = t⁴ - 1, ya que {I, M, M², M³} son linealmente independientes. Espectro Sp(M) = {±1, ±i}.

Cualquier circulante es un polinomio en M: C(a,b,c,d) = f(M), donde f(t) = a + bt + ct² + dt³.

Propiedades algebraicas y diagonalización

Los circulantes forman un subálgebra conmutativa de M_n(ℂ):

• El producto de circulantes es un circulante: f(M)g(M) = h(M), h(t) = f(t)g(t).
• Espectro: Sp(C) = {f(λ) | λ ∈ Sp(M)}.
• Determinante: det C(a,b,c,d) = (a+b+c+d)(a-b+c-d)(a+bi-c-di)(a-bi-c+di).
• Todos los circulantes son diagonalizables en una base común; el álgebra circulante es isomorfa a ℂ⁴.

Los vectores propios de M para λ ∈ Sp(M) resuelven:

\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}

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

M es unitaria (M* = M⁻¹), por lo que es diagonalizable en una base ortonormal. La matriz normalizada U (1/2 F, donde F es la matriz DFT) da:

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}

Conexión con la Transformada Discreta de Fourier

La matriz F transforma la primera fila del circulante (a,b,c,d) en el vector de valores propios:

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}

Generalizando a orden n: Sp(M) = {1, ω, …, ω^{n-1}}, ω = e^{2πi/n}. La DFT F calcula f(ω^k) para el polinomio f(t) = Σ a_k t^k.

La FFT reduce la complejidad de O(n²) a O(n log n). Para 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₁.

Aplicaciones de la FFT:

• Multiplicación circulante-vector: F⁻¹(FA · FB).
• Multiplicación circulante-circulante: primera fila del resultado es F⁻¹(FA · FB)^⊤.

La matriz DFT unitaria U = F/√n tiene espectro en el círculo unitario. U² es una matriz de reflexión con valores propios {1 (⌈(n+1)/2⌉ veces), -1 (⌊(n-1)/2⌋ veces)}.

Sumas gaussianas y el espectro de U

La traza de U involucra la suma gaussiana cuadrática:

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

Fórmula de Gauss:

| n mod 4 | tr U |

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

| 0 | 1+i |

| 1 | 1 |

| 2 | 0 |

| 3 | i |

El espectro de U se determina por las multiplicidades de 1, -1, i, -i vía tr U.

Ideas clave:

• Los circulantes son polinomios en la matriz de permutación M, diagonalizables en la base DFT.
• El álgebra circulante es isomorfa a ℂ[t]/(tⁿ-1), por tanto conmutativa.
• La DFT calcula eficientemente el espectro circulante; la FFT acelera las operaciones.
• El espectro de la matriz DFT unitaria U está ligado a sumas gaussianas.
• Aplicaciones: convoluciones rápidas, multiplicación de polinomios módulo tⁿ-1.

— Editorial Team