Inscription / Connexion Nouveau Sujet
Accueil l'île des mathématiques Forum de mathématiquesListe de tous les forums de mathématiques SupérieurOn parle exclusivement de maths, pour le supérieur principalement, les BTS, IUT, prépas... École ingénieur AlgèbreTopics traitant de algèbre [tout]Lister tous les topics de mathématiques

1 2 +

Niveau école ingénieur
Partager :

Transformée de Fourier discrète (suite 1)

Posté par
matheux14 18-09-23 à 02:37

Bonjour,

C'est la suite de ce problème Transformée de Fourier discrète.

Dans toute la suite de cette partie nous supposerons que N est impair et notre objectif est de d´eterminer la dimension des espaces propres de U. Pour \alpha \in \C on note m_{\alpha} = \dim(ker(U_n - \alpha I_N)).


1-a) Montrer que \sum\limits_{0 \le \ell < k \le N - 1} (k + \ell) = \dfrac{N(N - 1)^2}{2}.

b) Montrer que \det(U) = N^{-\frac{N}{2}} i^{\frac{N(N - 1)}{2}} (-1)^{\frac{N(N - 1)}{2}} \prod\limits_{0 \le \ell < k \le N - 1} \left(2 \sin\left(\dfrac{\pi(k - \ell)}{N}\right)\right)

2) On pose S = \sum\limits^{N - 1}_{\ell = 0} \zeta^{\ell^2}. Montrer que |S| = \sqrt{N}.


3) En déduire que :

(m_1 - m_{-1})^2 + (m_i - m_{-i})^2 = 1

et qu'il existe des nombres \varepsilon \in \{-1, +1\} et \eta \in \{1, i\} tels que S = \varepsilon \eta \sqrt{N}.

4) En considérant la matrice U^2, montrer que

m_1 + m_{-1} - m_i - m_{-i} = 1.

5) Montrer que :

- Si N \equiv 1 [4] alors \eta = 1 ;

- Si N \equiv 3 [4] alors \eta = i.

6) Montrer que \det(U) = i^{\frac{N(N - 1)}{2}} \varepsilon et en déduire la valeur de \varepsilon en fonction de N.

7) Conclure que, si M = \lfloor N/4 \rfloor, on a

\begin{cases} m_1 = M + 1 \text{ et } m_{-1} = m_{-i} = M \text{ si } N \equiv 1 [4], \\\ \\ m_1 = m_{-1} = m_{-i} = M + 1 \text{ et } m_{i} = M \text{ si } N \equiv 3 [4]\end{cases}.

Réponses

1-a) Je ne trouve pas la même chose comme l'énoncé.

Je trouve plutôt \dfrac{N(N^2 - 1)}{2}.

\begin{aligned} \sum\limits_{0 \le \ell < k \le N - 1} (k + \ell) &= \sum\limits^{N - 1}_{k = 0} \sum\limits^{k}_{\ell = 0} (k + \ell) \\\\ &= \sum\limits^{N - 1}_{k = 0}\left(\sum\limits^{k}_{\ell = 0} k + \sum\limits^{k}_{\ell = 0} \ell\right) \\\\ &= \sum\limits^{N - 1}_{k = 0}\left(k(k + 1) + \dfrac{k(k + 1)}{2}\right) \\\\ &= \dfrac{3}{2} \sum\limits^{N - 1}_{k = 0} k^2 + \dfrac{3}{2}\sum\limits^{N - 1}_{k = 0} k \\\\ &= \dfrac{N(N - 1)(2N - 1)}{4} + \dfrac{3N(N - 1)}{4} \\\\ &= \dfrac{N(N - 1)(N + 1)}{2} \end{aligned}

\boxed{\sum\limits_{0 \le \ell < k \le N - 1} (k + \ell) = \dfrac{N(N^2 - 1)}{2}}

1-b) On a \det(V(\alpha)) = \prod\limits_{1 \le i < j \le N} (\alpha_j - \alpha_i)

Il me semble que \det(U) = \dfrac{1}{\sqrt N}\prod\limits_{1 \le \ell < k \le N} (\zeta^k - \zeta^{\ell}).

Posté par
GBZMre : Transformée de Fourier discrète (suite 1) 18-09-23 à 10:53

