Преобразование Фурье на конечных группах - Fourier transform on finite groups

Смотрите также: Дискретное преобразование Фурье (общее)

Преобразования Фурье
Непрерывное преобразование Фурье
Ряд Фурье
Дискретное преобразование Фурье
Дискретное преобразование Фурье
Дискретное преобразование Фурье над кольцом
Преобразование Фурье на конечных группах
Анализ Фурье
Связанные преобразования

В математика, то Преобразование Фурье на конечных группах является обобщением дискретное преобразование Фурье из циклический произвольно конечные группы.

Определения

В преобразование Фурье функции ${\displaystyle f:G\rightarrow \mathbb {C} \,}$в представление ${\displaystyle \varrho :G\rightarrow GL(d_{\varrho },\mathbb {C} )\,}$ из ${\displaystyle G\,}$ является

${\displaystyle {\widehat {f}}(\varrho )=\sum _{a\in G}f(a)\varrho (a).}$

Для каждого представления ${\displaystyle \varrho \,}$ из ${\displaystyle G\,}$, ${\displaystyle {\widehat {f}}(\varrho )\,}$ это ${\displaystyle d_{\varrho }\times d_{\varrho }\,}$ матрица, где ${\displaystyle d_{\varrho }\,}$ степень ${\displaystyle \varrho \,}$.

В обратное преобразование Фурье в элементе ${\displaystyle a\,}$ из ${\displaystyle G\,}$ дан кем-то

${\displaystyle f(a)={\frac {1}{|G|}}\sum _{i}d_{\varrho _{i}}{\text{Tr}}\left(\varrho _{i}(a^{-1}){\widehat {f}}(\varrho _{i})\right).}$

Характеристики

Преобразование свертки

В свертка двух функций ${\displaystyle f,g:G\rightarrow \mathbb {C} \,}$ определяется как

${\displaystyle (f\ast g)(a)=\sum _{b\in G}f(ab^{-1})g(b).}$

Преобразование Фурье свертки в любом представлении ${\displaystyle \varrho \,}$ из ${\displaystyle G\,}$ дан кем-то

${\displaystyle {\widehat {f\ast g}}(\varrho )={\hat {f}}(\varrho ){\hat {g}}(\varrho ).}$

Формула планшереля

Для функций ${\displaystyle f,g:G\rightarrow \mathbb {C} \,}$, формула Планшереля утверждает

${\displaystyle \sum _{a\in G}f(a^{-1})g(a)={\frac {1}{|G|}}\sum _{i}d_{\varrho _{i}}{\text{Tr}}\left({\hat {f}}(\varrho _{i}){\hat {g}}(\varrho _{i})\right),}$

куда ${\displaystyle \varrho _{i}\,}$ неприводимые представления ${\displaystyle G.\,}$

Преобразование Фурье для конечных абелевых групп

Если группа грамм конечный абелева группа, ситуация значительно упрощается:

• все неприводимые представления ${\displaystyle \varrho _{i}}$ имеют степень 1 и, следовательно, равны неприводимым характерам группы. Таким образом, матричное преобразование Фурье в этом случае становится скалярным.

• Множество неприводимых грамм-представления имеют самостоятельную естественную групповую структуру, которую можно отождествить с группой ${\displaystyle {\widehat {G}}:=\mathrm {Hom} (G,S^{1})}$ из групповые гомоморфизмы из грамм к ${\displaystyle S^{1}=\{z\in \mathbb {C} ,|z|=1\}}$. Эта группа известна как Понтрягин дуальный из грамм.

Преобразование Фурье функции ${\displaystyle f:G\rightarrow \mathbb {C} }$ это функция ${\displaystyle {\widehat {f}}:{\widehat {G}}\to \mathbb {C} }$ данный

${\displaystyle {\widehat {f}}(\chi )=\sum _{a\in G}f(a){\bar {\chi }}(a).}$

Обратное преобразование Фурье тогда дается выражением

${\displaystyle f(a)={\frac {1}{|G|}}\sum _{\chi \in {\widehat {G}}}{\widehat {f}}(\chi )\chi (a).}$

За ${\displaystyle G=\mathbb {Z} /n}$, выбор примитивного п-й корень единства ${\displaystyle \zeta }$ дает изоморфизм

${\displaystyle G\to {\widehat {G}},}$

