Cyrkulanty i DFT: właściwości i obliczenia

Cyrkulanty: wartości własne, DFT i struktura algebraiczna

Cyrkulanty to kwadratowe macierze, w których każdy wiersz po pierwszym powstaje poprzez cykliczne przesunięcie poprzedniego w prawo. Dla rzędu n cyrkulant C(a₀,…,aₙ₋₁) ma postać:

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}

Wszystkie obliczenia prowadzone są nad ℂ. Kluczowe oznaczenia: χ_A(t) — wielomian charakterystyczny, μ_A(t) — wielomian minimalny, Sp(A) — widmo, A* = \overline{A}^⊤ — sprzężenie hermitowskie.

Rozważmy macierz cyklicznej permutacji M rzędu 4:

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

Jej potęgi: M², M³, M⁴ = E. Wielomian minimalny μ_M(t) = t⁴ - 1, ponieważ {E, M, M², M³} są liniowo niezależne. Widmo Sp(M) = {±1, ±i}.

Każdy cyrkulant można wyrazić jako wielomian od M: C(a,b,c,d) = f(M), gdzie f(t) = a + bt + ct² + dt³.

Właściwości algebraiczne i diagonalizacja

Cyrkulanty tworzą przemienną podalgebrę macierzy M_n(ℂ):

• Iloczyn cyrkulantów to cyrkulant: f(M)g(M) = h(M), h(t) = f(t)g(t).
• Widmo: Sp(C) = {f(λ) | λ ∈ Sp(M)}.
• Wyznacznik: det C(a,b,c,d) = (a+b+c+d)(a-b+c-d)(a+bi-c-di)(a-bi-c+di).
• Wszystkie cyrkulanty są diagonalizowalne we wspólnej bazie, algebra cyrkulantów jest izomorficzna z ℂ⁴.

Wektory własne M dla λ ∈ Sp(M) rozwiązuje się z układu:

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

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

M jest unitarna (M* = M⁻¹), więc diagonalizowalna w bazie ortonormalnej. Znormalizowana macierz U (1/2 F, gdzie F — macierz DFT) daje:

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}

Związek z dyskretną transformatą Fouriera

Macierz F przekształca pierwszy wiersz cyrkulanta (a,b,c,d) w wektor wartości własnych:

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}

Uogólnienie na rząd n: Sp(M) = {1, ω, …, ω^{n-1}}, ω = e^{2πi/n}. DFT F oblicza f(ω^k) dla wielomianu f(t) = Σ a_k t^k.

FFT zmniejsza złożoność z O(n²) do O(n log n). Dla 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₁.

Zastosowanie FFT:

• Mnożenie cyrkulanta przez wektor: F⁻¹(FA · FB).
• Mnożenie cyrkulantów: pierwszy wiersz wyniku — F⁻¹(FA · FB)^⊤.

Unitarna macierz DFT U = F/√n ma widmo na okręgu jednostkowym. U² — macierz odbić z wartościami własnymi {1 (⌈(n+1)/2⌉ razy), -1 (⌊(n-1)/2⌋ razy)}.

Sumy Gaussa i widmo U

Ślad macierzy U zawiera kwadratową sumę Gaussa:

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

Wzór Gaussa:

| n mod 4 | tr U |

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

| 0 | 1+i |

| 1 | 1 |

| 2 | 0 |

| 3 | i |

Widmo U określa krotności 1, -1, i, -i poprzez tr U.

Co ważne:

• Cyrkulanty to wielomiany od macierzy permutacji M, diagonalizowalne w bazie DFT.
• Algebra cyrkulantów jest izomorficzna z ℂ[t]/(tⁿ-1), przemienna.
• DFT efektywnie oblicza widmo cyrkulanta, FFT przyspiesza operacje.
• Widmo unitarnej macierzy DFT U jest związane z sumami Gaussa.
• Zastosowania: szybkie sploty, mnożenie wielomianów modulo tⁿ-1.

— Editorial Team