Bonjour,
Puisque 0\leq \ell<k, \ell va de 0 à k-1 et pas k.

Le déterminant de \dfrac1{\sqrt{N}}V n'est pas \dfrac1{\sqrt{N}}\det(V).

Posté par
matheux14re : Transformée de Fourier discrète (suite 1) 19-09-23 à 00:24

Bonsoir GBZM

1-a)

\begin{aligned} \sum\limits_{0 \le \ell < k \le N - 1} (k + \ell) &=\sum\limits^{N - 1}_{k = 0} \sum\limits^{k - 1}_{\ell = 0} (k + \ell) \\\\ &= \sum\limits^{N - 1}_{k = 0}\left(\sum\limits^{k - 1}_{\ell = 0} k + \sum\limits^{k - 1}_{\ell = 0} \ell\right) \\\\ &= \sum\limits^{N - 1}_{k = 0}\left(k(k - 1) + \dfrac{k(k - 1)}{2}\right) \\\\ &= \dfrac{3}{2} \sum\limits^{N - 1}_{k = 0} k^2 - \dfrac{3}{2}\sum\limits^{N - 1}_{k = 0} k \\\\ &= \dfrac{N(N - 1)(2N - 1)}{4} - \dfrac{N(N - 1)}{4} \\\\ &= \dfrac{N(N - 1)^2}{2} \end{aligned}

Pour le déterminant

1-b) J'ai essayé de calculer pour N = 3 et c'est assez laborieux..

Posté par
GBZMre : Transformée de Fourier discrète (suite 1) 19-09-23 à 07:24

\zeta^k-\zeta^\ell = {?}
On cherche bien sûr une expression qui nous rapproche du résultat demandé en 1 b).

Posté par
matheux14re : Transformée de Fourier discrète (suite 1) 19-09-23 à 22:23

Bonsoir GBZM

Soit x_n = \cos\left(\dfrac{2\pi n}{N}\right) et y_n = \sin\left(\dfrac{2\pi n}{N}\right), on a

\zeta^k - \zeta^{\ell} = (x_k - x_{\ell}) - i (y_{\ell} - y_k)

Posté par
matheux14re : Transformée de Fourier discrète (suite 1) 19-09-23 à 22:51

\zeta^k - \zeta^{\ell} = 2 \sin\left(\dfrac{\pi(k + \ell)}{N}\right) \sin\left(\dfrac{\pi(\ell - k)}{N}\right) -2 i \left(\cos\left(\dfrac{\pi(k + \ell)}{N}\right) \sin\left(\dfrac{\pi(k - \ell)}{N}\right)\right)

Posté par
GBZMre : Transformée de Fourier discrète (suite 1) 19-09-23 à 23:37

Il y a un problème de signe, et je me débrouillerais pour mieux arranger les choses en vue du produit à faire et de l'expression finale qu'on vise.

Posté par
GBZMre : Transformée de Fourier discrète (suite 1) 20-09-23 à 16:21

Désolé, pas de problème de signe, juste que la façon dont tu as écrit l'expression fait qu'il n'est pas commode de s'y retrouver.

Posté par
matheux14re : Transformée de Fourier discrète (suite 1) 21-09-23 à 16:57

Est-ce qu'il faut calculer \dfrac{1}{\sqrt N}\prod\limits_{1 \le \ell < k \le N} (\zeta^k - \zeta^{\ell}) ?

Je me suis arrêter à l'expression du 19-09-23 à 22:51 parce que j'ai vu 2\sin\left(\dfrac{\pi(k - \ell)}{N}\right) qui se retrouve dans le résultat demandé.

Posté par
matheux14re : Transformée de Fourier discrète (suite 1) 21-09-23 à 16:59

Plutôt \dfrac{1}{\sqrt N}\prod\limits_{1 \le \ell < k \le N - 1} (\zeta^k - \zeta^{\ell})

Posté par
GBZMre : Transformée de Fourier discrète (suite 1) 21-09-23 à 17:13

