Circulants et DFT : propriétés et calculs

Circulants : valeurs propres, DFT et structure algébrique

Les circulants sont des matrices carrées où chaque ligne après la première est un décalage cyclique à droite de la précédente. D'ordre n, le circulant C(a₀,…,aₙ₋₁) a l'aspect suivant :

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}

Tous les calculs sont sur ℂ. Notation clé : χ_A(t) — polynôme caractéristique, μ_A(t) — polynôme minimal, Sp(A) — spectre, A* = \overline{A}^⊤ — adjoint hermitien.

Considérons la matrice de permutation cyclique M d'ordre 4 :

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

Ses puissances : M², M³, M⁴ = I. Polynôme minimal μ_M(t) = t⁴ - 1, car {I, M, M², M³} sont linéairement indépendants. Spectre Sp(M) = {±1, ±i}.

Tout circulant est un polynôme en M : C(a,b,c,d) = f(M), où f(t) = a + bt + ct² + dt³.

Propriétés algébriques et diagonalisation

Les circulants forment une sous-algèbre commutative de M_n(ℂ) :

• Le produit de circulants est un circulant : f(M)g(M) = h(M), h(t) = f(t)g(t).
• Spectre : Sp(C) = {f(λ) | λ ∈ Sp(M)}.
• Déterminant : det C(a,b,c,d) = (a+b+c+d)(a-b+c-d)(a+bi-c-di)(a-bi-c+di).
• Tous les circulants sont diagonalizables dans une base commune ; l'algèbre des circulants est isomorphe à ℂ⁴.

Les vecteurs propres de M pour λ ∈ Sp(M) résolvent :

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

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

M est unitaire (M* = M⁻¹), donc diagonalisable dans une base orthonormée. La matrice normalisée U (1/2 F, où F est la matrice DFT) donne :

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}

Lien avec la transformée de Fourier discrète

La matrice F transforme la première ligne du circulant (a,b,c,d) en le vecteur des valeurs propres :

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}

Généralisant à l'ordre n : Sp(M) = {1, ω, …, ω^{n-1}}, ω = e^{2πi/n}. La DFT F calcule f(ω^k) pour le polynôme f(t) = Σ a_k t^k.

La FFT réduit la complexité de O(n²) à O(n log n). Pour 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₁.

Applications de la FFT :

• Multiplication circulant-vecteur : F⁻¹(FA · FB).
• Multiplication circulant-circulant : première ligne du résultat est F⁻¹(FA · FB)^⊤.

La matrice DFT unitaire U = F/√n a son spectre sur le cercle unité. U² est une matrice de réflexion avec valeurs propres {1 (⌈(n+1)/2⌉ fois), -1 (⌊(n-1)/2⌋ fois)}.

Sommes gaussiennes et spectre de U

La trace de U implique la somme gaussienne quadratique :

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

Formule de Gauss :

| n mod 4 | tr U |

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

| 0 | 1+i |

| 1 | 1 |

| 2 | 0 |

| 3 | i |

Le spectre de U est déterminé par les multiplicités de 1, -1, i, -i via tr U.

Points clés :

• Les circulants sont des polynômes en la matrice de permutation M, diagonalizables dans la base DFT.
• L'algèbre des circulants est isomorphe à ℂ[t]/(tⁿ-1), donc commutative.
• La DFT calcule efficacement le spectre des circulants ; la FFT accélère les opérations.
• Le spectre de la matrice DFT unitaire U est lié aux sommes gaussiennes.
• Applications : convolutions rapides, multiplication de polynômes modulo tⁿ-1.

— Editorial Team