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

редактировать

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

Содержание

1 Определения
2 Свойства
- 2.1 Преобразование свертки
- 2.2 Формула Планшереля
3 Преобразование Фурье для конечных абелевых групп
4 Связь с теорией представлений
5 Приложения
6 См. Также
7 Ссылки

Определения

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

f ^ (ϱ) = ∑ a ∈ G f (a) ϱ (a). {\ displaystyle {\ widehat {f}} (\ varrho) = \ sum _ {a \ in G} f (a) \ varrho (a).}

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

Для каждого представления $ϱ {\ displaystyle \ varrho \,}$ $\ varrho \,$ из $G {\ displaystyle G \,}$ $G \,$ , $f ^ (ϱ) {\ displaystyle {\ widehat {f}} (\ varrho) \,}$ $\ widehat { f} (\ varrho) \,$ представляет собой матрицу $d ϱ × d ϱ {\ displaystyle d _ {\ varrho} \ times d _ {\ varrho} \,}$ $d _ {\ varrho} \ times d _ {\ varrho} \,$ , где $d ϱ {\ displaystyle d _ {\ varrho} \,}$ $d _ {\ varrho} \,$ - степень $ϱ {\ displaystyle \ varrho \,}$ $\ varrho \,$ .

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

f (a) = 1 | G | Я д ϱ я Тр (ϱ я (а - 1) е ^ (ϱ я)). {\ displaystyle f (a) = {\ frac {1} {| G |}} \ sum _ {i} d _ {\ varrho _ {i}} {\ text {Tr}} \ left (\ varrho _ {i } (a ^ {- 1}) {\ widehat {f}} (\ varrho _ {i}) \ right).}

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

Свойства

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

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

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

(f \ ast g) (a) = \ сумма _ {{b \ in G}} f (ab ^ {{- 1}}) g (b).

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

f ∗ g ^ (ϱ) = f ^ (ϱ) g ^ (ϱ). {\ displaystyle {\ widehat {f \ ast g}} (\ varrho) = {\ hat {f}} (\ varrho) {\ hat {g}} (\ varrho).}

{\ displaystyle {\ widehat {f \ ast g}} (\ varrho) = {\ hat {f}} (\ varrho) {\ шляпа {g}} (\ varrho).}

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

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

∑ a ∈ G f (a - 1) g (a) = 1 | G | ∑ id ϱ я Тр (е ^ (ϱ я) г ^ (ϱ я)), {\ Displaystyle \ сумма _ {а \ в G} е (а ^ {- 1}) г (а) = {\ гидроразрыва { 1} {| G |}} \ sum _ {i} d _ {\ varrho _ {i}} {\ text {Tr}} \ left ({\ hat {f}} (\ varrho _ {i}) {\ шляпа {g}} (\ varrho _ {i}) \ right),}

{\ 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),}

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

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

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

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

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

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

f ^ (χ) = ∑ a ∈ G f (a) χ ¯ (a). {\ displaystyle {\ widehat {f}} (\ chi) = \ sum _ {a \ in G} f (a) {\ bar {\ chi}} (a).}

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

Тогда обратное преобразование Фурье задается как

f (a) = 1 | G | ∑ χ ∈ G ^ f ^ (χ) χ (a). {\ displaystyle f (a) = {\ frac {1} {| G |}} \ sum _ {\ chi \ in {\ widehat {G}}} {\ widehat {f}} (\ chi) \ chi ( a).}

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

Для $G = Z / n {\ displaystyle G = \ mathbb {Z} / n}$ ${\ displaystyle G = \ mathbb {Z} / n}$ , выбор примитива n-го корня из единицы $ζ {\ displaystyle \ zeta}$ $\ zeta$ дает изоморфизм

G → G ^, {\ displaystyle G \ to {\ widehat {G}},}

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

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

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

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

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

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

C [G] ≅ ⨁ i E nd (V i) {\ displaystyle \ mathbb {C} [ G] \ cong \ bigoplus _ {i} \ mathrm {End} (V_ {i})}

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

, заданный как

∑ g ∈ G agg ↦ (∑ ag ρ i (g): V i → 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 \ sum _ {g \ in G } a_ {g} g \ mapsto \ left (\ sum a_ {g} \ rho _ {i} (g): V_ {i} \ to V_ {i} \ right)}

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

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

Приложения

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

См. Также

Ссылки