данный ${\displaystyle m\mapsto (r\mapsto \zeta ^{mr})}$. В литературе распространенным выбором является ${\displaystyle \zeta =e^{2\pi i/n}}$, который объясняет формулу, приведенную в статье о дискретное преобразование Фурье. Однако такой изоморфизм не является каноническим, как и ситуация, когда конечномерное векторное пространство изоморфно своему двойной, но для изоморфизма необходимо выбрать базис.

Свойство, которое часто полезно для оценки вероятности, заключается в том, что преобразование Фурье равномерного распределения просто ${\displaystyle \delta _{a,0},\,}$ где 0 - тождество группы и ${\displaystyle \delta _{i,j}\,}$ это Дельта Кронекера.

Преобразование Фурье также может выполняться на смежных классах группы.

Связь с теорией представления

Существует прямая связь между преобразованием Фурье на конечных группах и теория представлений конечных групп. Множество комплекснозначных функций на конечной группе, ${\displaystyle G}$вместе с операциями поточечного сложения и свертки образуют кольцо, которое естественным образом отождествляется с групповое кольцо из ${\displaystyle G}$ над комплексными числами, ${\displaystyle \mathbb {C} [G]}$. Модули этого кольца - то же самое, что и изображения. Теорема Машке подразумевает, что ${\displaystyle \mathbb {C} [G]}$ это полупростое кольцо, так что Теорема Артина – Веддерберна он разлагается как прямой продукт из матричные кольца. Преобразование Фурье на конечных группах явно демонстрирует это разложение с кольцом матриц размерности ${\displaystyle d_{\varrho }}$ для каждого неприводимого представления. Теорема Питера-Вейля (для конечных групп) утверждает, что существует изоморфизм

${\displaystyle \mathbb {C} [G]\cong \bigoplus _{i}\mathrm {End} (V_{i})}$

данный

${\displaystyle \sum _{g\in G}a_{g}g\mapsto \left(\sum a_{g}\rho _{i}(g):V_{i}\to V_{i}\right)}$

Левая сторона - это групповая алгебра из грамм. Прямая сумма берется по полному набору неэквивалентных неприводимых грамм-представительства ${\displaystyle \varrho _{i}:G\to \mathrm {GL} (V_{i})}$.

Преобразование Фурье для конечной группы и есть этот изоморфизм. Упомянутая выше формула продукта эквивалентна утверждению, что эта карта является изоморфизм колец.

Приложения

Это обобщение дискретного преобразования Фурье используется в числовой анализ. А циркулянтная матрица матрица, в которой каждый столбец циклический сдвиг предыдущего. Циркулянтные матрицы могут быть диагонализованный быстро используя быстрое преобразование Фурье, и это дает быстрый метод решения системы линейных уравнений с циркулянтными матрицами. Точно так же преобразование Фурье на произвольных группах можно использовать для получения быстрых алгоритмов для матриц с другими симметриями (Аландер и Мунте-Каас 2005 ). Эти алгоритмы могут быть использованы для построения численные методы решения уравнений в частных производных сохраняющие симметрии уравнений (Мунте-Каас 2006 ).

Смотрите также

• преобразование Фурье
• Теория представлений конечных групп
• Теория характера

Рекомендации

• Аландер, Кристер; Мунте-Каас, Ханс З. (2005), "Приложения обобщенного преобразования Фурье в числовой линейной алгебре", КУСОЧЕК, 45 (4): 819–850, CiteSeerX  10.1.1.142.3122, Дои:10.1007 / s10543-005-0030-3, МИСТЕР  2191479.
• Диаконис, Перси (1988), Групповые представления в вероятности и статистике, Конспект лекций - серия монографий, 11, Институт математической статистики, Zbl  0695.60012.
• Диаконис, Перси (1991-12-12), «Конечные методы Фурье: доступ к инструментам» в Боллобаше, Бела; Чунг, Фань Р. К. (ред.), Вероятностная комбинаторика и ее приложения, Труды симпозиумов по прикладной математике, 44, Американское математическое общество, стр. 171–194, ISBN  978-0-8218-6749-5.
• Мунте-Каас, Ханс З. (2006), "О групповом анализе Фурье и сохраняющих симметрию дискретизации УЧП", Журнал физики А, 39 (19): 5563–84, CiteSeerX  10.1.1.329.9959, Дои:10.1088 / 0305-4470 / 39/19 / S14, МИСТЕР  2220776.
• Террас, Одри (1999), Анализ Фурье на конечных группах и приложениях, Cambridge University Press, стр. 251, ISBN  978-0-521-45718-7, Zbl  0928.43001.