Cirkulanty a DFT: vlastnosti a výpočty

Cirkulantní matice: vlastní hodnoty, DFT a algebraická struktura

Cirkulantní matice jsou čtvercové matice, kde každý řádek po prvním je získán cyklickým posunem předchozího doprava. Pro řád n má cirkulantní matice C(a₀,…,aₙ₋₁) tvar:

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}

Všechny výpočty jsou prováděny nad ℂ. Klíčová označení: χ_A(t) — charakteristický polynom, μ_A(t) — minimální polynom, Sp(A) — spektrum, A* = \overline{A}^⊤ — hermitovské sdružení.

Uvažujme matici cyklické permutace M řádu 4:

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

Její mocniny: M², M³, M⁴ = E. Minimální polynom μ_M(t) = t⁴ - 1, protože {E, M, M², M³} jsou lineárně nezávislé. Spektrum Sp(M) = {±1, ±i}.

Libovolný cirkulant lze vyjádřit jako polynom od M: C(a,b,c,d) = f(M), kde f(t) = a + bt + ct² + dt³.

Algebraické vlastnosti a diagonalizace

Cirkulantní matice tvoří komutativní podalgebru matic M_n(ℂ):

• Součin cirkulantů je cirkulant: f(M)g(M) = h(M), h(t) = f(t)g(t).
• Spektrum: 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).
• Všechny cirkulty jsou diagonalizovatelné ve společném bázi, algebra cirkulantů je izomorfní ℂ⁴.

Vlastní vektory M pro λ ∈ Sp(M) se řeší ze systému:

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

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

M je unitární (M* = M⁻¹), proto je diagonalizovatelná v ortonormální bázi. Normalizovaná matice U (1/2 F, kde F je matice DFT) dává:

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}

Souvislost s diskrétní Fourierovou transformací

Matice F převádí první řádek cirkulantní matice (a,b,c,d) na vektor vlastních hodnot:

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}

Zobecnění na řád n: Sp(M) = {1, ω, …, ω^{n-1}}, ω = e^{2πi/n}. DFT F počítá f(ω^k) pro polynom f(t) = Σ a_k t^k.

FFT snižuje složitost z O(n²) na O(n log n). Pro 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₁.

Aplikace FFT:

• Násobení cirkulantní matice vektorem: F⁻¹(FA · FB).
• Násobení cirkulantů: první řádek výsledku — F⁻¹(FA · FB)^⊤.

Unitární matice DFT U = F/√n má spektrum na jednotkové kružnici. U² — matice odrazů s vlastními hodnotami {1 (⌈(n+1)/2⌉ krát), -1 (⌊(n-1)/2⌋ krát)}.

Gaussovy sumy a spektrum U

Stopa matice U obsahuje kvadratickou Gaussovu sumu:

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

Gaussův vzorec:

| n mod 4 | tr U |

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

| 0 | 1+i |

| 1 | 1 |

| 2 | 0 |

| 3 | i |

Spektrum U je určeno násobností 1, -1, i, -i přes tr U.

Co je důležité:

• Cirkulantní matice jsou polynomy od matice permutace M, diagonalizovatelné v bázi DFT.
• Algebra cirkulantů je izomorfní ℂ[t]/(tⁿ-1), komutativní.
• DFT efektivně počítá spektrum cirkulantní matice, FFT zrychluje operace.
• Spektrum unitární DFT-matice U souvisí s Gaussovými sumami.
• Aplikace: rychlé konvoluce, násobení polynomů modulo tⁿ-1.

— Editorial Team