Fourierova transformace na konečných grupách - Fourier transform on finite groups

Fourierovy transformace

V matematice je Fourierova transformace na konečných grupách zobecněním diskrétní Fourierovy transformace z cyklických na libovolné konečné skupiny .

Definice

Fourierova transformace z funkce při zobrazení z IS ${\ displaystyle f: G \ to \ mathbb {C}}$ ${\ displaystyle \ varrho: G \ to \ mathrm {GL} (d _ {\ varrho}, \ mathbb {C})}$${\ displaystyle G}$

${\ displaystyle {\ widehat {f}} (\ varrho) = \ součet _ {a \ v G} f (a) \ varrho (a).}$

Pro každého zastoupení všech , je matice, kde je stupeň . ${\ displaystyle \ varrho}$${\ displaystyle G}$${\ displaystyle {\ widehat {f}} (\ varrho)}$${\ displaystyle d _ {\ varrho} \ krát d _ {\ varrho}}$${\ displaystyle d _ {\ varrho}}$${\ displaystyle \ varrho}$

Inverzní Fourierova transformace na prvku z je dána ${\ displaystyle a}$${\ displaystyle G}$

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

Vlastnosti

Transformace konvoluce

Konvoluce dvou funkcí je definována jako ${\ displaystyle f, g: G \ to \ mathbb {C}}$

${\ displaystyle (f \ ast g) (a) = \ součet _ {b \ v G} f \! \ vlevo (ab ^ {- 1} \ vpravo) g (b).}$

Fourierova transformace konvoluce v každém zastoupení všech je dán ${\ displaystyle \ varrho}$${\ displaystyle G}$

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

Plancherelův vzorec

U funkcí se uvádí Plancherelův vzorec ${\ displaystyle f, g: G \ to \ mathbb {C}}$

${\ displaystyle \ sum _ {a \ v 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),}$

kde jsou neredukovatelné reprezentace . ${\ displaystyle \ varrho _ {i}}$${\ displaystyle G}$

Fourierova transformace pro konečné abelianské skupiny

Pokud je skupina G konečnou abelianskou skupinou , situace se značně zjednoduší:

• všechny neredukovatelné reprezentace jsou stupně 1, a proto se rovnají neredukovatelným znakům skupiny. Fourierova transformace s maticovou hodnotou se tedy v tomto případě stává skalární. ${\ displaystyle \ varrho _ {i}}$

• Sada nesnížitelných G -representations má přirozenou strukturu skupiny v samo o sobě, které mohou být identifikovány se skupinou ze skupiny homomorfismů od G do . Tato skupina je známá jako Pontryagin Dual z G . ${\ displaystyle {\ widehat {G}}: = \ mathrm {Hom} (G, S ^ {1})}$${\ displaystyle S ^ {1} = \ {z \ v \ mathbb {C}, | z | = 1 \}}$

Fourierova transformace funkce je funkce daná ${\ displaystyle f: G \ to \ mathbb {C}}$${\ displaystyle {\ widehat {f}}: {\ widehat {G}} \ to \ mathbb {C}}$

${\ displaystyle {\ widehat {f}} (\ chi) = \ součet _ {a \ v G} f (a) {\ bar {\ chi}} (a).}$

Inverzní Fourierova transformace je pak dána vztahem

${\ displaystyle f (a) = {\ frac {1} {| G |}} \ součet _ {\ chi \ v {\ widehat {G}}} {\ widehat {f}} (\ chi) \ chi ( A).}$

Pro , výběr z primitivního n -tý kořen jednoty poskytuje izomorfismus ${\ displaystyle G = \ mathbb {Z} / n}$ ${\ displaystyle \ zeta}$

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

dané uživatelem . V literatuře je běžná volba , která vysvětluje vzorec uvedený v článku o diskrétní Fourierově transformaci . Takový izomorfismus však není kanonický, podobně jako situace, kdy konečný trojrozměrný vektorový prostor je izomorfní s jeho dvojím , ale poskytnutí izomorfismu vyžaduje volbu základu. ${\ displaystyle m \ mapsto (r \ mapsto \ zeta ^ {mr})}$${\ displaystyle \ zeta = e ^ {2 \ pi i / n}}$

Vlastnost, která je často užitečná s pravděpodobností, je, že Fourierova transformace rovnoměrného rozdělení je jednoduše , kde 0 je identita skupiny a je Kroneckerova delta . ${\ displaystyle \ delta _ {a, 0}}$${\ displaystyle \ delta _ {i, j}}$

Fourierovu transformaci lze provést také na kosetech skupiny.

Vztah s teorií reprezentace

Existuje přímý vztah mezi Fourierovou transformací na konečných grupách a teorií reprezentace konečných grup . Množina komplexně hodnocený funkce na konečné skupiny, spolu s operacemi sčítání bodové a konvoluce, tvoří kruh, který je přirozeně identifikován s kruhovou skupinu z přes komplexní čísla, . Moduly tohoto prstenu jsou to samé jako reprezentace. Maschke věta znamená, že je polojednoduché kruh , tak podle Artin-Wedderburn teorém se rozkládá jako přímý produkt z matrice kroužků . Fourierova transformace na konečných skupinách výslovně vykazuje tento rozklad, s maticovým prstencem dimenze pro každou neredukovatelnou reprezentaci. Přesněji řečeno, Peter-Weylova věta (pro konečné skupiny) uvádí, že existuje izomorfismus ${\ 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})}$

dána

${\ displaystyle \ sum _ {g \ v G} a_ {g} g \ mapsto \ left (\ sum a_ {g} \ rho _ {i} (g): V_ {i} \ do V_ {i} \ doprava )}$

Na levé straně je skupina algebry z G . Přímý součet je za celou sadu nerovných neredukovatelných G- reprezentací . ${\ displaystyle \ varrho _ {i}: G \ to \ mathrm {GL} (V_ {i})}$

Fourierova transformace pro konečnou skupinu je právě tento izomorfismus. Výše uvedený produktový vzorec odpovídá tvrzení, že tato mapa je prstencovým izomorfismem .

Aplikace

Toto zobecnění diskrétní Fourierovy transformace se používá v numerické analýze . Circulant matice je matice, kde každý sloupec představuje cyklický posun z předchozího. Cirkulační matice lze rychle diagonalizovat pomocí rychlé Fourierovy transformace , což přináší rychlou metodu řešení systémů lineárních rovnic s cirkulačními maticemi. Podobně lze Fourierovu transformaci na libovolných skupinách použít k získání rychlých algoritmů pro matice s jinými symetriemi ( Åhlander & Munthe-Kaas 2005 ). Tyto algoritmy lze použít pro konstrukci numerických metod pro řešení parciálních diferenciálních rovnic, které zachovávají symetrii rovnic ( Munthe-Kaas 2006 ).

Při aplikaci na booleovskou skupinu je Fourierova transformace v této skupině Hadamardova transformace , která se běžně používá v kvantových výpočtech a dalších polích. Shorův algoritmus používá jak Hadamardovu transformaci (aplikací Hadamardovy brány na každý qubit), tak kvantovou Fourierovu transformaci . První z nich považuje qubits za indexované skupinou a druhý je považuje za indexované pro účely Fourierovy transformace na konečných skupinách. ${\ displaystyle (\ mathbb {Z} / 2 \ mathbb {Z}) ^ {n}}$${\ displaystyle (\ mathbb {Z} / 2 \ mathbb {Z}) ^ {n}}$${\ displaystyle \ mathbb {Z} / 2 ^ {n} \ mathbb {Z}}$

Viz také

• Fourierova transformace
• Teorie reprezentace konečných grup
• Teorie znaků

Reference