Attention, tu fais de nouveau comme si le déterminant de \dfrac1{\sqrt{N}} V était \dfrac1{\sqrt{N}}\det(V).
Ensuite c'est bien de faire ressortir \sin\left(\dfrac{\pi(k-\ell)}{N}\right), mais alors il vaut mieux le mettre en facteur et s'arranger pour que l'autre facteur soit sympa !
Je procéderais ainsi :
\large e^{-2i\,k\,\pi/N}-e^{-2i\,\ell\,\pi/N}=e^{-i(k+\ell)\pi/N}\left(e^{-i(k-\ell)\pi/N}-e^{i(k-\ell)\pi/N}\right),
et on reconnaît dans ce qui est entre parenthèses -2i\sin\left((k-\ell)\pi/N\right).

Posté par
matheux14re : Transformée de Fourier discrète (suite 1) 21-09-23 à 17:21

Oui, c'est bien ce que j'ai fait.

Mais ce qui me pose problème, c'est le produit qu'il faut calculer.

Posté par
matheux14re : Transformée de Fourier discrète (suite 1) 21-09-23 à 17:23

Puisque que déterminant de \dfrac1{\sqrt{N}}V n'est pas \dfrac1{\sqrt{N}}\det(V), comment utiliser ce \dfrac1{\sqrt{N}} ?

Posté par
GBZMre : Transformée de Fourier discrète (suite 1) 21-09-23 à 17:54

M'enfin ??? Tu ne vois pas ce qu'est le déterminant de \lambda M en fonction de \lambda, de \det(M) et de la taille de M ?

Posté par
GBZMre : Transformée de Fourier discrète (suite 1) 21-09-23 à 17:57

matheux14 @ 21-09-2023 à 17:21

Mais ce qui me pose problème, c'est le produit qu'il faut calculer.

Quel problème est-ce que cela te pose ? Le seul problème un peu délicat est réglé par la question 1 a) (il faut bien qu'elle serve à quelque chose !).

Posté par
matheux14re : Transformée de Fourier discrète (suite 1) 21-09-23 à 22:21

Désolé, je m'étais un peu melangé dans les calculs.

1-b) La matrice de Vandermonde V(\alpha) est définie par V(\alpha) = (\alpha^{j - 1}_i)_{1 \le i, j \le n} et

\det(V(\alpha)) = \prod\limits_{1 \le i < j \le N} (\alpha_j - \alpha_i).

On a pu exprimer U en fonction de la matrice de la matrice de Vandermonde :

U = \dfrac{1}{\sqrt{N}} V(1, \zeta, \zeta^2, \dots, \zeta^{N - 1})

Puis on va

Citation :
arranger les choses en vue du produit à faire et de l'expression finale qu'on vise.


Intuitivement, on calcule \zeta^k - \zeta^{\ell}, et puisque \det(V(\alpha)) = \prod\limits_{1 \le i \le j \le N} (\alpha_j - \alpha_i), on a \det(U) = \left(\dfrac{1}{\sqrt{N}}\right)^N \prod\limits_{0 \le \ell < k \le N - 1} (\alpha_k - \alpha_{\ell}) = \left(\dfrac{1}{\sqrt{N}}\right)^N \prod\limits_{0 \le \ell < k \le N - 1} (\zeta^k - \zeta^{\ell}) on trouve

\zeta^k - \zeta^{\ell} = -2 \sin\left(\dfrac{\pi(k - \ell)}{N}\right) e^{i\frac{\pi(k + \ell)}{N}} en poursuivant ce calcul
Citation :
\large e^{-2i\,k\,\pi/N}-e^{-2i\,\ell\,\pi/N}=e^{-i(k+\ell)\pi/N}\left(e^{-i(k-\ell)\pi/N}-e^{i(k-\ell)\pi/N}\right),


\det(U) =N^{-N/2} \prod\limits_{0 \le \ell < k \le N - 1} \left(-e^{-i\frac{(k + \ell)\pi}{N}}\right) \times (-i) \times \prod\limits_{0 \le \ell < k \le N - 1} \left(2\sin\left(\dfrac{(k - \ell)\pi}{N}\right)\right)

\det(U) = N^{-N/2} i^{\frac{N(N - 1)}{2}}  (-1)^{\frac{N(N - 1)}{2}} \prod\limits_{0 \le \ell < k \le N - 1} \left(e^{-i\frac{(k + \ell)\pi}{N}}\right) \prod\limits_{0 \le \ell < k \le N - 1} \left(2\sin\left(\dfrac{(k - \ell)\pi}{N}\right)\right)

