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

Comme dans le sujet, les coordonnées sont numérotées de $0$ à $n-1$ et tout indice de coordonnée est ramené modulo $n$ ; ainsi, par exemple, $x_{-1}=x_{n-1}$ et $x_n=x_0$. On conserve

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

I — Le spectre d'un décalage cyclique

1. L'application $T$ est linéaire puisqu'elle ne fait que permuter les coordonnées. Après un décalage, chaque coordonnée avance d'une position ; après $n$ décalages, chaque coordonnée retrouve sa place. Ainsi

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

En particulier, $T$ est inversible et

$$T^{-1}=T^{n-1}.$$

Si $\lambda$ est une valeur propre de $T$ et si $x\neq0$ vérifie $Tx=\lambda x$, alors

$$x=T^nx=\lambda^n x.$$

Comme $x\neq0$,

$$\lambda^n=1.$$

Toute valeur propre éventuelle est donc une racine $n$-ième de l'unité.

2. Soit $x=(x_0,\ldots,x_{n-1})\neq0$ tel que $Tx=\lambda x$. Les égalités coordonnées par coordonnées donnent

$$x_{r-1}=\lambda x_r, \qquad 1\leqslant r\leqslant n-1,$$

et

$$x_{n-1}=\lambda x_0.$$

Comme $\lambda^n=1$, on a $\lambda\neq0$. Les premières relations donnent alors

$$x_r=\lambda^{-r}x_0.$$

Si $x_0=0$, toutes les coordonnées seraient nulles ; donc $x_0\neq0$. Les racines $n$-ièmes de l'unité sont $1,\omega^{-1},\omega^{-2},\ldots,\omega^{-(n-1)}$.

Pour $0\leqslant k\leqslant n-1$, prenons

$$\lambda_k=\omega^{-k}.$$

L'espace propre associé est alors la droite engendrée par

$$v_k= \bigl(1,\omega^k,\omega^{2k},\ldots,\omega^{(n-1)k}\bigr).$$

Réciproquement, un calcul direct donne bien

$$Tv_k=\omega^{-k}v_k.$$

Les nombres $\omega^{-k}$, pour $0\leqslant k\leqslant n-1$, sont deux à deux distincts. L'endomorphisme $T$ possède donc $n$ valeurs propres distinctes dans un espace de dimension $n$. Il est diagonalisable et

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

est une base de $E$.

3. Si $n$ divise $m$, alors $\omega^m=1$ et

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

Supposons maintenant que $n$ ne divise pas $m$. Alors $\omega^m\neq1$ et la somme géométrique donne

$$S_m = \frac{1-(\omega^m)^n}{1-\omega^m} = \frac{1-\omega^{mn}}{1-\omega^m} =0.$$

Ainsi

$$\boxed{ \sum_{r=0}^{n-1}\omega^{mr} = \begin{cases} n&\text{si }n\mid m,\\ 0&\text{sinon.} \end{cases}}$$

II — Les opérateurs invariants par décalage

4. Comme

$$e_r=T^re_0,$$

l'action de $A$ sur $e_0$ détermine son action sur toute la base canonique. Écrivons

$$Ae_0=\sum_{j=0}^{n-1}a_je_j.$$

Pour tout $r$, on a $Ae_r=A(T^re_0)=T^r(Ae_0)=\sum_{j=0}^{n-1}a_je_{j+r}$.

D'autre part, $\left(\sum_{j=0}^{n-1}a_jT^j\right)e_r=\sum_{j=0}^{n-1}a_je_{j+r}$.

Les deux endomorphismes coïncident donc sur une base, d'où

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

L'unicité vient de l'égalité

$$Ae_0=\sum_{j=0}^{n-1}a_je_j,$$

qui détermine les coefficients $a_j$ de manière unique.

Réciproquement, toute combinaison linéaire de $I,T,\ldots,T^{n-1}$ commute avec $T$.

Pour la matrice de $A$, le coefficient situé à la ligne $r$ et à la colonne $s$ est le coefficient de $e_r$ dans $Ae_s$. Or

$$Ae_s=\sum_{j=0}^{n-1}a_je_{j+s}.$$

Le terme $e_r$ correspond à l’unique $j\in\{0,\ldots,n-1\}$ tel que $j\equiv r-s\pmod n$. Ainsi, si l’on note $[r-s]_n$ ce représentant,

$$\boxed{A_{r,s}=a_{[r-s]_n}.}$$

Chaque colonne s'obtient donc par décalage cyclique de la précédente : c'est bien la structure d'une matrice circulante.

5. D'après la question 2,

$$T^jv_k=(\omega^{-k})^jv_k=\omega^{-jk}v_k.$$

Par conséquent,

$$Av_k = \sum_{j=0}^{n-1}a_jT^jv_k = \left(\sum_{j=0}^{n-1}a_j\omega^{-jk}\right)v_k.$$

