Décalages cycliques, matrices circulantes et transformée de Fourier

Sur un cycle de $n$ positions, décaler toutes les coordonnées d'un cran ne change aucune relation qui dépend seulement des écarts de position. Cette symétrie impose une base remarquable : dans cette base, le décalage devient diagonal, puis tout opérateur qui lui est invariant se réduit à $n$ multiplications indépendantes. On fera apparaître cette base à partir du problème spectral lui-même, avant d'en tirer la transformée de Fourier discrète, la convolution cyclique et une limite à la concentration simultanée d'un vecteur et de ses coefficients de Fourier.

Dans tout le problème, $n\geqslant2$, $E=\mathbb C^n$, et les coordonnées sont numérotées de $0$ à $n-1$. Lorsqu’un indice de coordonnée sort de cet intervalle, il est ramené modulo $n$ : par exemple, $x_{-1}=x_{n-1}$ et $x_n=x_0$. On pose

$$T(x_0,x_1,\ldots,x_{n-1})=(x_{n-1},x_0,\ldots,x_{n-2})$$

et

$$\omega=e^{2i\pi/n}.$$

I — Le spectre d'un décalage cyclique

1. Montrer que $T$ est un automorphisme de $E$ et que

$$T^n=\operatorname{Id}_E.$$

Que peut-on déjà en déduire sur une éventuelle valeur propre de $T$ ?

2. Déterminer, sans calculer de déterminant, toutes les valeurs propres de $T$ et les espaces propres correspondants. En déduire que $T$ est diagonalisable et faire apparaître explicitement une base propre

$$(v_0,v_1,\ldots,v_{n-1}).$$

On choisira les vecteurs $v_k$ de sorte que leur première coordonnée soit égale à $1$.

3. Pour $m\in\mathbb Z$, calculer

$$S_m=\sum_{r=0}^{n-1}\omega^{mr}$$

en distinguant les cas où $n$ divise $m$ ou non.

II — Les opérateurs invariants par décalage

On note $(e_0,\ldots,e_{n-1})$ la base canonique de $E$.

4. Soit $A\in\mathcal L(E)$ tel que

$$AT=TA.$$

Montrer qu'il existe un unique $n$-uplet $(a_0,\ldots,a_{n-1})\in\mathbb C^n$ tel que

$$A=a_0I+a_1T+\cdots+a_{n-1}T^{n-1}.$$

Exprimer alors le coefficient de la matrice de $A$ situé à la ligne $r$ et à la colonne $s$ en fonction des $a_j$. Une telle matrice sera appelée matrice circulante.

5. Pour $0\leqslant k\leqslant n-1$, déterminer la valeur propre de $A$ associée au vecteur propre $v_k$ construit à la question 2. On notera cette valeur propre $\widehat a_k$.

6. En déduire que toutes les matrices circulantes sont diagonalisées par la même base. Caractériser l'inversibilité de $A$ à l'aide des nombres

$$\widehat a_0,\widehat a_1,\ldots,\widehat a_{n-1}.$$

III — Le changement de base de Fourier

Pour $x=(x_0,\ldots,x_{n-1})\in E$, on définit désormais

$$\widehat x_k=\sum_{j=0}^{n-1}x_j\omega^{-jk}, \qquad 0\leqslant k\leqslant n-1.$$

Le vecteur $\widehat x=(\widehat x_0,\ldots,\widehat x_{n-1})$ est appelé transformée de Fourier discrète de $x$.

7. Soit

$$\mathcal F=\bigl(\omega^{-kj}\bigr)_{0\leqslant k,j\leqslant n-1}.$$

Montrer que $\widehat x=\mathcal F x$, puis déterminer $\mathcal F^{-1}$. En déduire la formule d'inversion

$$x_j=\frac1n\sum_{k=0}^{n-1}\widehat x_k\omega^{jk}.$$

8. Relier les nombres $\widehat x_k$ aux coordonnées de $x$ dans la base propre $(v_0,\ldots,v_{n-1})$. Puis démontrer l'identité de Parseval

$$\sum_{k=0}^{n-1}|\widehat x_k|^2 = n\sum_{j=0}^{n-1}|x_j|^2.$$

IV — De la matrice circulante à la convolution

9. Pour $a=(a_0,\ldots,a_{n-1})\in E$, on pose

$$C_a=\sum_{j=0}^{n-1}a_jT^j.$$

Calculer la coordonnée d'indice $r$ de $C_ax$. On note alors $a*x=C_ax$ et l'on appelle $a*x$ la convolution cyclique de $a$ et $x$.

Montrer que, pour tout $k$, $\widehat{a*x}_k=\widehat a_k\,\widehat x_k$.

10. On considère l'endomorphisme

$$L=2I-T-T^{-1}.$$

(a) Déterminer les valeurs propres de $L$ dans la base $(v_0,\ldots,v_{n-1})$. Montrer qu’elles sont réelles et positives ou nulles.

(b) Déterminer $\ker L$.

(c) Pour $b\in E$, déterminer une condition nécessaire et suffisante pour que l’équation

$$Lx=b$$

admette une solution. Lorsque cette condition est satisfaite, décrire toutes les solutions.

V — Peut-on être concentré dans les deux bases ?

Pour $x\in E$, on note

$$\operatorname{supp}x=\{j\in\{0,\ldots,n-1\}:x_j\neq0\}$$

et

$$\|x\|_2=\left(\sum_{j=0}^{n-1}|x_j|^2\right)^{1/2}.$$

11. Soit $x\neq0$. En utilisant l'identité de Parseval et l'inégalité de Cauchy-Schwarz, démontrer le principe d'incertitude discret

$$\boxed{ |\operatorname{supp}x|\, |\operatorname{supp}\widehat x| \geqslant n. }$$

12. Soit $d$ un diviseur de $n$ et $q=n/d$. On définit $x\in E$ par

$$x_j= \begin{cases} 1&\text{si }q\text{ divise }j,\\ 0&\text{sinon.} \end{cases}$$

Déterminer $\widehat x$, puis les cardinalités de $\operatorname{supp}x$ et de $\operatorname{supp}\widehat x$. En déduire que l'inégalité de la question 11 peut être une égalité. Que donnent en particulier les diviseurs non triviaux lorsque $n$ est composé ?

Synthèse. La formule d'inversion montre que les coordonnées de $x$ dans la base propre $(v_0,\ldots,v_{n-1})$ du décalage cyclique $T$ sont $\widehat x_k/n$. Dans cette base, $T$ est diagonal. Les endomorphismes qui commutent avec $T$ sont exactement les matrices circulantes ; ils sont donc diagonaux dans la même base. Pour $C_a=\sum_{j=0}^{n-1}a_jT^j$, les nombres $\widehat a_k$ sont les valeurs propres de $C_a$, et l'identité $\widehat{a*x}_k=\widehat a_k\,\widehat x_k$ montre que la convolution cyclique devient une multiplication terme à terme après transformée de Fourier. Lorsque $n$ se factorise, cette structure permet aussi de décomposer le calcul de la transformée en calculs plus petits et de réduire le nombre d'opérations : c'est le principe des algorithmes de transformée de Fourier rapide.