Soit \mathcal{P} = \prod\limits_{0 \le \ell < k \le N - 1} \left(e^{-i\frac{(k + \ell)\pi}{N}}\right)

\ln(\mathcal{P}) = \sum\limits_{0 \le \ell < k \le N - 1} \left(-i\frac{(k + \ell)\pi}{N}\right) = -\dfrac{i \pi}{N} \sum\limits_{0 \le \ell < k \le N - 1} (k + \ell) = -\dfrac{i \pi}{N} \dfrac{N(N - 1)^2}{2}

\ln(\mathcal{P}) = - \dfrac{i \pi(N - 1)^2}{2} \Longrightarrow \mathcal{P} = \left(e^{-i2\pi}\right)^{N - 1} = 1

Finalement on a bien

\boxed{\det(U) = N^{-N/2} i^{\frac{N(N - 1)}{2}}  (-1)^{\frac{N(N - 1)}{2}} \prod\limits_{0 \le \ell < k \le N - 1} \left(2\sin\left(\dfrac{(k - \ell)\pi}{N}\right)\right)}

2) S = \sum\limits^{N - 1}_{\ell = 0} \zeta^{\ell^2} = \sum\limits^{N - 1}_{\ell = 0} e^{-\frac{i 4 \pi \ell}{N}} = \sum\limits^{N - 1}_{\ell = 0} 1 = N \Longrightarrow |S| = \sqrt{N} puisque e^{-i4\pi} = 1

Posté par
GBZMre : Transformée de Fourier discrète (suite 1) 21-09-23 à 23:21

Non, ça ne va pas.
Je commence à fatiguer.

Posté par
matheux14re : Transformée de Fourier discrète (suite 1) 22-09-23 à 09:31

Qu'est ce qui ne va pas ?

Posté par
GBZMre : Transformée de Fourier discrète (suite 1) 22-09-23 à 09:47

Tu apportes un soin extrême à la présentation LaTeX. Si seulement tu pouvais apporter le même soin aux calculs eux-mêmes !
Je relève : un facteur i oublié dans \zeta^k-\zeta^{\ell}, un signe - en trop dans la première ligne de \det(U).
Plus embêtant :
- comment justifies tu ton \mathcal P= \ldots ? Il vaudrait mieux d'ailleurs ne pas parler du logarithme népérien d'un nombre complexe !
- ce que tu as écrit pour la question 2), c'est vraiment n'importe quoi !

Posté par
GBZMre : Transformée de Fourier discrète (suite 1) 22-09-23 à 15:50

L'hypothèse N impair sert à la fois pour 1b) et pour 2.
Pour le calcul de |S|, il n'est pas inutile de se rappeler que |S|^2= S\bar S.

Posté par
matheux14re : Transformée de Fourier discrète (suite 1) 22-09-23 à 21:09

Je ne vois pas vraiment comment utiliser parité de N.

Après avoir rectifié les erreurs de signes, il semble qu'on doit montrer que \mathcal{P} = \prod\limits_{0 \le \ell < k \le N - 1} \left(e^{-i\frac{(k + \ell)\pi}{N}}\right) = 1 pour aboutir au résultat.

Si N = 2n + 1

On a \prod\limits_{0 \le \ell < k \le N - 1} \left(e^{-i\frac{(k + \ell)\pi}{N}}\right) = \prod\limits_{0 \le \ell < k \le 2n} \left(e^{-i\frac{(k + \ell)\pi}{2n + 1}}\right) = \prod\limits^{2n}_{k = 0} \prod\limits^{k - 1}_{\ell = 0} e^{-i\frac{(k + \ell)\pi}{2n + 1}}

Posté par
GBZMre : Transformée de Fourier discrète (suite 1) 22-09-23 à 21:49

Sans avoir besoin de passer par le logarithme, le produit d'exponentielle est l'exponentielle de la somme.

Posté par
matheux14re : Transformée de Fourier discrète (suite 1) 23-09-23 à 21:59

Bonsoir GBZM

\prod\limits_{0 \le \ell < k \le N - 1} \left(e^{-i\frac{(k + \ell)\pi}{N}}\right) = e^{-\frac{i \pi}{N} \sum\limits_{0 \le \ell < k \le N - 1} (k + \ell)} = e^{-\frac{i \pi N(N - 1)^2}{N}} = e^{-i\pi(N - 1)^2}