La valeur propre associée à $v_k$ est donc

$$\boxed{ \widehat a_k = \sum_{j=0}^{n-1}a_j\omega^{-jk}. }$$

C'est précisément la formule qui conduira à la transformée de Fourier discrète.

6. La base $(v_0,\ldots,v_{n-1})$ dépend uniquement de $T$, et non des coefficients $a_j$. Toute matrice circulante est donc diagonale dans cette même base, avec diagonale

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

Un endomorphisme diagonal est inversible si et seulement si aucun coefficient diagonal n'est nul. Ainsi

$$\boxed{ A\text{ est inversible} \iff \forall k\in\{0,\ldots,n-1\},\ \widehat a_k\neq0. }$$

III — Le changement de base de Fourier

7. Par définition de $\mathcal F$,

$$(\mathcal Fx)_k = \sum_{j=0}^{n-1}\omega^{-kj}x_j = \widehat x_k.$$

Donc

$$\widehat x=\mathcal Fx.$$

Posons

$$\mathcal G=(\omega^{jk})_{0\leqslant j,k\leqslant n-1}.$$

Le coefficient situé à la ligne $r$ et à la colonne $s$ de $\mathcal G\mathcal F$ vaut

$$\sum_{k=0}^{n-1}\omega^{rk}\omega^{-ks} = \sum_{k=0}^{n-1}\omega^{(r-s)k}.$$

D'après la question 3, cette somme vaut $n$ si $r=s$ et $0$ sinon. Ainsi

$$\mathcal G\mathcal F=nI_n.$$

Comme $\mathcal F$ est carrée,

$$\boxed{ \mathcal F^{-1}=\frac1n\mathcal G =\frac1n(\omega^{jk})_{0\leqslant j,k\leqslant n-1}. }$$

On obtient alors

$$x=\mathcal F^{-1}\widehat x,$$

c'est-à-dire, pour chaque $j$,

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

8. La coordonnée d'indice $j$ de $\frac1n\sum_{k=0}^{n-1}\widehat x_kv_k$ vaut $\frac1n\sum_{k=0}^{n-1}\widehat x_k\omega^{jk}$, c'est-à-dire $x_j$ par la formule d'inversion. Ainsi

$$\boxed{ x=\frac1n\sum_{k=0}^{n-1}\widehat x_kv_k.}$$

Les coordonnées de $x$ dans la base propre $(v_k)$ sont donc

$$\frac{\widehat x_0}{n},\ldots,\frac{\widehat x_{n-1}}{n}.$$

Pour Parseval, développons :

$$\begin{aligned} \sum_{k=0}^{n-1}|\widehat x_k|^2 &= \sum_{k=0}^{n-1} \left(\sum_{j=0}^{n-1}x_j\omega^{-jk}\right) \left(\sum_{\ell=0}^{n-1}\overline{x_\ell}\omega^{\ell k}\right)\\ &= \sum_{j=0}^{n-1}\sum_{\ell=0}^{n-1} x_j\overline{x_\ell} \sum_{k=0}^{n-1}\omega^{(\ell-j)k}. \end{aligned}$$

La somme intérieure vaut $n$ lorsque $j=\ell$ et $0$ sinon. Il reste donc

