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

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

Определения [ править ]

Преобразование Фурье функции в представлении от IS${\ displaystyle f: G \ to \ mathbb {C}}$ ${\ displaystyle \ varrho: G \ to \ mathrm {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\to \mathbb {C} }$

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

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

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

Формула Планшереля [ править ]

Для функций формула Планшереля утверждает${\displaystyle f,g:G\to \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}$

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

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

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

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

Преобразование Фурье функции - это функция, заданная формулой${\displaystyle f:G\to \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}}$

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

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

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

Существует прямая связь между преобразованием Фурье на конечных группах и теорией представлений конечных групп . Набор комплексных функций на конечную группу, вместе с операциями поточечного сложения и сверток, образует кольцо, которое естественным образом идентифицирован с кольцом группы из над комплексными числами, . Модули этого кольца - это то же самое, что и представления. Теорема Машке следует , что это полупростое кольцо , поэтому по артиновской-Wedderburn теорема она разлагается в прямое произведение из матричных колец${\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)}$

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

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

Приложения [ править ]

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

Применительно к булевой группе преобразование Фурье в этой группе является преобразованием Адамара , которое обычно используется в квантовых вычислениях и других областях. Алгоритм Шора использует как преобразование Адамара (применяя вентиль Адамара к каждому кубиту), так и квантовое преобразование Фурье . Первый рассматривает кубиты как проиндексированные группой, а второй считает их проиндексированными с целью преобразования Фурье на конечных группах. ^[1]${\displaystyle (\mathbb {Z} /2\mathbb {Z} )^{n}}$${\displaystyle (\mathbb {Z} /2\mathbb {Z} )^{n}}$${\displaystyle \mathbb {Z} /2^{n}\mathbb {Z} }$

См. Также [ править ]

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

Ссылки [ править ]