Pour N = 2p + 1

\prod\limits_{0 \le \ell < k \le N - 1} \left(e^{-i\frac{(k + \ell)\pi}{N}}\right) = e^{-i\pi(2p)^2} = 1

Si N = 2p

\prod\limits_{0 \le \ell < k \le N - 1} \left(e^{-i\frac{(k + \ell)\pi}{N}}\right) = e^{-i\pi(2p - 1)^2} = -1

Comme N est impair d'après l'énoncé, on a bien le résultat souhaité.

2) On a |S|^2 = S \cdot \overline{S}

|S|^2 = \left(\sum\limits^{N - 1}_{\ell = 0} \zeta^{\ell^2}\right)\left(\sum\limits^{N - 1}_{\ell = 0} \zeta^{-\ell^2}\right)

Il me semble qu'il faut utiliser le fait que N est impair pour montrer qu'on peut écrire

|S|^2 = \left(\sum\limits^{N - 1}_{\ell = 0} \zeta^{\ell^2}\right)\left(\sum\limits^{N - 1}_{\ell = 0} \zeta^{-\ell^2}\right) = \sum\limits^{N - 1}_{\ell = 0} \zeta^{\ell^2} \cdot \zeta^{-\ell^2} = N \Longrightarrow |S| = \sqrt{N}

Mais je ne vois pas vraiment, si je ne raconte pas n'importe quoi bien sur..

Posté par
GBZMre : Transformée de Fourier discrète (suite 1) 24-09-23 à 11:45

1b) : Tu es sûr d'avoir trouvé N(N-1)^2 comme résultat du calcul de la question 1a) ? Tu perds beaucoup de temps avec tes fautes d'inattention.
2) : Le boulot reste à faire. On peut se souvenir que k^2-\ell^2=(k+\ell)(k-\ell), et traiter k et \ell comme des entiers modulo N (c'est plus commode).

Posté par
matheux14re : Transformée de Fourier discrète (suite 1) 24-09-23 à 21:03

Oui, j'ai corrigé les erreurs pour 1-b)

2) |S|^2 = \left(\sum\limits^{N - 1}_{k = 0} \zeta^{k^2}\right)\left(\sum\limits^{N - 1}_{\ell = 0} \zeta^{-\ell^2}\right) = \sum\limits^{N - 1}_{k = 0}\sum\limits^{N - 1}_{\ell = 0}  \zeta^{k^2 - \ell^2} = \sum\limits^{N - 1}_{k = 0}\sum\limits^{N - 1}_{\ell = 0} \zeta^{(k - \ell)(k + \ell)}

Ensuite on a k - \ell \equiv 0 [N] or \sum\limits^{N - 1}_{n = 0} \zeta^{nq} = \begin{cases} 1 \text{ si } N \mid q \\\\ 0 \text{ sinon} \end{cases}

Donc \sum\limits^{N - 1}_{\ell = 0} \zeta^{(k - \ell)(k + \ell)} = 1 \Longrightarrow |S|^2 = \sum\limits^{N - 1}_{k = 0}\sum\limits^{N - 1}_{\ell = 0}  \zeta^{k^2 - \ell^2} = \sum\limits^{N - 1}_{k = 0}\sum\limits^{N - 1}_{\ell = 0} \zeta^{(k - \ell)(k + \ell)} =  \sum\limits^{N - 1}_{k = 0} 1 = N \Longrightarrow |S| = \sqrt{N}

Posté par
GBZMre : Transformée de Fourier discrète (suite 1) 25-09-23 à 10:38

Je n'ai pas vu la correction pour le 1b).
Et tu écris toujours n'importe quoi pour la 2)

matheux14 @ 24-09-2023 à 21:03

Ensuite on a k - \ell \equiv 0 [N]

Posté par
matheux14re : Transformée de Fourier discrète (suite 1) 25-09-23 à 11:07

k et \ell sont congrus modulo N signifie que k - \ell \equiv 0 [N] non ?

Je crois que vous me conseilliez d'utiliser les restes de k et \ell par N peut-être..

pour 1-b) \prod\limits_{0 \le \ell < k \le N - 1} \left(e^{-i\frac{(k + \ell)\pi}{N}}\right) =  e^{-\frac{i\pi(N - 1)^2}{2}}