$$\boxed{ \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. Comme $(T^jx)_r=x_{r-j}$, on obtient directement

$$(C_ax)_r = \sum_{j=0}^{n-1}a_jx_{r-j}.$$

C'est donc bien la formule $(a*x)_r=\sum_{j=0}^{n-1}a_jx_{r-j}$ annoncée pour la convolution cyclique.

D'après la question 8, $x=\frac1n\sum_{k=0}^{n-1}\widehat x_kv_k$, tandis que la question 5 donne $C_av_k=\widehat a_kv_k$. Par conséquent,

$$a*x=C_ax=\frac1n\sum_{k=0}^{n-1}\widehat x_k\widehat a_kv_k.$$

Par unicité des coordonnées dans la base $(v_k)$, les coefficients de Fourier de $a*x$ sont

$$\boxed{ \widehat{a*x}_k = \widehat a_k\widehat x_k. }$$

La convolution dans la base canonique devient donc une multiplication coordonnée par coordonnée dans la base de Fourier.

10. Pour tout $k$, $Tv_k=\omega^{-k}v_k$ et $T^{-1}v_k=\omega^kv_k$. Ainsi

$$Lv_k=\bigl(2-\omega^{-k}-\omega^k\bigr)v_k.$$

(a) Comme $\omega^k+\omega^{-k}=2\cos(2\pi k/n)$, la valeur propre correspondante est

$$\lambda_k =2-2\cos\left(\frac{2\pi k}{n}\right) =4\sin^2\left(\frac{\pi k}{n}\right).$$

Cette écriture montre immédiatement que $\lambda_k$ est réelle et positive ou nulle. Ainsi

$$\boxed{ \lambda_k=4\sin^2\left(\frac{\pi k}{n}\right)\geqslant0. }$$

(b) Pour $0\leqslant k\leqslant n-1$, on a $\lambda_k=0$ si et seulement si $k=0$. Ainsi $\ker L=\operatorname{Vect}(v_0)$ et, comme $v_0=(1,1,\ldots,1)$,

$$\boxed{ \ker L=\operatorname{Vect}(1,1,\ldots,1). }$$

(c) Appliquons la transformée de Fourier à l’équation $Lx=b$. D’après la diagonalisation obtenue en (a), pour chaque $k$ on a $\widehat{Lx}_k=\lambda_k\widehat x_k$. L’équation $Lx=b$ équivaut donc à

$$\lambda_k\widehat x_k=\widehat b_k, \qquad 0\leqslant k\leqslant n-1.$$

Pour $k\neq0$, $\lambda_k>0$, donc $\widehat x_k=\widehat b_k/\lambda_k$. Pour $k=0$, l'équation devient $0=\widehat b_0$, avec $\widehat b_0=\sum_{j=0}^{n-1}b_j$.

Ainsi

$$\boxed{ Lx=b\text{ admet une solution} \iff \sum_{j=0}^{n-1}b_j=0. }$$

Lorsque cette condition est satisfaite, les coefficients $\widehat x_k$ sont imposés pour $k\neq0$, tandis que $\widehat x_0$ est arbitraire. Deux solutions diffèrent donc d'un élément de $\ker L$, c'est-à-dire d'un vecteur constant.

Si $x_*$ est une solution particulière,

$$\boxed{ \{x\in E:Lx=b\} = x_*+\operatorname{Vect}(1,\ldots,1). }$$

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

11. Posons

$$S=\operatorname{supp}x, \qquad s=|S|,$$

et

$$R=\operatorname{supp}\widehat x, \qquad r=|R|.$$

Comme $x\neq0$, on a $s\geqslant1$. La transformée de Fourier étant inversible, $\widehat x\neq0$ et donc $r\geqslant1$.

Pour tout $k$, $|\widehat x_k|=\left|\sum_{j\in S}x_j\omega^{-jk}\right|\leqslant\sum_{j\in S}|x_j|$.

En appliquant Cauchy-Schwarz aux deux familles réelles $(|x_j|)_{j\in S}$ et $(1)_{j\in S}$,

$$\left(\sum_{j\in S}|x_j|\right)^2 \leqslant s\sum_{j\in S}|x_j|^2 =s\|x\|_2^2.$$

Par conséquent,

$$|\widehat x_k|^2\leqslant s\|x\|_2^2.$$

Seuls les indices de $R$ contribuent à $\|\widehat x\|_2^2$, donc

$$\sum_{k=0}^{n-1}|\widehat x_k|^2=\sum_{k\in R}|\widehat x_k|^2\leqslant rs\|x\|_2^2.$$

D'autre part, Parseval donne $n\|x\|_2^2=\sum_{k=0}^{n-1}|\widehat x_k|^2$.

Donc

$$n\|x\|_2^2 \leqslant rs\|x\|_2^2.$$

Comme $x\neq0$, $\|x\|_2^2>0$ et l'on peut simplifier :

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

12. Comme $q=n/d$, les indices de $\{0,\ldots,n-1\}$ divisibles par $q$ sont $0,q,2q,\ldots,(d-1)q$. Il y en a exactement $d$, donc $|\operatorname{supp}x|=d$.

Pour tout $k$, $\widehat x_k=\sum_{m=0}^{d-1}\omega^{-mqk}$. Or $\omega^q=e^{2i\pi/d}$, donc $\widehat x_k=\sum_{m=0}^{d-1}e^{-2i\pi mk/d}$. Cette somme vaut $d$ si $d$ divise $k$, et $0$ sinon. Ainsi

$$\boxed{ \widehat x_k= \begin{cases} d&\text{si }d\mid k,\\ 0&\text{sinon.} \end{cases}}$$

Dans $\{0,\ldots,n-1\}$, les multiples de $d$ sont $0,d,2d,\ldots,(q-1)d$. Il y en a $q=n/d$, donc $|\operatorname{supp}\widehat x|=n/d$. Finalement, $|\operatorname{supp}x|\,|\operatorname{supp}\widehat x|=d(n/d)=n$.

L'égalité est donc atteinte. Si $n$ est composé, tout diviseur non trivial $1<d<n$ fournit un exemple où les deux supports ont strictement moins de $n$ éléments tout en saturant exactement le principe d'incertitude.

Le même changement de base relie ainsi la réduction d'un endomorphisme, la diagonalisation simultanée des matrices circulantes, la convolution cyclique et la concentration des vecteurs. La transformée de Fourier discrète n'est pas ici une formule isolée : elle est le système de coordonnées naturellement adapté au décalage cyclique.