Zirkulanten und DFT: Eigenschaften und Berechnungen

Zirkulanten: Eigenwerte, DFT und algebraische Struktur

Zirkulanten sind quadratische Matrizen, bei denen jede Zeile nach der ersten eine zyklische Rechtsverschiebung der vorherigen darstellt. Für die Ordnung n sieht der Zirkulant C(a₀,…,aₙ₋₁) so aus:

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}

Alle Berechnungen erfolgen über ℂ. Wichtige Notation: χ_A(t) — charakteristisches Polynom, μ_A(t) — minimales Polynom, Sp(A) — Spektrum, A* = \overline{A}^⊤ — hermitesches Adjungiertes.

Betrachten wir die zyklische Permutationsmatrix M der Ordnung 4:

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

Ihre Potenzen: M², M³, M⁴ = I. Minimales Polynom μ_M(t) = t⁴ - 1, da {I, M, M², M³} linear unabhängig sind. Spektrum Sp(M) = {±1, ±i}.

Jeder Zirkulant ist ein Polynom in M: C(a,b,c,d) = f(M), wobei f(t) = a + bt + ct² + dt³.

Algebraische Eigenschaften und Diagonalisierung

Zirkulanten bilden eine kommutative Unteralgebra von M_n(ℂ):

• Produkt von Zirkulanten ist ein Zirkulant: f(M)g(M) = h(M), h(t) = f(t)g(t).
• Spektrum: 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).
• Alle Zirkulanten sind in einer gemeinsamen Basis diagonalisierbar; die Zirkulantenalgebra ist isomorph zu ℂ⁴.

Eigenvektoren von M für λ ∈ Sp(M) lösen:

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

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

M ist unitär (M* = M⁻¹), daher diagonalisierbar in einer orthonormierten Basis. Die normalisierte Matrix U (1/2 F, wobei F die DFT-Matrix ist) ergibt:

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}

Verbindung zur Diskreten Fourier-Transformation

Die Matrix F wandelt die erste Zeile des Zirkulanten (a,b,c,d) in den Eigenwertvektor um:

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}

Verallgemeinerung auf Ordnung n: Sp(M) = {1, ω, …, ω^{n-1}}, ω = e^{2πi/n}. DFT F berechnet f(ω^k) für das Polynom f(t) = Σ a_k t^k.

FFT reduziert die Komplexität von O(n²) auf O(n log n). Für 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-Anwendungen:

• Zirkulant-Vektor-Multiplikation: F⁻¹(FA · FB).
• Zirkulant-Zirkulant-Multiplikation: erste Zeile des Ergebnisses ist F⁻¹(FA · FB)^⊤.

Die unitäre DFT-Matrix U = F/√n hat ihr Spektrum auf dem Einheitskreis. U² ist eine Reflexionsmatrix mit Eigenwerten {1 (⌈(n+1)/2⌉ mal), -1 (⌊(n-1)/2⌋ mal)}.

Gaußsche Summen und das Spektrum von U

Die Spur von U beinhaltet die quadratische Gaußsche Summe:

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

Gaußsche Formel:

| n mod 4 | tr U |

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

| 0 | 1+i |

| 1 | 1 |

| 2 | 0 |

| 3 | i |

Das Spektrum von U wird durch die Vielfachheiten von 1, -1, i, -i über tr U bestimmt.

Wichtige Erkenntnisse:

• Zirkulanten sind Polynome in der Permutationsmatrix M, diagonalisierbar in der DFT-Basis.
• Die Zirkulantenalgebra ist isomorph zu ℂ[t]/(tⁿ-1), daher kommutativ.
• DFT berechnet das Zirkulantenspektrum effizient; FFT beschleunigt Operationen.
• Das Spektrum der unitären DFT-Matrix U hängt mit Gaußschen Summen zusammen.
• Anwendungen: schnelle Faltungen, Polynommultiplikation modulo tⁿ-1.

— Editorial Team