Pour N = 2p + 1,

\prod\limits_{0 \le \ell < k \le N - 1} \left(e^{-i\frac{(k + \ell)\pi}{N}}\right) = e^{-\frac{i\pi(2p)^2}{2}} = e^{-i 2 \pi p^2} = 1 car p^2 est un entier.

Posté par
GBZMre : Transformée de Fourier discrète (suite 1) 25-09-23 à 12:20

OK pour 1b).
J'ai écrit

GBZM @ 24-09-2023 à 11:45

traiter k et \ell comme des entiers modulo N (c'est plus commode)
Je n'ai jamais suggéré qu'ils étaient congrus modulo N, bien sûr !
On peut fixer k-\ell=m modulo N et faire varier \ell de 0 à N-1 pour regarder les valeurs de k+\ell= m+2\ell modulo N. Ici l'hypothèse N impair sert.

Posté par
matheux14re : Transformée de Fourier discrète (suite 1) 25-09-23 à 13:55

J'ai pas compris, comme ceci |S|^2 = \sum_{\ell=0}^{N-1} \zeta^{m(m + 2 \ell)} ?

Posté par
GBZMre : Transformée de Fourier discrète (suite 1) 25-09-23 à 14:16

Non, \large |S|^2 =\sum_{m=0}^{N-1} \sum_{\ell=0}^{N-1} \zeta^{m(m + 2 \ell)}

Posté par
matheux14re : Transformée de Fourier discrète (suite 1) 25-09-23 à 20:17

|S|^2 =\sum_{m=0}^{N-1} \sum_{\ell=0}^{N-1} \zeta^{m(m + 2 \ell)}

En poursuivant ce calcul je retombe sur |S|^2 = \sum_{m=0}^{N-1} \zeta^{m^2}

Pour N = 2p + 1,  |S|^2 = \sum_{m=0}^{2p} \zeta^{m^2}

Posté par
GBZMre : Transformée de Fourier discrète (suite 1) 26-09-23 à 09:27

Pourquoi avoir suggéré d'écrire |S|^2 sous cette forme ? Pour que tu penses à calculer

\large\sum_{\ell=0}^{N-1}\zeta^{m(m+2\ell)}=\sum_{\ell=0}^{N-1}\left(\zeta^{m}\right)^{m+2\ell}.

Le résultat dépend bien sûr de N et de m. Si tu es perdu, prends N=9 et m=0 puis m=2, par exemple, pour voir ce qui se passe.

Tu sembles avoir complètement perdu ta boussole dans cet exercice et ne plus pouvoir avancer dans la bonne direction sans qu'on te mâche tout. Peut-être devrais-tu laisser tomber, quitte à y revenir plus tard ?

Posté par
matheux14re : Transformée de Fourier discrète (suite 1) 01-10-23 à 14:15

Bonjour GBZM, si m = 0, je trouve |S|^2 = N^2

Pour m = 2, rien d'intéressant.. si je ne raconte pas n'importe quoi.

Et je n'ai pas vraiment compris pourquoi c'est plus commode de poser k et l comme des entiers modulo N.

Posté par
GBZMre : Transformée de Fourier discrète (suite 1) 01-10-23 à 15:01

matheux14 @ 01-10-2023 à 14:15

si m = 0, je trouve |S|^2 = N^2

Non. D'une part si tu calcules juste la somme pour m=2, tu n'as pas a priori tout S^2, et d'autre part la somme ne vaut pas N^2.
Citation :
Pour m = 2, rien d'intéressant

Mais encore ?
Citation :
je n'ai pas vraiment compris pourquoi c'est plus commode de poser k et l comme des entiers modulo N.

J'endéduis que tu n'as pas sérieusement traité le cas N=9 et m=2.

Posté par
matheux14re : Transformée de Fourier discrète (suite 1) 01-10-23 à 16:12

Pour obtenir la valeur complète de |S|^2, il faut tenir compte de toutes les valeurs possibles de m en utilisant la périodicité de \zeta pour regrouper les termes.

On a \zeta^N = 1, donc \zeta^{m + qN} = \zeta^m, avec q un entier.

Donc pour m = 0, \sum_{\ell=0}^{N-1}\left(\zeta^{m}\right)^{m+2\ell} = \sum_{\ell=0}^{N-1} 1 = N

Peut-être que |S|^2 = \sum_{\ell=0}^{N-1}\left(\zeta^{m}\right)^{m+2\ell}  \neq \sum_{m=0}^{N-1} \sum_{\ell=0}^{N-1} \zeta^{m(m + 2 \ell)} sinon on a bien N^2 pour cette double somme.

Et pour m \neq 0, \sum_{\ell=0}^{N-1}\left(\zeta^{m}\right)^{m+2\ell} = \sum_{\ell=0}^{N-1} \zeta^{m(m+2\ell)} = \zeta^{m^2} \sum_{\ell=0}^{N-1} \zeta^{2m\ell} = \zeta^{m^2} \dfrac{\zeta^{2mN} - 1}{\zeta^{2m} - 1} = 0 car \zeta^{2mN} = 1

Posté par
GBZMre : Transformée de Fourier discrète (suite 1) 01-10-23 à 19:00

Bon, le cas N=9, m=2 est enfin traité correctement.
Pourquoi ne veux-tu pas traiter le cas N=9, m=2 ?
\sum_{\ell=0}^8 (\zeta^2)^{2+2\ell}= {?}
Et après \sum_{m=0}^{8} \sum_{\ell=0}^{8}\zeta^{m(m+2\ell)}={?}

Posté par
matheux14re : Transformée de Fourier discrète (suite 1) 01-10-23 à 19:18

Ben \sum_{\ell=0}^8 (\zeta^2)^{2+2\ell}= 0

Donc [tex]\sum_{m=0}^{8} \sum_{\ell=0}^{8}\zeta^{m(m+2\ell)}= 0[/tex

Posté par
GBZMre : Transformée de Fourier discrète (suite 1) 01-10-23 à 19:27


Ce n'est pas possible !

Posté par
GBZMre : Transformée de Fourier discrète (suite 1) 01-10-23 à 19:29

J'aurais aimé voir les 2+2\ell modulo 9 : 2, 4, 6, 8, 1, 3, 5, 7, 0.

Posté par
GBZMre : Transformée de Fourier discrète (suite 1) 01-10-23 à 19:37

Reprenons : après de multiples erreurs, tu finis par traiter correctement le cas m=0, le cas m=2, et tu trouves le moyen de te tromper pour la somme pour tous les m de 0 à N-1.

Posté par
GBZMre : Transformée de Fourier discrète (suite 1) 01-10-23 à 19:37

à N-1, pardon.

Posté par
matheux14re : Transformée de Fourier discrète (suite 1) 01-10-23 à 20:16

J'ai pas compris.

En poursuivant bien les calculs du cas m = 0, on ne trouvera pas |S| = \sqrt N..

Puisque j'ai juste montré que m = 0, \sum_{\ell=0}^{N-1}\left(\zeta^{m}\right)^{m+2\ell} = \sum_{\ell=0}^{N-1} 1 = N

Pas que |S|^2 = \sum_{m=0}^{N-1} \sum_{\ell=0}^{N-1} \zeta^{m(m + 2 \ell)} = N

GBZM @ 01-10-2023 à 19:27


Ce n'est pas possible !


Si m = 2 \neq 0, alors on a bien 0.

Si vous êtes bien d'accord avec

Citation :
Et pour m \neq 0, \sum_{\ell=0}^{N-1}\left(\zeta^{m}\right)^{m+2\ell} = \sum_{\ell=0}^{N-1} \zeta^{m(m+2\ell)} = \zeta^{m^2} \sum_{\ell=0}^{N-1} \zeta^{2m\ell} = \zeta^{m^2} \dfrac{\zeta^{2mN} - 1}{\zeta^{2m} - 1} = 0 car \zeta^{2mN} = 1
bien sûr.

Citation :
et tu trouves le moyen de te tromper pour la somme pour tous les m de 0 à N-1.


Posté par
GBZMre : Transformée de Fourier discrète (suite 1) 01-10-23 à 20:36

Tu as écrit :

matheux14 @ 01-10-2023 à 19:18


Donc \sum_{m=0}^{8} \sum_{\ell=0}^{8}\zeta^{m(m+2\ell)}= 0
À ton avis, c'est correct ?
Pour le calcul que tu fais, il faut ajouter la précision que \zeta^{2m}\neq 1. Tu vois la raison ?

Posté par
matheux14re : Transformée de Fourier discrète (suite 1) 01-10-23 à 23:31

Bien sûr, je suis d'accord avec \zeta^{2m} \neq 1 mais \zeta^{2mN} = 1.

Posté par
GBZMre : Transformée de Fourier discrète (suite 1) 02-10-23 à 09:29

Tu n'as pas compris ma question. Pourquoi peux-tu affirmer que si 0<m<N alors \zeta^{2m}\neq 1 ?

Posté par
matheux14re : Transformée de Fourier discrète (suite 1) 02-10-23 à 18:13

Parce que N \nmid 2m, N étant impair.

Posté par
GBZMre : Transformée de Fourier discrète (suite 1) 02-10-23 à 18:52

Voila où sert l'imparité de N dans cette question.
Peut-on considérer que |S|=\sqrt{N] est établi ? Il faudrait bien sûr recoller proprement les morceaux.
On peut alors passer à 3). La question commence par "En déduire ...". Il convient donc de faire le lien entre |S| et la quantité qui fait intervenir les multiplicités des valeurs propres.

Posté par
matheux14re : Transformée de Fourier discrète (suite 1) 03-10-23 à 22:52

Bonsoir GBZM

On a montré que \sum_{\ell=0}^{N-1}\left(\zeta^{m}\right)^{m+2\ell} = \sum_{\ell=0}^{N-1} 1 = N pour m = 0.

Et pour m \neq 0, \sum_{\ell=0}^{N-1}\left(\zeta^{m}\right)^{m+2\ell} = 0

Je ne vois pas comment arriver à |S|^2 = \sum_{m=0}^{N-1} \sum_{\ell=0}^{N-1} \zeta^{m(m + 2 \ell)} = N pour m = 0.

3) Pour \alpha \in \C,  m_{\alpha} = \dim(ker(U_n - \alpha I_N)), soit m_{\alpha} représente la multiplicité associé à la valeur propre \alpha.

On a U = \dfrac{1}{\sqrt N} V(1 , \zeta, \zeta^2, \dots, \zeta^{N - 1})

Il me semble donc que le lien entre entre |S| et la quantité qui fait intervenir les multiplicités des valeurs propres est :

\dfrac{|S|}{\sqrt N} = (m_1 - m_{-1})^2 + (m_i - m_{-i})^2 et en utilisant U^2, on a \left(\dfrac{|S|}{\sqrt N}\right)^2 = (m_1 + m_{-1}) - (m_i + m_{-i})  si je ne raconte pas n'importe quoi bien sûr.

Mais aucune idée de comment le montrer.

Est-il possible de relier les multiplicités des valeurs propres à la structure de la matrice V et aussi U ?

Posté par
GBZMre : Transformée de Fourier discrète (suite 1) 04-10-23 à 09:01

Les bras m'en tombent, comme disait la Vénus de Milo.

matheux14 @ 03-10-2023 à 22:52

On a montré que \sum_{\ell=0}^{N-1}\left(\zeta^{m}\right)^{m+2\ell} = \sum_{\ell=0}^{N-1} 1 = N pour m = 0.

Et pour m \neq 0, \sum_{\ell=0}^{N-1}\left(\zeta^{m}\right)^{m+2\ell} = 0

Et tu ne vois pas comment montrer que la somme de ces quantités pour m de 0 à N-1 est égale à N ????

Posté par
matheux14re : Transformée de Fourier discrète (suite 1) 04-10-23 à 09:34

Ah oui, je n'avais pas pensé à celà une seconde, ce n'était pas si évident..

1 2 +


Rechercher
Menu
Espace membre
31 visiteurs
Changer d'île

Vous devez être membre accéder à ce service...

Pas encore inscrit ?

1 compte par personne, multi-compte interdit !

Ou identifiez-vous :

Rester sur la page

Inscription gratuite

Fiches en rapport

parmi 1719 fiches de maths

Désolé, votre version d'Internet Explorer est plus que périmée ! Merci de le mettre à jour ou de télécharger Firefox ou Google Chrome pour utiliser le site. Votre ordinateur vous remerciera !