1. fejezet Abel-csoportok 1.1. Algoritmikus k´erd´esek Abel-csoportokban A kurzus soran ´ el˝osz¨or az Abel-csoportokkal kapcsolatos algoritmikus k´erd´esekkel foglalkozunk. Abel-csoportokban altal ´ aban ´ addit´ıv jel¨ol´est haszna´ lunk, tehat ´ a csoportmuveletet ˝ a + szimbolum ´ jel¨oli.
1.2. Szabad Abel-csoportok A szabad objektumok fontos szerepet jatszanak ´ az algebraban, ´ hiszen bel˝oluk ¨ faktork´epz´es seg´ıts´eg´evel el˝oall´ ´ ıthato´ az o¨ sszes algebrai struktura. ´ P´eldaul ´ egy tetsz˝oleges csoport fel´ırhato´ egy alkalmas szabad csoport faktorcsoportjak´ent. Az Abel-csoportok csaladj ´ aban ´ a szabad Abel-csoportok jatssz ´ ak ´ ezt a szerepet. ´ 1.2.1 Legyen F egy Abel-csoport, X pedig az F csoport egy r´eszhalDefin´ıcio maza. Az X halmazt szabad generator-rendszernek ´ nevezzuk, ¨ ha hXi = F , ¯ valamint tetsz˝oleges G Abel-csoport e´ s tetsz˝oleges f : X → G lek´epez´es eset´en l´etezik pontosan egy homomorfizmus f : F → G, ugy ´ hogy f |X = f¯. Egy G Abelcsoportot szabad Abel-csoportnak mondunk, ha van neki szabad generator´ rendszere.
1
2
Abel-csoportok
P´elda 1.2.2 Tekintsuk ¨ az eg´esz szamok ´ Z csoportjat ´ az o¨ sszeadasra ´ n´ezve. Nyilvan ´ az X = {1} halmaz generalja ´ a csoportot. Legyen G egy tetsz˝oleges ¯ Abel-csoport, e´ s tekintsunk ¨ egy f : X → G lek´epez´est; tegyuk ¨ fel, hogy f¯(1) = g. Ha l´etezik f : Z → G homomorfizmus melyre f |X = f¯ teljesul, ¨ akkor n ∈ Z eset´en ! f (n) = f
1| + ·{z · · + 1} n-szer
= f (1) + · · · + f (1) = g + · · · + g = ng. {z } | {z } | n-szer
n-szer
Tehat, ´ ha a k´ıvant ´ homomorfizmus l´etezik, akkor az egy´ertelmu. ˝ A l´etez´es igazolas ´ ahoz ´ meg kell mutatni, hogy a fenti f lek´epez´es homomorfizmus. Mivel, ng + mg = (n + m)g, ´ıgy f (n + m) = (n + m)g = ng + mg = f (n) + f (m). Tehat ´ f egy homomorfizmus, tovabb ´ a´ f (1) = 1g = g = f¯(g). Mivel f valaszt ´ asa ´ tetsz˝oleges volt, X egy szabad generator-rendszer, ´ a Z csoport pedig szabad csoport. P´elda 1.2.3 Legyen Z2 = {02 , 12 }, a 2-vel valo´ osztas ´ marad´ekainak k´etelemu ˝ ´ ıtjuk, hogy az csoportja. Ennek generator-rendszere ´ az X = {12 } halmaz. All´ X halmaz nem szabad generator-rendszer. ´ Legyen p´eldaul ´ Z3 = {03 , 13 , 23 } a haromelem ´ u ˝ marad´ekosztaly ´ csoport, e´ s legyen f¯ : 12 7→ 13 . Ha f a f¯ egy kiterjeszt´ese, akkor f (02 ) = 03 kell, hogy teljesulj¨ ¨ on. Viszont, f (02 ) = f (12 + 12 ) = f (12 ) + f (12 ) = 13 + 13 = 23 . Tehat ´ X nem szabad generator-rendszer. ´ Hasonlo´ gondolatmenet mutatja, hogy Z2 -ben nincs szabad generator-rendszer, ´ ´ıgy az nem szabad Abel-csoport. Lemma 1.2.4 Legyen F egy Abel-csoport es ´ legyenek X, Y szabad generator´ rendszerek F -ben. Ekkor |X| = |Y |. ´ . Jel¨olje Z2 a k´etelemu B IZONY´I T AS ˝ Abel-csoportot. A szabad generator´ rendszerek defin´ıcioja ´ szerint az f : F → Z2 homomorfizmusok szama ´ megegyezik az X → Z2 , illetve az Y → Z2 lek´epez´esek szam ´ aval. ´ Ezek szama ´ 2|X| , illetve 2|Y | . ´Igy, |X| = |Y |. 2 Jegyzet friss´ ıtve:
2006. december 12.
´ Csoportelmeleti algoritmusok
3
Egy szabad Abel-csoportban, a szabad generator-rendszerek ´ szamoss ´ ag ´ at ´ a csoport rangjanak ´ mondjuk. A 1.2.4 lemma szerint a rang egy jol ´ definialt ´ fogalom. Az 1.2.2 p´eldaban ´ szerepl˝o csoport rangja 1. Az 1.2.3 p´elda gondolatmenet´et hasznalva ´ nem neh´ez latni, ´ hogy v´eges Abel-csoportok nem lehetnek szabadok. Valoj ´ aban ´ a v´egesen generalt ´ szabad Abel-csoportok egyszeruen ˝ meghatarozhat ´ ok, ´ a k¨ovetkez˝ok´eppen. Jol ´ ismert, hogy az eg´esz szamok ´ Z halmaza Abel-csoportot alkot az o¨ sszeadasra ´ n´ezve. Tekinthetjuk ¨ ennek a csoportnak az o¨ nmagaval ´ vett k-szoros Descartes szork zatat, ´ a Z = Z ⊕ · · · ⊕ Z csoportot. Ennek a csoportnak az elemei rendezett k-asok (a1 , . . . , ak ) ahol az ai elemek eg´eszek. Az (a1 , . . . , ak ) e´ s a (b1 , . . . , bk ) elemek o¨ sszege (a1 + b1 , . . . , ak + bk ). Ennek a csoportnak a z´ero-eleme ´ a (0, . . . , 0) elem, az (a1 , . . . , ak ) elem inverze pedig a (−a1 , . . . , −ak ). A csoportok direkt szorzatanak ´ defin´ıcioja ´ miatt, k´et csoportbeli elem (a1 , . . . , ak ) e´ s (b1 , . . . , bk ) akkor e´ s csakis akkor egyenl˝o, ha ai = bi teljesul ¨ minden i-re. T´etel 1.2.5 Legyen F egy Abel-csoport es ´ legyen X egy veges ´ szabad gek nerator-rendszer ´ X-ben. Ekkor F izomorf a Z csoporttal, ahol k = |X|. ´ . Legyen i ∈ {1, . . . , k} e´ s jel¨olje ei a Zk csoportnak azt az elem´et B IZONY´I T AS amelynek minden koordinat ´ aja ´ 0, kiv´eve az i-dik koordinat ´ at, ´ ami 1. Legyenek x1 , . . . , xk az X elemei, e´ s legyen f¯ : xi 7→ ei . Mivel X szabad generator´ ´ ıtjuk, hogy rendszer, a f¯ lek´epez´es kiterjeszthet˝o egy f homomorfizmussa. ´ All´ f egy bijekcio. ´ Mivel az {e1 , . . . , ek } halmaz generalja ´ a Zk csoportot e´ s benne van az f k´ep´eben, f szurjekt´ ¨ ıv. Tegyuk ¨ fel, hogy α1 , . . . , αk ∈ Z eset´en az x = α1 x1 + · · · + αk xk elem benne van, az f magjaban. ´ Ekkor (0, . . . , 0) = f (x) = f (α1 x1 + · · · + αk xk ) = α1 f (x1 ) + · · · + αk f (xk )
= α1 e1 + · · · + αk ek = (α1 , . . . , αk ).
Tehat ´ α1 = · · · = αk = 0 e´ s ´ıgy x = 0. Ez´ert, ker f = 0, ami azt jelenti, hogy f injekt´ıv. Tehat ´ f valoban ´ bijekcio. ´ 2 K¨ ovetkezm´eny 1.2.6 A fenti {e1 , . . . , ek } halmaz szabad generator-rendszere ´ a k k Z csoportnak, ´ıgy a Z csoport szabad Abel-csoport, melynek rangja k. Jegyzet friss´ ıtve:
2006. december 12.
4
Abel-csoportok
´ . Tovabbra B IZONY´I T AS ´ is hasznaljuk ´ az el˝oz˝o bizony´ıtas ´ jel¨ol´eseit, e´ s legyen Y = {e1 , . . . , ek }. Tegyuk ¨ fel, hogy G egy tetsz˝oleges Abel-csoport, e´ s legyen g¯ : Y → G egy tetsz˝oleges lek´epez´es. Mivel X = {x1 , . . . , xk } szabad generator´ ¯ : xi 7→ g¯(ei ) lek´epez´es rendszere az el˝oz˝o t´etelben szerepl˝o F csoportnak, a h kiterjeszthet˝o egy h : F → G homomorfizmussa. ´ Definialjuk ´ az g lek´epez´est k −1 a k¨ovetkez˝ok´eppen: ha x ∈ Z , akkor legyen g(x) = h(f (x)), ahol f az el˝oz˝o bizony´ıtasban ´ definialt ´ izomorfizmus. Mivel, az f e´ s a h homomorfizmus, a g lek´epez´es is az. Tovabb ´ a, ´ g(ei ) = h(f −1 (ei )) = h(xi ) = g¯(ei ). Ez´ert g kiterjeszt´ese a g¯ lek´epez´esnek e´ s ´ıgy a k´ıvant ´ lek´epez´es l´etezik. Tegyuk ¨ k fel, hogy g1 , g2 : Z → G homomorfizmusok melyek kiterjesztik a g¯ lek´epez´est. Ekkor az f g1 , f g2 lek´epez´esek kiterjesztik a xi 7→ g(ei) lek´epez´est. Mivel X szabad generator-rendszer, ´ f g1 = f g2 , azaz g1 = g2 . Tehat ´ a g¯ lek´epez´es kiterjeszt´ese egy´ertelmu, ˝ a {e1 , . . . , ek } halmaz szabad generator-rendszer, ´ az Zk pedig szabad csoport. 2 Term´eszetesen a Zk csoportnak sok mas ´ szabad generator-rendszere ´ is k ´ van. Altal aban ´ a Z szabad generator-rendszereit ´ bazisoknak ´ mondjuk, az {e1 , . . . , ek } rendszert pedig standard bazisnak ´ nevezzuk. ¨ K¨ ovetkezm´eny 1.2.7 Egy k elem altal ´ generalt ´ Abel-csoport elo˝ all ´ mint a Zk csoport faktorcsoportja. ´ . Legyen X = {x1 , . . . , xk } egy k elemu B IZONY´I T AS ˝ generator-rendszere ´ a G csok portnak, e´ s definialjuk ´ az f : Z → G homomorfizmust a ei 7→ xi lek´epez´es kiterjeszt´esek´ent. Mivel X generalja ´ a G csoportot, f szurjekt´ ¨ ıv, e´ s ´ıgy, a hok momorfizmus t´etel szerint, G ∼ = Z /(ker f ). 2 P´elda 1.2.8 Legyen G = Z3 ⊕ Z5 = hai ⊕ hbi. Legyen f : Zk → G az e1 7→ a, e2 7→ b lek´epez´es kiterjeszt´ese. Ekkor f (α1 , α2 ) = α1 a + α2 b, azaz f (α1 , α2 ) = 0, akkor e´ s csakis akkor, ha 3|α1 e´ s 5|α2 . Tehat ´ ker f = {(α3, β5) | α, β ∈ Z} = h(3, 0), (0, 5)i . 2 ´Igy G ∼ = Z / h(3, 0), (0, 5)i.
Jegyzet friss´ ıtve:
2006. december 12.
´ Csoportelmeleti algoritmusok
5
A szabad generator-rendszer ´ defin´ıcioja ´ nem teszi lehet˝ov´e, hogy egyszeruen ˝ ellen˝orizzuk, ¨ hogy egy szabad Abel-csoportbeli halmaz szabad generator-rendszer-e. ´ A k¨ovetkez˝o lemma, egy k¨onnyebben kezelhet˝o szuks´ ¨ eges e´ s elegend˝o felt´etelt ad. Lemma 1.2.9 Legyen F egy Abel-csoport, es ´ legyen X = {x1 , . . . , xk } egy veges ´ reszhalmaza ´ F -nek. Ekkor X szabad generator-rendszer ´ akkor es ´ csakis akkor, ha F minden eleme pontosan egyfelek ´ eppen ´ ´ırhato´ α1 , . . . , αk egesz ´ szamok ´ seg´ıtseg ´ evel ´ α1 x1 + · · · + αk xk alakban. ´ . Tegyuk B IZONY´I T AS ¨ fel el˝osz¨or, hogy X egy szabad generator-rendszer. ´ Ebben az esetben az F minden eleme fel´ırhato´ α1 x1 + · · · + αk xk alakban. Legyen f : F → Zk a 1.2.5 t´etelben definialt ´ izomorfizmus. Tegyuk ¨ fel, hogy α1 , . . . , αk e´ s β1 , . . . , βk eg´esz szamok ´ ugy ´ hogy α1 x1 + · · · + αk xk = β1 x1 + · · · + βk xk . Mivel f izomorfizmus, (α1 , . . . , αk ) = f (α1 x1 + · · · + αk xk ) = f (β1 x1 + · · · + βk xk ) = (β1 , . . . , βk ). Amib˝ol α1 = β1 , . . . , αk = βk k¨ovetkezik. Tehat ´ az α1 x1 + · · · + αk xk elem fel´ırasa ´ egy´ertelmu. ˝ Tegyuk ¨ most fel, hogy X rendelkezik a t´etelben megk¨ovetelt tulajdonsaggal. ´ Legyen G egy Abel-csoport, e´ s legyen g¯ : X → G egy lek´epez´es. Definialjuk ´ az k f : F → Z lek´epez´est: f (α1 x1 + · · · + αk xk ) = (α1 , . . . , αk ). A felt´etel szerint, f jol-defini ´ alt, ´ e´ s egyszeru ˝ szamol ´ as ´ mutatja, hogy f homomorfizmus. Mivel f (xi ) = ei , a standard bazis ´ elemek benne vannak az f k´ep´eben, ´ıgy f szurjekt´ ¨ ıv. Ha f (α1 x1 + · · · + αk xk ) = (0, . . . , 0), akkor az f defin´ıcioja ´ miatt, α1 = · · · = αk = 0, azaz α1 x1 + · · · + αk xk = 0. Tehat, ´ ker f = 0, e´ s ´ıgy f egy izomorfizmus. Tekintsuk ¨ az ei standard bazis ´ elemeket Zk -ban e´ s legyen Y = {e1 , . . . , ek }. ¯ : Y → G azt a lek´epez´est melyre h(e ¯ i ) = g¯(xi ). Ekkor a h ¯ kiterjesztJel¨olje h k het˝o egy h : Z → G homomorfizmussa, ´ e´ s definialhatjuk ´ a g lek´epez´est a k¨ovetkez˝ok´eppen: x ∈ F eset´en legyen g(x) = h(f (x)). Mivel h e´ s f homomorfizmusok, a g is az, tovabb ´ a´ g|X = g¯. Ha g1 , g2 : F → G melyekre g1 |X = g2 |X = g¯, −1 −1 akkor g1 f e´ s g2 f olyan lek´epez´esek, melyekre g1 f −1 |Y = g2 f −1 |Y . Mivel Y szabad generator-rendszer, ´ g1 f −1 = g2 f −1 k¨ovetkezik, tehat ´ g1 = g2 . 2 Jegyzet friss´ ıtve:
2006. december 12.
6
Abel-csoportok
1.3. Szabad Abel-csoportok r´eszcsoportjai Egy szabad Abel-csoport minden r´eszcsoportja is szabad Abel-csoport. Mi ezt az eredm´enyt csak v´egesen generalt ´ szabad Abel-csoportok eset´en bizony´ıtjuk. T´etel 1.3.1 Egy k rangu´ szabad Abel-csoport tetszoleges ˝ reszcsoportja ´ is egy legfeljebb k rangu´ szabad Abel-csoport. ´ . A 1.2.5 t´etel miatt, elegend˝o belatni, B IZONY´I T AS ´ hogy az F = Zk csoport tetsz˝oleges H r´eszcsoportja szabad Abel-csoport melynek rangja legfeljebb k. Legyen i ∈ {0, . . . , k} e´ s jel¨olje Fi azon k-asok halmazat, ´ amelyekben az els˝o i koordinata ´ 0. Ezzel definialtuk ´ k¨ovetkez˝o F -beli r´eszcsoportlancot: ´ F = F0 > F1 > · · · > Fk−1 > Fk = 0; tovabb ´ a´ i ∈ {0, . . . , k − 1} eset´en Fi /Fi+1 ∼ = Z. Legyen Hi = H ∩ Fi . Ekkor, ha i ∈ {0, . . . , k − 1}, akkor Hi H ∩ Fi H ∩ Fi (H ∩ Fi ) + Fi+1 ∼ = = , = Hi+1 H ∩ Fi+1 H ∩ Fi ∩ Fi+1 Fi+1
e´ s ez´ert Hi /Hi+1 izomorf a Fi /Fi+1 ∼ ´ A Z egy = Z csoport egy r´eszcsoportjaval. r´eszcsoportja vagy trivialis, ´ vagy pedig izomorf Z-vel, ez´ert vagy Hi /Hi+1 = 0 vagy Hi /Hi+1 ∼ = Z. A fentiek szerint a H csoportban definialtunk ´ egy H0 = H > H1 > · · · > Hk−1 > Hk = 0 r´eszcsoportlancot ´ amelynek faktorai vagy trivialisak ´ vagy pedig izomorfak a Z csoporttal. A lancb ´ ol ´ hagyjuk el az ism´etl˝od´eseket, e´ s alkossunk egy H0 = H > H1 > · · · > Hm−1 > Hm = 0 r´eszcsoportlancot ´ amelyben minden faktor izomorf a Z csoporttal. Jegyezzuk ¨ itt meg, hogy m 6 k. Valasszunk, ´ i ∈ {1, . . . , m} eset´en, egy ai ∈ Hi−1 elemet ugy, ´ hogy hai + Hi i = Hi−1 /Hi . Ilyen elem l´etezik, hiszen Hi−1 /Hi egy ciklikus csoport. Mivel Hi−1 /Hi ∼ = Z, Hi−1 /Hi = {k(ai + Hi ) | k ∈ Z} = {kai + Hi | k ∈ Z}, Jegyzet friss´ ıtve:
2006. december 12.
´ Csoportelmeleti algoritmusok
7
tovabb ´ a´ k1 ai + Hi = k2 ai + Hi akkor e´ s csakis akkor, ha k1 = k2 . Legyen x ∈ Hi−1 . Az x elem a Hi r´eszcsoport pontosan egy mell´ekosztaly ´ aban ´ talalhat ´ o, ´ ez´ert egy´eretelmuen ˝ l´eteznek k ∈ Z e´ s y ∈ Hi melyekkel x = kai + y teljesul. ¨ Azt all´ ´ ıtjuk, hogy a {a1 , . . . , am } halmaz szabad generator-rendszer ´ a H csoportban. Legyen x ∈ H. Az el˝oz˝o bekezd´es all´ ´ ıtasa ´ szerint l´etezik pontosan egy α1 ∈ Z e´ s pontosan egy y1 ∈ H1 ugy ´ hogy x = α1 a1 + y1 . Hasonloan, ´ l´etezik pontosan egy α2 ∈ Z e´ s pontosan egy y2 ∈ H2 ugy ´ hogy y1 = α2 a2 + y2 , e´ s ´ıgy y = α1 a1 +α2 a2 +y2 . Ezt a sort folytatva, azt talaljuk, ´ hogy egy´ertelmuen ˝ l´eteznek α1 , . . . , αm ∈ Z amelyek kiel´eg´ıtik az y = α1 a1 + · · · + αm am egyenletet. Az 1.2.9 lemma szerint a {a1 , . . . , am } halmaz szabad generator-rendszer ´ a H csoportban, e´ s ´ıgy a H csoport szabad Abel-csoport. Tovabb ´ a´ a H csoport rangja m, ami nem nagyobb mint k. 2
1.4. Sormuveletek ˝ eg´esz m´atrixokkal Jel¨olje Mm,k (Z) az m sorbol ´ e´ s k oszlopbol ´ all ´ o´ Z feletti matrixok ´ halmazat. ´ A Zk csoport egy G r´eszcsoportjat ´ megadhatjuk egy A ∈ Mm,k (Z) matrix ´ seg´ıts´eg´evel, melynek a sorai generaljak ´ a G csoportot. Szimbolumokkal ´ ezt a t´enyt ugy ´ fejezzuk ¨ ki, hogy G = hAi. A fenti 1.3.1 t´etel szerint, feltehetjuk, ¨ hogy m 6 k. Vilagos, ´ hogy az hAi csoport megegyezik az A matrix ´ soraibol ´ all ´ o´ eg´esz egyutthat ¨ os ´ linearis ´ kombinaci ´ ok ´ a halmazaval. ´ Ebben a szakaszban olyan modszereket ´ ismertetunk, ¨ amik az alabbi ´ k´erd´esekre valaszt ´ adnak: (i) Ha A ∈ Mm,k (Z) e´ s B ∈ Mn,k (Z), akkor vajon igaz-e, hogy hAi = hBi. k (ii) Ha A e´ s B a fenti matrixok, ´ akkor igaz-e, hogy Zk / hAi ∼ = Z / hBi.
(iii) Ha A ∈ Mm,k (Z) e´ s a ∈ Zk , akkor vajon igaz-e, hogy a ∈ hAi. A Mm,k (Z)-beli matrixok ´ k¨or´eben a k¨ovetkez˝o muveleteket ˝ elemi (egesz) ´ sormuveleteknek ˝ nevezzuk: ¨ (i) k´et sor felcser´el´ese; (ii) egy sor szorzasa ´ −1-gyel; Jegyzet friss´ ıtve:
2006. december 12.
8
Abel-csoportok
(iii) egy sor valamely eg´esz t¨obbsz¨or¨os´enek hozzaad ´ asa ´ egy masik ´ sorhoz. P´elda 1.4.1 Tekintsuk ¨ az alabbi ´ matrixot ´ 1 −1 3 0 2 0 4 . −2 3 1 −3 0 Az els˝o e´ s a harmadik sor felcser´el´ese utan ´ 3 1 −3 2 0 −2 1 −1 3
a 0 4 . 0
matrixot ´ kapjuk. Szorozzuk meg a masodik ´ sort −1-gyel: 3 1 −3 0 0 −4 . 2 −2 1 −1 3 0
V´egul ¨ pedig adjuk a masodik ´ sor −2-szeres´et a harmadik sorhoz: 3 1 −3 0 0 −4 . 2 −2 −3 3 3 8
Ha A, B ∈ Mm,k (Z), akkor az A e´ s B matrixokat ´ sor-ekvivalensnek mondjuk, ha a B megkaphato´ az A-bol ´ sormuveletek ˝ seg´ıts´eg´evel. Lemma 1.4.2 A sor-ekvivalencia egy ekvivalencia relaci ´ o´ az Mm,k (Z) halmazon. Tovabb ´ a, ´ ha A es ´ B sor-ekvivalens matrixok, ´ akkor hAi = hBi. ´ . Vilagos, B IZONY´I T AS ´ hogy a relaci ´ o´ reflex´ıv, mert az A matrixb ´ ol ´ o¨ nmagat ´ kapjuk, ha p´eldaul ´ egy sorat ´ k´etszer megszorozzuk −1-gyel. A relaci ´ o´ nyilvan ´ tranzit´ıv is, mert ha az A matrixb ´ ol ´ megkaphato´ a B, a B-b˝ol pedig a C sormuveletek ˝ seg´ıts´eg´evel, akkor ezeket a sormuveleteket ˝ egymas ´ utan ´ elv´egezve az A matrixb ´ ol ´ a C-t nyerjuk. ¨ Az ekvivalencia relaci ´ o´ igazolas ´ ahoz ´ tehat ´ csak a szimmetriat ´ kell belatni. ´ El˝osz¨or megmutatjuk, hogy a fenti Jegyzet friss´ ıtve:
2006. december 12.
´ Csoportelmeleti algoritmusok
9
sormuveletek ˝ megford´ıthatoak, ´ azaz ha B megkaphato´ A-bol ´ egyetlen sormuvelet ˝ seg´ıts´eg´evel, akkor A is megkaphato´ B-b˝ol szint´en egyetlen sormuve˝ let seg´ıts´eg´evel. Az all´ ´ ıtas ´ nyilvanval ´ o, ´ ha a sormuvelet ˝ k´et sor felcser´el´ese, vagy pedig egy sor −1-gyel valo´ szorzasa. ´ Ha a B-t ugy ´ kaptuk, hogy az A matrix ´ i-dik sorahoz ´ hozzaadtuk ´ a j-dik sor α-szorosat, ´ (i 6= j) akkor a B-b˝ol visszanyerjuk ¨ az A-t, ha a B matrix ´ i-dik sorahoz ´ hozzaadjuk ´ az jdik sor −α-szorosat. ´ Tehat ´ ha most feltesszuk, ¨ hogy A e´ s B sor-ekvivalens matrixok, ´ akkor a B matrix ´ megkaphato´ az A-bol ´ elemi sormuveletek ˝ egy sorozatat ´ v´egrehajtva. A fenti okoskodas ´ miatt, ha most a B-b˝ol indulunk ki, e´ s a sormuveletek ˝ ellentettj´et hajtjuk v´egre ford´ıtott sorrendben, akkor visszakapjuk az A matrixot. ´ Tehat ´ a relaci ´ o´ szimmetrikus. A masodik ´ all´ ´ ıtas ´ bizony´ıtas ´ ahoz ´ el˝osz¨or belatjuk, ´ hogy ha a B matrix ´ megkaphato´ az A matrixb ´ ol ´ egy sormuvelet ˝ seg´ıts´eg´evel, akkor hBi 6 hAi. Az all´ ´ ıtas ´ nyilvanval ´ o, ´ ha a sormuvelet ˝ k´et sor felcser´el´ese vagy pedig egy sor −1-gyel valo´ szorzasa. ´ Tegyuk ¨ fel, hogy B-t ugy ´ kaptuk, hogy az A matrix ´ i-dik sorahoz ´ hozzaadtuk ´ a j-dik sor α-szorosat. ´ Ekkor az i-dik sor kiv´etel´evel, a B matrix ´ minden sora szerepel az A matrixban ´ is. Ezek a sorok tehat ´ benne vannak az hAi r´eszcsoportban. A B matrix ´ i-dik sora fel´ırhato´ ai + αaj alakban, ahol ai e´ s aj jel¨oli az A matrix ´ i-dik e´ s j-dik sorat. ´ Ebb˝ol a fel´ırasb ´ ol ´ latszik, ´ hogy ez a sor is benne van az A sorai altal ´ generalt ´ hAi r´eszcsoportban, tehat ´ valoban ´ hBi 6 hAi. Ha most feltesszuk, ¨ hogy B megkaphato´ az A-bol ´ egyetlen sormuvelet ˝ seg´ıts´eg´evel, akkor az el˝oz˝o bekezd´esben bizony´ıtottak miatt, hBi 6 hAi. Ekkor azonban A is megkaphato´ az B matrixb ´ ol ´ egy hasonlo´ sormuvelet ˝ seg´ıts´eg´evel, ´ıgy hAi 6 hBi. Tehat ´ hAi = hBi k¨ovetkezik. V´egul, ¨ ha A e´ s B ekvivalens matrixok, ´ akkor B megkaphato´ az A-bol ´ sormuveletek ˝ egy sorozatanak ´ seg´ıts´eg´evel. Ezek a sormuveletek ˝ azonban ´ nem valtoztatj ´ ak ´ meg a sorok altal ´ generalt ´ r´eszcsoportot. Igy hAi = hBi teljesul. ¨ 2
A 1.4.1 p´eldaban ´ szerepl˝o n´egy matrix ´ egymassal ´ paronk´ ´ ent sor-ekvivalens. Jegyzet friss´ ıtve:
2006. december 12.
10
Abel-csoportok
1.5. A Hermite norm´al forma Az el˝oz˝o fejezetben lattuk, ´ hogy az elemi sormuveletek ˝ nem valtoztatnak ´ egy Mm,k (Z)-beli matrix ´ sorai altal ´ generalt ´ r´eszcsoporton. ´Igy ha A ∈ Mm,k (Z), akkor elemi sormuveletek ˝ seg´ıts´eg´evel szeretn´enk egy sz´ep” B ∈ Mm,k (Z) ” matrixot ´ kapni melyre hAi = hBi teljesul. ¨ Lassunk ´ erre egy p´eldat. ´ P´elda 1.5.1 Legyen A a k¨ovetkez˝o matrix: ´
−1 −2 −1 −2 2 0 2 0 −1 −3 1 −2 −3 2 2 3 1 2 −3 2 3 3 −2 2 −1
.
Az els˝o sor megfelel˝o skalarszorosait ´ hozzaadva ´ a t¨obbi sorhoz, el´erhetjuk, ¨ hogy az els˝o oszlopban csak az els˝o sorbeli elem nem-nulla:
−1 0 0 0 0
−2 2 −4 −5 −3
−1 0 −4 −1 −5
−2 2 −1 −3 0 4 . −9 8 −4 5
Vegyuk ¨ az els˝o sor ellentettj´et, hogy vez´ereleme (a sorbeli els˝o nem-nulla elem) pozit´ıv legyen: 1 2 1 2 −2 0 2 0 −1 −3 0 −4 −4 0 4 . 8 0 −5 −1 −9 0 −3 −5 −4 5 A masodik ´ sor megfelel˝o skalarszorosait ´ hozzaadva ´ a t¨obbi sorhoz, cs¨okkenthetjuk ¨ a masodik ´ oszlopban, a masodik ´ sortol ´ lefel´e l´ev˝o elemek abszolut ´ Jegyzet friss´ ıtve:
2006. december 12.
´ Csoportelmeleti algoritmusok e´ rt´ek´et:
11
1 0 0 0 0
2 1 2 −2 2 0 −1 −3 0 −4 −2 −2 1 −1 −12 −1 1 −5 −6 −1
A negyedik sort hasznalva, ´ lenullazhatjuk ´ a dik, e´ s o¨ t¨odik soraban ´ l´ev˝o elemeit: 1 2 1 2 0 0 2 23 0 0 −4 −2 0 1 −1 −12 0 0 −4 6 Cser´eljuk ¨ fel masodik ´ e´ s negyedik 1 2 0 1 0 0 0 0 0 0
.
masodik ´ oszlop masodik, ´ harma-
−2 −1 −2 −1 0
.
sorokat: 1 2 −2 −1 −12 −1 −4 −2 −2 . 2 23 −1 −4 6 0
A masodik ´ sor −2-szeres´et az els˝o sorhoz adva el´erjuk, ¨ hogy a masodik ´ sor vez´ereleme felett az els˝o sorban 0 legyen: 1 0 3 26 0 0 1 −1 −12 −1 0 0 −4 −2 −2 . 2 23 −1 0 0 0 0 −4 6 0 A fenti eljar ´ ashoz ´ hasonloan, ´ a negyedik sor seg´ıts´eg´evel lenullazzuk ´ a harmadik oszlop harmadik e´ s o¨ t¨odik soraban ´ l´ev˝o elemeit, felcser´eljuk ¨ a negyedik e´ s a harmadik sorokat, majd gondoskodunk rola, ´ hogy a harmadik sor vez´ereleme felett csak a vez´erelemn´el kisebb abszolut ´ e´ rt´eku ˝ elemek legyenek. Jegyzet friss´ ıtve:
2006. december 12.
12
Abel-csoportok
´Igy a k¨ovetkez˝o matrixot ´ kapjuk:
1 0 0 0 0
0 1 0 0 0
1 1 2 0 0
3 11 23 44 52
1 −2 −1 −4 −2
.
A negyedik e´ s o¨ t¨odik sorokat addig adogatjuk egymashoz, ´ vagy vonogatjuk egymasb ´ ol, ´ m´ıg az egyikben a negyedik oszlopban l´ev˝o elem 0 lesz. Aztan ´ sorcser´evel el´erjuk, ¨ hogy a negyedik sorban e´ s negyedik oszlopban l´ev˝o elem nem-nulla, majd a negyedik sor vez´ereleme feletti elemeket redukaljuk: ´
1 0 0 0 0
0 1 0 0 0
1 1 2 0 0
3 1 3 26 3 69 4 −14 0 30
.
V´egul ¨ az o¨ t¨odik sor seg´ıts´eg´evel redukaljuk ´ az o¨ t¨odik oszlopban l´ev˝o elemeket:
1 0 0 0 0
0 1 0 0 0
1 1 2 0 0
3 1 3 26 3 9 . 4 16 0 30
Az eljar ´ as ´ v´egeredm´enye egy fels˝o haromsz¨ ´ og matrix, ´ melyben a vez´erelemek nem-negat´ıvak, illetve a vez´erelemek felett t˝olik kisebb abszolut ´ e´ rt´eku ˝ nemnegat´ıv szamok ´ vannak. ´ 1.5.2 Azt mondjuk, hogy egy A ∈ Mm,k (Z) matrix Defin´ıcio ´ Hermite normal ´ formaban ´ (HNF) van ha a k¨ovetkez˝ok teljesulnek: ¨ (i) Valamely r-re az els˝o r sor nem-nulla, az utolso´ m − r sor pedig nulla. Azaz a nulla sorok a matrix ´ aljan ´ talalhat ´ ok. ´ Jegyzet friss´ ıtve:
2006. december 12.
´ Csoportelmeleti algoritmusok
13
(ii) Ha i 6 r e´ s Ai,ji az i-dik sor els˝o nem-nulla eleme, akkor j1 < j2 < · · · < jr . Azaz, a nem-nulla sorok vezerelemei ´ (a sorban l´ev˝o els˝o nem-nulla elem) egyre beljebb talalhat ´ ok, ´ e´ s ´ıgy a matrix ´ fels˝o haromsz¨ ´ og alaku. ´ (iii) Ha i 6 r, akkor Ai,ji > 0. Azaz a nem-nulla sorok vez´ereleme pozit´ıv. (iv) Ha k < i 6 r akkor 0 6 Ak,ji < Ai,ji . Azaz, a egy nem-nulla sor vez´ereleme felett kisebb, nem-negat´ıv elemek talalhat ´ ok. ´ Az 1.5.1 p´eldaban ´ az szamol ´ as ´ v´eg´en kapott matrix ´ HNF alaku. ´ A p´elda jol ´ szeml´elteti, azt az eljar ´ ast, ´ amivel barmely ´ eg´esz e´ rt´eku ˝ matrix ´ HNF alakra hozhato. ´ Az eljar ´ as ´ egy le´ıras ´ at ´ adja a HNF algoritmus, mely egy tetsz˝oleges matrixot ´ Hermite normal ´ formaj ´ uv ´ a´ konvertal. ´ Az algoritmus le´ıras ´ aban ´ Mi jel¨oli az M matrix ´ i-dik sorat, ´ Mi,j pedig az i-dik sor j-dik elem´et. Ha a, b ∈ Z, akkor egy´ertelmuen ˝ l´eteznek q e´ s r eg´esz szamok ´ melyekre a = qb + r e´ s 0 6 r < |b| (euklideszi osztas) ´ e´ s a div b jel¨oli az osztas ´ q hanyados ´ at. ´ Sajnos a HNF algoritmus nem tuls ´ agosan ´ hat´ekony. Tekintsuk ¨ p´eldaul ´ az alabbi ´ matrixot: ´ 5 −1 1 −1 4 −2 −4 −3 3 1 −1 1 −3 4 −2 . 2 −3 −3 −4 −4 −2 −1 −5 −1 4 Ennek HNF alakja az algoritmus hato: ´ 1 0 0 0 0
GAP implementaci ´ oja ´ seg´ıts´eg´evel megkap0 1 0 0 0
0 0 1 0 0
0 210 0 92 0 446 1 1400 0 2073
M´ıg az input matrix ´ elemei viszonylag kicsik (legfeljebb 5 abszolut ´ e´ rt´ekuek), ˝ e´ s az eredm´eny maximalis ´ abszolut ´ e´ rt´eku ˝ eleme is 2073, addig a k¨ozbuls˝ ¨ o matrixokban ´ el˝ofordulo´ legmagasabb abszolut ´ e´ rt´eku ˝ elem 2.386.233. Mivel, nagyobb matrixokban ´ ez a probl´ema m´eg e´ lesebben jelentkezik, fontos feladat, hogy olyan HNF algoritmusokat tervezzunk, ¨ amelyekben a k¨ozbuls˝ ¨ o matrixok ´ elemei nem n˝onek tulzottan ´ nagyra. Ez jelenleg is egy akt´ıv kutatasi ´ terulet. ¨ Jegyzet friss´ ıtve:
2006. december 12.
14
Abel-csoportok
1. algoritmus: HNF Input: M ∈ Mm,n (Z) Output: HNF of M set i := 1; j := 1; while i 6 m and j 6 n if Mi,j = · · · = Mm,j = 0 then set j := j + 1 else while ∃k 6= ℓ ∈ {i, . . . , m} : 0 < |Mk,j | 6 |Mℓ,j | do set q := Mℓ,j div Mk,j set Mℓ := Mℓ − qMk end while set k ∈ {i, . . . , m} : Mk,j 6= 0 /* k egy´ertelmu ˝ */ if k 6= i then set Mi ↔ Mk end if if Mi,j < 0 then set Mi := −Mi end if for ℓ ∈ {1, . . . , i − 1} set q := Mℓ,j div Mi,j set Mℓ := Mℓ − qMi end if set i := i + 1; j := j + 1 end if end while return M Algorithm 1: A HNF kiszam´ ´ ıtasa ´
Jegyzet friss´ ıtve:
2006. december 12.
´ Csoportelmeleti algoritmusok
15
T´etel 1.5.3 A HNF program outputja az egy olyan HNF alaku´ matrix ´ amely sorekvivalens az M ∈ Mm,n (Z) input matrixszal. ´ ´ . Mivel a programban csak elemi sormuveleteket B IZONY´I T AS ˝ hajtottunk v´egre, a program futasa ´ soran ´ minden l´ep´es az eredetivel sor-ekvivalens matrixot ´ eredm´enyez. Tehat ´ a v´egs˝o matrix ´ szint´en sor-ekvivalens lesz az eredeti M matrixszal. ´ Ha i ∈ {1, . . . , n}, akkor jel¨olje M (i) azt a matrixot ´ melyet az M els˝o i oszlopab ´ ol ´ kapunk. Teljes indukcioval ´ belatjuk, ´ hogy a k¨ovetkez˝o all´ ´ ıtasok ´ teljesulnek. ¨ (i) A j valtoz ´ o´ szaml ´ alja, ´ hogy a kuls˝ ¨ o while ciklus hanyszor ´ futott le. (j) Tovabb ´ a, ´ a kuls˝ ¨ o while ciklus j lefutasa ´ utan ´ M HNF alaku. ´ (ii) A kuls˝ ¨ o while ciklus j lefutasa ´ utan ´ az M (j) matrixban ´ a nem-nulla sorok szama ´ i − 1, tovabb ´ a´ i 6 j teljesul. ¨ A fenti all´ ´ ıtasokat ´ j szerinti indukcioval ´ bizony´ıtjuk. Az j = 0 esetben nincs mit belatnunk. ´ Tegyuk ¨ fel, hogy az all´ ´ ıtas ´ igaz a ciklus j − 1 elv´egz´ese utan, ´ e´ s lassuk ´ be, hogy az j-dik lefutas ´ utan ´ is igaz marad. A while utani ´ if utas´ıtas ´ felt´etele pontosan akkor teljesul, ¨ ha a j-dik oszlopban az i-dik sortol ´ (j−1) (j) lefel´e, nincs nem-nulla elem. Ekkor, ha M HNF alaku, ´ akkor M is az, (j−1) (j) tovabb ´ a, ´ a nem-nulla sorok szama ´ M -ben e´ s M -ben megegyezik. Tehat ´ a j valtoz ´ ot ´ eggyel megn¨oveljuk, ¨ az i valtoz ´ ot ´ nem valtoztatjuk, ´ e´ s a while ciklus v´eg´ere ugrunk. ´Igy ebben az esetben a fenti (i)–(ii) all´ ´ ıtasok ´ tovabbra ´ is fennallnak. ´ Ezt tesszuk ¨ eg´eszen addig, m´ıg az if utas´ıtas ´ felt´etele hamissa´ nem valik, ´ azaz a j-dik oszlopban az i-dik sortol ´ kezd˝od˝oen talalhat ´ o´ egy nem-nulla elem. Tegyuk ¨ fel most, hogy ebben az esetben vagyunk. A bels˝o while ciklus mindaddig fut, m´ıg Mk,j 6= 0 legalabb ´ k´et kul¨ ¨ onb¨oz˝o k ∈ {i, . . . , m} eset´en. Amennyiben ez a felt´etel teljesul, ¨ ugy ´ az algoritmus kivalaszt ´ ezen elemek k¨ozul ¨ k´et nem-nullat, ´ mondjuk Mk,j -t e´ s Ml,j -t, ugy ´ hogy a |Mk,j | 6 |Ml,j | teljesulj¨ ¨ on. Ezekkel az elemekkel marad´ekos osztast ´ v´egzunk: ¨ Ml,j = qMk,j + r, ahol q e´ s r eg´esz szamok ´ e´ s 0 6 r < |Mk,j |. Ezutan ´ kivonjuk az l-dik sorbol ´ a kdik sor q-szorosat. ´ A muvelet ˝ utan ´ az Ml,j = r teljesul, ¨ ´ıgy sikerult ¨ cs¨okkenteni az Ml,j elem abszolut ´ e´ rt´ek´et. A bels˝o while ciklus minden iteraci ´ oja ´ utan ´ az |Mi,j | + · · · + |Mm,j | o¨ sszeg cs¨okken, ´ıgy a ciklus v´eges sok l´ep´es utan ´ v´eget e´ r. Jegyzet friss´ ıtve:
2006. december 12.
16
Abel-csoportok
A fentiek miatt, a bels˝o while ciklus befejez´ese utan ´ Mk,j 6= 0 pontosan egy k ∈ {i, . . . , m} eset´en. Ha k 6= i akkor felcser´eljuk ¨ az i-dik e´ s k-dik sorokat, majd pedig, ha ez az elem negat´ıv, akkor negaljuk ´ az i-dik sort. Ezutan ´ az M (j) matrix ´ i-dik soranak ´ vez´ereleme Mi,j , amelyre teljesul, ¨ hogy j > i, Mi,j > 0, e´ s az is, hogy a vez´erelem alatt csupa nulla elem talalhat ´ o. ´ Tehat ´ a 1.5.2 defin´ıcio´ (i)–(ii) felt´eteleit belattuk. ´ A (iii) felt´etel az algoritmus v´eg´en talalhat ´ o´ for ciklus miatt teljesul. ¨ Ha ugyanis, valamely l ∈ {1, . . . , i−1} eset´en Ml,j -re az (iii) felt´etel nem teljesul, ¨ akkor ism´et marad´ekos osztast ´ v´egzunk, ¨ Ml,j = qMi,j + r ahol 0 6 r < Mi,j , e´ s kivonjuk az i-dik sor q-szorosat ´ az l-dik sorbol. ´ Ezutan ´ az Ml,j elem kiel´eg´ıti a 1.5.2 defin´ıcio´ (iii) felt´etel´et is. Ha a matrix ´ oszlopainak szama ´ n, akkor a while ciklus n lefutasa ´ utan ´ M = M HNF alaku ´ lesz. 2 (n)
K¨ ovetkezm´eny 1.5.4 Minden egesz ´ matrix ´ sor-ekvivalens egy Hermite normal ´ formaban ´ lev ´ o˝ matrixszal. ´ ´ . Az el˝oz˝o t´etel szerint, a HNF algoritmus outputja e´ pp megfelel˝o. 2 B IZONY´I T AS Eml´ekezzunk, ¨ hogy a 1.3.1 t´etel szerint a Zn csoport minden r´eszcsoportja szabad csoport, ´ıgy egy A ∈ Mm,n (Z) matrix ´ eset´en is igaz, hogy hAi szabad. A HNF seg´ıts´eg´evel meghatarozhatjuk ´ ennek a csoportnak egy bazis ´ at. ´ T´etel 1.5.5 Ha A egy HNF matrix, ´ akkor A nem-nulla sorai az hAi csoport egy bazis ´ at ´ alkotjak. ´ ´ . Tegyuk B IZONY´I T AS ¨ fel, hogy A ∈ Mm,n (Z) egy HNF matrix, ´ e´ s legyen v ∈ hAi. A 1.2.9 lemma szerint elegend˝o belatni, ´ hogy v pontosan egyf´elek´eppen ´ırhato´ fel az A matrix ´ nem-nulla sorainak eg´esz egyutthat ¨ os ´ linearis ´ kombinaci ´ ojak´ ´ ent. Legyen r az A-beli nem-nulla sorok szama, ´ e´ s i ∈ {1, . . . , r} eset´en legyen Ai,ji az i-dik sor vez´ereleme. Ha feltesszuk, ¨ hogy v = (v1 , . . . , vn ) ∈ hAi, akkor v fel´ırhato´ v = α1 A1 + · · · + αr Ar
(1.1)
alakban, ahol A1 , . . . , Ar az A matrix ´ els˝o r sora, α1 , . . . , αr pedig eg´esz szamok. ´ ´ r egyenletb˝ol all ´ o´ egyenletrendA (1.1) egyenletb˝ol r szam ´ u ´ vji elemre az alabbi Jegyzet friss´ ıtve:
2006. december 12.
´ Csoportelmeleti algoritmusok
17
szert kapjuk: vj1 = α1 A1,j1 vj2 = α1 A1,j2 + α2 A2,j2 .. . vjr = α1 A1,jr + α2 A2,jr + · · · + αr Ar,jr . Tekintsuk ¨ ezt az egyenletrendszert a Q test felett. Az egyenletrendszer matrixa ´ n´egyzet alaku ´ also´ haromsz¨ ´ og matrix, ´ ´ıgy ennek a matrixnak ´ a determinansa ´ k nem-z´ero. ´ Ez´ert, ennek az egyenletrendszernek pontosan egy Q -beli megoldasa ´ van: (α1 , . . . , αr ). K¨ovetkez´esk´epp, a (1.1) fel´ıras ´ egy´ertelmu, ˝ tehat ´ az A nem-nulla sorai az hAi csoport egy bazis ´ at ´ adjak. ´ 2
Ha A ∈ Mm,k (Z), akkor szeretn´enk eld¨onteni p´eldaul, ´ hogy egy Zk -beli v elem benne van-e az hAi csoportban. A 1.5.5 t´etel bizony´ıtasa ´ azt sugallja, hogy a Hermite normal ´ forma seg´ıts´eg´evel ezt a probl´emat ´ is hat´ekonyan meg tudjuk oldani. P´elda 1.5.6 Legyen A a k¨ovetkez˝o matrix: ´ 0 0 0 −2 2 0 −2 1 1 −1 −2 −1 2 0 0 0 −3 1 −3 3
e´ s legyen v = (2, −1, 2, −4, 4). K´erd´es, hogy a v vektor eleme-e az hAi csoportnak. Egy A matrixszal ´ ekvivalens HNF matrix ´ a HNF algoritmus seg´ıts´eg´evel k¨onnyen kiszam´ ´ ıthato: ´ 2 0 0 0 0 0 1 0 0 0 0 0 1 1 −1 0 0 0 2 −2
Az 1.4.2 lemma szerint feltehetjuk, ¨ hogy A a fenti HNF matrix. ´ Legyenek A1 , A2 , A3 , A4 az A matrix ´ sorai, e´ s tegyuk ¨ fel hogy v ∈ hAi, azaz a v vektor fel´ırhato´ v = α1 A1 +α2 A2 +α3 A3 +α4 A4 alakban valamely α1 , α2 , α3 , α4 ∈ Z szamok ´ seg´ıts´eg´evel. A fenti linearis ´ kombinaci ´ o´ els˝o koordinat ´ aja ´ mindenk´epp 2α1 . Jegyzet friss´ ıtve:
2006. december 12.
18
Abel-csoportok
Mivel v els˝o koordinat ´ aja ´ 2, ´ıgy α1 = 1 kell, hogy teljesulj¨ ¨ on. Ugyanez a gondolatmenet mutatja, hogy a v masodik ´ koordinat ´ aja ´ α2 , ´ıgy α2 = −1, e´ s hasonloan ´ α3 = 2. A v vektor negyedik koordinat ´ aja ´ α3 + 2α4 . Emiatt, α4 = −3. Ezek utan ´ k¨onnyu ˝ szamol ´ as ´ mutatja, hogy valoban ´ v = A1 − A2 + 2A3 − 3A4 , tehat ´ v ∈ hAi. A fenti p´elda alapjan ´ k¨onnyu ˝ egy altal ´ anos ´ algoritmust l´etrehozni. Az algoritmus le´ıras ´ aban ´ a HNF algoritmusnal ´ hasznalt ´ jel¨ol´est alkalmazzuk, a v vektor i-dik komponens´et pedig vi jel¨oli.
2. algoritmus: I S M EMBER Input: A ∈ Mm,n (Z) HNF matrix ´ e´ s v ∈ Zn Output: (x1 , . . . , xm ) ha v ∈ hAi; egy´ebk´ent false set r := a nem-nulla sorok szama ´ for i ∈ {1, . . . , r} do set Ai,j := az i-dik sor vez´ereleme if Ai,j ∤ vj then return false end if set xi := vj /Ai,j set v := v − xi Ai end for if v 6= 0 then return false else return (x1 , . . . , xr , 0, . . . , 0) ∈ Zn end if Algorithm 2: Tartalmazasi ´ algoritmus T´etel 1.5.7 Legyen A ∈ Mm,n (Z) egy HNF matrix, ´ legyenek A1 , . . . , Am az A n matrix ´ sorai, es ´ legyen v ∈ Z . Ha v ∈ hAi, akkor az IsMember algoritmus outputja egy vektor (x1 , . . . , xm ) amelyre teljesul ¨ a v = x1 A1 + · · · + xm Am ; egyebk ´ ent ´ az output false. Jegyzet friss´ ıtve:
2006. december 12.
(1.2)
´ Csoportelmeleti algoritmusok
19
´ . Az r valtoz B IZONY´I T AS ´ o´ jel¨oli a nem-nulla sorok szam ´ at. ´ A for ciklus belsej´eben Ai,j az i-dik sor els˝o nem nulla eleme. Tegyuk ¨ fel el˝osz¨or, hogy v ∈ hAi e´ s ´ıgy v = x1 A1 + · · · + xm Am , ahol x1 , . . . , xm ∈ Z. Az 1.5.5 t´etel szerint az A matrix ´ els˝o r sora az hAi csoport egy bazis ´ at ´ adja, ez´ert az x1 , . . . , xr egyutthat ¨ ok ´ egy´ertelmuen ˝ meghatarozottak. ´ Tovabb ´ a, ´ mivel az utolso´ m − r sor nulla, az xr+1 , . . . , xm egyutthat ¨ ok ´ tetsz˝olegesek, tehat ´ feltehetjuk, ¨ hogy xr+1 = · · · = xm = 0. Legyen, i ∈ {0, . . . , r − 1} eset´en, vi = xi+1 Ai+1 + · · · + xr Ar , e´ s legyen vr = 0. ´ ıtjuk, hogy ha for ciklus i-szer sikeresen v´egigfut (azaz a ciklusbeli return All´ utas´ıtas ´ nem hajtodik ´ v´egre), az x1 , . . . , xi egyutthat ¨ ok ´ e´ rt´eke helyes, az algoritmusbeli v valtoz ´ o´ e´ rt´eke pedig vi . Az i = 0 esetben nincs mit belatni. ´ Tegyuk ¨ fel, hogy az all´ ´ ıtas ´ igaz a for ciklus i − 1 lefutasa ´ utan, ´ e´ s igazoljuk, hogy i lefutas ´ utan ´ is igaz marad. Legyen Ai,j az i-dik sor els˝o nem-nulla eleme. Ekkor a vi−1 vektor els˝o j − 1 komponense szuks´ ¨ egszeruen ˝ 0, vj pedig az Ai,j elem xi -szerese kell, hogy legyen. Tehat ´ ha Ai,j ∤ vj , akkor v 6∈ hAi e´ s az output false. Masr´ ´ eszr˝ol, ha Ai,j |vj , akkor xi = vj /Ai,j , e´ s ´ıgy a xi skalart ´ megtalaltuk. ´ Az ezt k¨ovet˝o set parancs miatt, v = vi−1 − xi Ai = vi . Ha a v vektor nem eleme a hAi csoportnak akkor k´et eset lehets´eges. Az els˝o esetben a for cikluson beluli ¨ if felt´etele nem teljesul, ¨ e´ s ´ıgy az output false. Ha ez nem igaz, akkor a for ciklus elv´egz´ese utan ´ a v vektor nem lehet nullvektor, mert ebben az esetben a v ∈ hAi teljesulne. ¨ Tehat ´ az algoritmus outputja ebben az esetben is false. 2 Korabban ´ lattuk, ´ hogy minden eg´esz matrix ´ sor-ekvivalens egy HNF mat´ rixszal. Most igazoljuk, hogy ez a matrix ´ l´enyeg´eben egy´ertelmuen ˝ meghatarozott. ´ T´etel 1.5.8 Ha H a Zn csoport egy reszcsoportja, ´ akkor letezik ´ pontosan egy HNF matrix ´ A melynek nincsenek zer ´ o´ sorai, es ´ amelyre H = hAi teljesul. ¨ ´ . Legyenek A e´ s B HNF matrixok B IZONY´I T AS ´ z´ero´ sorok n´elkul ¨ melyekre H = hAi = hBi teljesul. ¨ Az 1.5.5 t´etel szerint, az A sorai e´ s a B sorai is bazis ´ at ´ adjak ´ az hAi = hBi csoportnak, ´ıgy az 1.2.4 lemma szerint, az A sorainak szama ´ megegyezik a B sorainak szam ´ aval. ´ Jel¨oljuk ¨ ezt a szamot ´ m-mel. Az all´ ´ ıtast ´ m szerinti indukcioval ´ igazoljuk. Jegyzet friss´ ıtve:
2006. december 12.
20
Abel-csoportok
Ha m = 1, akkor matrixaink ´ mind¨ossze egy sorbol ´ allnak. ´ Mivel, A ∈ hBi, l´etezik α ∈ Z, melyre A = αB teljesul. ¨ Hasonloan, ´ B = βA valamely β ∈ Z eg´esz szamra. ´ Tehat, ´ A = αB = αβA. Mivel A-nak van nem-nulla eleme, azt kapjuk, hogy αβ = 1, tehat ´ vagy α = β = 1, vagy pedig α = β = −1. Mivel az A e´ s B matrixok ´ vez´erelemei nem-negat´ıvak, α = β = 1 k¨ovetkezik. Tehat, ´ ebben az esetben A = B, ´ıgy az all´ ´ ıtast ´ az m = 1 esetben igazoltuk. Tegyuk ¨ most fel, hogy m > 1. Legyenek a e´ s b az A e´ s B matrixok ´ els˝o sorainak vez´erelemei. Tegyuk ¨ fel, hogy a a j1 -dik oszlopban talalhat ´ o, ´ a b pedig a j2 -dik oszlopban. Ekkor, a HNF defin´ıcioja ´ miatt, a hAi csoport minden elem´eben az els˝o j1 − 1 koordinata ´ 0, tehat ´ a b elem oszlopszama ´ legalabb ´ j1 . Tehat ´ j1 6 j2 . Az e´ rvel´est megford´ıtva kapjuk, hogy j2 6 j1 , azaz j1 = j2 k¨ovetkezik; jel¨olje j ezt a szamot. ´ Legyen A1 az a matrix ´ melyet A-bol ´ kapunk az els˝o sor t¨orl´ese utan; ´ k´epezzuk ¨ a B1 matrixot ´ hasonloan. ´ A hA1 i csoport a hAi csoport pontosan azon elemeib˝ol all, ´ melyekben a j-dik komponens 0. Hasonloan, ´ a hB1 i csoport a hBi csoport pontosan azon elemeib˝ol all, ´ melyekben a j-dik komponens 0. Mivel hAi = hBi, k¨ovetkezik, hogy hA1 i = hB1 i. Jel¨olje H1 ezt a csoportot. Mivel az A1 e´ s B1 matrixok ´ HNF alakuak, ´ az indukcios ´ feltev´es miatt, A1 = B1 . Legyen u az A els˝o sora, v pedig a B els˝o sora. Jel¨olje D a H-beli elemek j-dik komponenseinek a halmazat. ´ A D halmaz a Z egy r´eszcsoportja, melyet a is e´ s b is general. ´ Ez´ert a = ±b, de mivel a is e´ s b is pozit´ıv, a = b k¨ovetkezik. Tehat ´ u − v ∈ H1 . Tegyuk ¨ fel, hogy u 6= v, e´ s legyen c az u − v vektor els˝o nem-nulla komponense. T´etelezzuk ¨ fel, hogy c a k-dik oszlopban van. Ekkor az A1 matrix ´ egyik soranak ´ vez´ereleme d szint´en a k-dik oszlopban van, e´ s d|c. Azonban a HNF defin´ıcioja ´ szerint, a d felett csak d-n´el kisebb nem-negat´ıv elemek lehetnek, ez´ert az u e´ s v matrixok ´ k-dik komponense kisebb mint d, ´ıgy a kul¨ ¨ onbs´eguk ¨ abszolut ´ e´ rteke is legfeljebb d − 1, ami ellentmondas. ´ Tehat ´ u = v, e´ s ´ıgy A = B. 2 K¨ ovetkezm´eny 1.5.9 Minden egesz ´ matrix ´ sor-ekvivalens pontosan egy HNF matrixszal. ´ ´ . Korabban B IZONY´I T AS ´ lattuk, ´ hogy l´etezik egy ilyen HNF matrix. ´ Tegyuk ¨ ˆ a nulla sorok elhagyasa fel, hogy A e´ s B ilyen matrixok, ´ e´ s jel¨olje Aˆ e´ s B ´ utan ´ Jegyzet friss´ ıtve:
2006. december 12.
´ Csoportelmeleti algoritmusok
21
D E D E ˆ , e´ s ´ıgy az el˝oz˝o t´etelb˝ol Aˆ = B ˆ k¨ovetkezik. kapott matrixokat. ´ Ekkor Aˆ = B Mivel A-nak e´ s B-nek ugyanannyi sora van, A = B szint´en teljesul. ¨ 2
1.6. Unimodul´aris m´atrixok Legyen A ∈ Mm,n (Z), e´ s tegyuk ¨ fel, hogy a B matrixot ´ az A-bol ´ egy elemi sormuvelet ˝ seg´ıts´eg´evel kaptuk. Legyen P ∈ Mm,m (Z) az a matrix ´ melyet az m × m-es egys´egmatrixb ´ ol ´ kapunk ugyanannak az elemi sormuveletnek ˝ az elv´egz´ese utan. ´ Az ilyen P matrix ´ neve elemi matrix. ´ A haromf´ ´ ele elemi sormuveletet ˝ egyenk´ent megvizsgalva, ´ k¨onnyu ˝ ellen˝orizni, hogy B = P A teljesul. ¨ Azaz egy elemi sormuvelet ˝ realizalhat ´ o´ mint egy elemi matrixszal ´ balrol ´ t¨ort´en˝o szorzas ´ eredm´enye. Ha most a B matrix ´ sor-ekvivalens az A matrixszal, ´ akkor a B megkaphato´ az A-bol ´ elemi sormuveletek ˝ sorozatos elv´egz´ese utan. ´ Ha P1 , . . . , Pk az ezekhez a sormuveletekhez ˝ tartozo´ elemi matrixok, ´ akkor a fenti gondolatmenet miatt B = Pk Pk−1 · · · P1 A. Tehat ´ bizony´ıtottuk az alabbi ´ lemmat. ´ Lemma 1.6.1 Legyenek A, B ∈ Mm,n (Z) sor-ekvivalens egesz ´ matrixok. ´ Ekkor leteznek ´ P1 , . . . , Pk ∈ Mm,m (Z) elemi matrixok ´ melyekre B = Pk Pk−1 · · · P1 A teljesul. ¨ Azok az Mm,m (Z)-beli A matrixok ´ melyekre A−1 ∈ Mm,m (Z) teljesul ¨ csoportot alkotnak; ennek a csoportnak a szokasos ´ neve m-dimenzios ´ unimodularis ´ csoport, jele pedig GLm (Z). Egy unimodularis ´ csoportban talalhat ´ o´ matrixokat ´ unimodularis ´ matrixoknak ´ nevezzuk. ¨ Mivel egy invertalhat ´ o´ A ∈ Mm,m (Z) eset´en −1 −1 det A = (det A) teljesul, ¨ egy unimodularis ´ matrix ´ determinansa ´ 1 vagy −1. A fenti lemmaban ´ szerepl˝o Pi matrixok ´ unimodularisak, ´ a szorzatuk is az, ´ıgy a k¨ovetkez˝o eredm´enyt kapjuk. Lemma 1.6.2 Ha A, B ∈ Mm,n (Z) sor-ekvivalens egesz ´ matrixok, ´ akkor letezik ´ P ∈ GLm (Z) matrix ´ melyre B = P A teljesul. ¨ Az unimodularis ´ matrixok ´ egy sokoldalu ´ e´ s jol ´ hasznalhat ´ o´ jellemz´es´et adja a k¨ovetkez˝o lemma. Jegyzet friss´ ıtve:
2006. december 12.
22
Abel-csoportok
Lemma 1.6.3 Ha B ∈ Mm,m (Z), akkor a k¨ovetkezok ˝ ekvivalensek: (i) B unimodularis; ´ (ii) det B = ±1; (iii) B sor-ekvivalens az m × m-es egysegm ´ atrixszal. ´ (iv) hBi = Zm ; (v) B elemi matrixok ´ szorzata. ´ . Az unimodularis B IZONY´I T AS ´ matrix ´ defin´ıcioj ´ an ´ al ´ belattuk, ´ hogy egy ilyen matrix ´ determinansa ´ 1 vagy −1. Tehat ´ (i)-b˝ol (ii) k¨ovetkezik. Tegyuk ¨ fel, hogy det B = ±1. Legyen A a B-hez tartozo´ HNF matrix. ´ Ekkor, az 1.6.2 lemma miatt, l´etezik P ∈ GLm (Z) mellyel A = P B, e´ s ´ıgy det A = (det P )(det B) = ±1 teljesul. ¨ Mivel A fels˝o haromsz¨ ´ og alaku, ´ az A sorainak vez´erelemei az atl ´ oban ´ talalhat ´ ok. ´ Mivel det A = ±1, az atl ´ oban ´ l´ev˝o elemek abszolut ´ e´ rt´eke 1, e´ s ´ıgy a HNF defin´ıcioja ´ miatt, egyr´eszt A diagonalis ´ matrix, ´ masr´ ´ eszt a diagonalisban ´ minden elem 1. Tehat ´ A az egys´egmatrix, ´ e´ s ´ıgy (ii)-b˝ol k¨ovetkezik (iii). Ha B ekvivalens az m × m-es egys´egmatrixszal, ´ akkor 1.4.2 lemma miatt, hBi = Zm , tehat ´ (iv) k¨ovetkezik a (iii)-bol. ´ Tegyuk ¨ fel most, hogy hBi = Zm . Jel¨olje A a B-vel ekvivalens HNF matrixot. ´ Ekkor A ∈ Mm,m (Z) melyre hBi = hAi = Zm teljesul. ¨ Mivel az I egys´egmatrix ´ sorai a Zm csoportot generalj ´ ak, ´ e´ s az egys´egmatrix ´ HNF alaku, ´ 1.5.8 t´etel miatt A = I, azaz B sor-ekvivalens I-vel. Ekkor azonban, 1.6.1 lemma szerint l´eteznek P1 , . . . , Pk ∈ GLm (Z) melyekkel, A = Pk · · · P1 = Pk · · · P1 teljesul, ¨ azaz (iv)-b˝ol k¨ovetkezik (v). Mivel az elemi matrixok ´ unimodularisak, ´ (v)-b˝ol nyilvan ´ k¨ovetkezik (i). 2 K¨ ovetkezm´eny 1.6.4 Az A, B ∈ Mm,n (Z) matrixok ´ sor-ekvivalensek, akkor es ´ csakis akkor, ha letezik ´ egy P ∈ GLm (Z) unimodularis ´ matrix ´ mellyel B = P A teljesul. ¨ ´ . A 1.6.2 lemma szerint az all´ B IZONY´I T AS ´ ıtas ´ az egyik iranyban ´ teljesul. ¨ Tegyuk ¨ fel, hogy l´etezik a felt´eteleket kiel´eg´ıt˝o P . Ekkor a 1.6.3 lemma szerint P = P1 · · · Pk , ahol Pi ∈ GLn (Z) egy elemi matrix. ´ Mivel minden elemi matrix ´ Jegyzet friss´ ıtve:
2006. december 12.
´ Csoportelmeleti algoritmusok
23
megfelel egy elemi sormuveletnek, ˝ ezeket a sormuveleteket ˝ ford´ıtott sorrendben az A matrixon ´ v´egrehajtva pontosan a B matrixot ´ kapjuk, tehat ´ A e´ s B valoban ´ sor-ekvivalensek. 2 Sok gyakorlati alkalmazasban ´ egy matrix ´ HNF alakja mellett szuks´ ¨ eg lehet a 1.6.4 k¨ovetkezm´enyben talalhat ´ o´ P transzformal ´ o´ matrix ´ meghataroz ´ as ´ ara ´ is. A transzformal ´ o´ matrixot ´ a 1. algoritmus egyszeru ˝ modos´ ´ ıtasa ´ seg´ıts´eg´evel megkaphatjuk. Az algoritmus elej´en a P matrixot ´ az egys´egmatrixnak ´ inicializaljuk. ´ K´es˝obb az algoritmus futasa ´ soran ´ minden M matrixszal ´ v´egzett sor-muvelet ˝ utan ´ a P matrixszal ´ is elv´egezzuk ¨ ugyanazt a sor-muveletet. ˝ Az algoritmus v´eg´en a P matrix ´ valoban ´ a transzformal ´ o´ matrix ´ lesz.
1.7. Smith norm´al forma Ebben a r´eszben az eg´esz matrixok ´ egy masik ´ normal ´ formaj ´ aval ´ ismerkedunk ¨ meg, amelyet ugy ´ kapunk, hogy elemi sormuveletek ˝ mellett elemi oszlopmuveleteket ˝ is megengedunk. ¨ Az elemi oszlopmuveletek ˝ az elemi sormuveletek ˝ nyilvanval ´ o´ megfelel˝oi. Azt mondjuk, hogy k´et eg´esz matrix ´ ekvivalens, ha az egyik megkaphato´ a masikb ´ ol ´ elemi sor- e´ s oszlopmuveletek ˝ seg´ıts´eg´evel. A k¨ovetkez˝o all´ ´ ıtas ´ a HNF-n´el targyalt ´ hasonlo´ all´ ´ ıtasokhoz ´ hasonloan ´ igazolhato. ´ Lemma 1.7.1 (i) A fenti ekvivalencia fogalom ekvivalencia relaci ´ o´ az egesz ´ matrixok ´ halmazan. ´ (ii) Ket ´ A, B ∈ Mm,n (Z) matrix ´ pontosan akkor ekvivalens, ha leteznek ´ P ∈ GLm (Z) es ´ Q ∈ GLn (Z) melyekkel P AQ = B teljesul. ¨ Sor- e´ s oszlopmuveleteket ˝ v´egrehajtva egy matrixot ´ kanonikus alakra hozhatunk. Azt mondjuk, hogy egy eg´esz matrix ´ A Smith normal ´ formaj ´ u, ´ ha (i) l´etezik r, ugy ´ hogy Ai,i > 0 minden i 6 r eset´en; (ii) A minden mas ´ eleme z´ero´ (azaz A diagonalis ´ matrix ´ e´ s a nulla sorok a v´eg´en talalhat ´ ok); ´ (iii) i ∈ {1, . . . , r − 1} eset´en, Ai,i osztoja ´ Ai+1,i+1 -nek. Jegyzet friss´ ıtve:
2006. december 12.
24
Abel-csoportok
T´etel 1.7.2 Minden egesz ´ matrix ´ ekvivalens egy Smith normal ´ formaban ´ lev ´ o˝ matrixszal. ´ ´ . Az alabbiakban B IZONY´I T AS ´ ismertetunk ¨ egy eljar ´ ast ´ amely alkalmas a SNF kiszam´ ´ ıtas ´ ara. ´ Legyen M ∈ Mm,n (Z) melyet SNF alakra k´ıvanunk ´ hozni. Az eljar ´ as ´ els˝o fazis ´ aban ´ az M matrixot ´ d 0 ··· 0 0 . (1.3) . C . 0
alakra hozzuk, ahol C ∈ Mm−1,n−1 (Z). Keressunk ¨ el˝osz¨or egy nem-nulla Mi,j elemet a matrixban. ´ Ha nincs ilyen elem, akkor M a z´ero-m ´ atrix, ´ ami SNF alaku, ´ tehat ´ nincs t¨obb tennivalonk. ´ Legyen tehat ´ Mi,j 6= 0. C´elunk, hogy elemi sor- e´ s oszlopmuveletekkel ˝ el´erjuk, ¨ hogy a matrix ´ i-dik soraban ´ e´ s j-dik oszlopaban ´ l´ev˝o elemek az Mi,j elem t¨obbsz¨or¨osei legyenek. Tegyuk ¨ fel, hogy Mi,j nem osztoja ´ az Mk,j elemnek. V´egezzunk ¨ marad´ekos osztast ´ Mk,j = qMi,j + r ahol 0 6 r < |Mi,j |. Vonjuk ki most az i-dik sor q-szorosat ´ a k-dik sorbol. ´ Ezutan ´ Mk,j = q teljesul, ¨ e´ s valtoztassuk ´ meg az i e´ rt´ek´et k-ra. Ezek utan ´ az Mi,j tovabbra ´ is nem-nulla, de az abszolut´ ´ ert´eke cs¨okkent az el˝oz˝oekhez k´epest. Ha Mi,j nem osztoja ´ valamely Mi,k elemnek, akkor az el˝oz˝oekhez hasonloan, ´ marad´ekos osztast ´ v´egzunk: ¨ Mi,k = qMi,j + r ahol 0 6 r < |Mi,j |, kivonjuk a j-dik oszlop q-szorosat ´ a k-dik oszlopbol, ´ majd a j e´ rt´ek´et k-ra valtoztatjuk. ´ Ezt addig csinaljuk, ´ m´ıg Mi,j osztoja ´ lesz minden i-dik sorbeli e´ s j-dik oszlopbeli elemnek. Ez v´eges id˝o utan ´ nyilvan ´ teljesulni ¨ fog, mert minden fenti l´ep´es utan ´ cs¨okken az Mi,j abszolut ´ e´ rt´eke an´elkul, ¨ hogy nullav ´ a´ valna. ´ Ha egyszer el´ertuk, ¨ hogy az idik sor e´ s a j-dik oszlop elemei mind oszthatok ´ a Mi,j elemmel, akkor elemi sor e´ s oszlopmuveletek ˝ seg´ıts´eg´evel el´erhetjuk, ¨ hogy az i-dik sorban e´ s a j-dik oszlopban csak az Mi,j elem legyen nem-nulla. Ezutan ´ egy oszlopcsere e´ s egy sorcsere seg´ıts´eg´evel kapunk egy (1.3) alaku ´ matrixot. ´ A fenti gondolatmenetet rekurz´ıvan ism´etelve a C matrixra, ´ egy diagonalis ´ matrixot ´ kapunk, melyre az SNF defin´ıcioj ´ anak ´ (i)–(ii) felt´etelei teljesulnek. ¨ Legyenek d1 = M1,1 , . . . , dr = Mr,r a diagonalis ´ matrix ´ nem-nulla elemei. Ha Jegyzet friss´ ıtve:
2006. december 12.
´ Csoportelmeleti algoritmusok
25
di |di+1 minden i ∈ {1, . . . , r − 1} eset´en, akkor a matrixunk ´ mar ´ SNF, tehat ´ az all´ ´ ıtasunkat ´ igazoltuk. Tegyuk ¨ fel, hogy ez nem teljesul ¨ valamely i eset´en. Jel¨olje d a gcd(Mi,i , Mi+1,i+1 ) legnagyobb k¨oz¨os osztot, ´ e´ s legyenek u, v ∈ Z melyekre uMi,i + vMi+1,i+1 = gcd(Mi,j , Mi+1,i+1 ) teljesul. ¨ Legyen
e´ s
1 0 .. . . .. . . . 0 ··· u v ··· 0 L= 0 · · · −Mi+1,i+1 /d Mi,i /d · · · 0 .. . . .. . . . 0 ··· 1
1 0 .. . . .. . . . 0 · · · 1 −vM i+1,i+1 /d · · · 0 R= 0 ··· 1 uMi,i /d ··· 0 .. . . .. . . . 0 ··· 1
ahol R ∈ Mn,n (Z) e´ s L ∈ Mm,m (Z), melyekben a nem-trivialis ´ blokkok az idik e´ s (i + 1)-dik sorokban illetve oszlopokban talalhat ´ ok. ´ K¨onnyu ˝ szamol ´ as ´ mutatja, hogy | det R| = | det L| = 1, tehat ´ L e´ s R unimodularis ´ matrixok. ´ Tovabb ´ a, ´ a LMR matrix ´ pontosan ugyanugy ´ n´ez ki mint az M matrix, ´ csak az i-dik atl ´ oelem ´ hely´en gcd(Mi,i , Mi+1,i+1 ) az (i + 1)-dik atl ´ oelem ´ hely´en pedig lcm(Mi,i , Mi+1,i+1 ) talalhat ´ o. ´ Megmutatjuk, hogy a fenti eljar ´ as ´ seg´ıts´eg´evel egy diagonalis ´ matrixb ´ ol ´ SNF matrixot ´ nyerhetunk. ¨ Legyenek d1 , . . . , dr a diagonalis ´ matrixunk ´ elemei. Hajtsuk v´egre az eljar ´ ast ´ el˝osz¨or a (d1 , d2 ), majd a (d1 , d3 ), e´ s sorban minden (d1 , di ) parra, ´ ahol i 6 r. Az eljar ´ as ´ v´egen az uj ´ d1 elem a r´egi d1 , . . . , dr elemek legnagyobb k¨oz¨os osztoja ´ lesz, i > 2 eset´en pedig az uj ´ di elem a r´egi d1 e´ s di elemek legnagyobb k¨oz¨os t¨obbsz¨or¨ose. Specialisan, ´ ezzel azt is el´ertuk, ¨ hogy d1 |di teljesul ¨ minden i ∈ {1, . . . , r} eset´en. Tegyuk ¨ fel tehat, ´ hogy a diagonalis ´ matrixunkban ´ d1 osztoja ´ minden di elemnek. V´egezzuk ¨ most el az eljar ´ ast ´ sorban a (d2 , d3 ), (d2 , d4 ), stb, parokra. ´ A fenti okoskodashoz ´ hasonloan ´ Jegyzet friss´ ıtve:
2006. december 12.
26
Abel-csoportok
belathatjuk, ´ hogy ezutan ´ az uj ´ d2 a r´egi d2 , . . . , dr elemek legnagyobb k¨oz¨os osztoja ´ lesz, illetve, hogy, az uj ´ d2 osztoja ´ lesz az uj ´ d3 , . . . , dr elemeknek. Jegyezzuk ¨ meg, hogy a d1 elemet ebben a l´ep´esben nem valtoztattuk ´ meg. Mivel d1 osztoja ´ volt a r´egi d2 , . . . , dr elemeknek, az uj ´ d2 pedig ezek legnagyobb ¨ k¨oz¨os osztoja, ´ ´ıgy kapjuk, hogy d1 osztja az uj ´ d2 -t. Osszefoglalva, a masodik ´ l´ep´es utan ´ egy olyan diagonalis ´ matrixot ´ kapunk melyben d1 |d2 e´ s, minden i ∈ {3, . . . , r} eset´en, d2 |di. Ezek utan ´ nyilvanval ´ o, ´ hogy az eljar ´ ast ´ folytatva valoban ´ SNF matrixot ´ nyerunk. ¨ 2 P´elda 1.7.3 Tekintsuk ¨ a k¨ovetkez˝o M matrixot: ´ 0 4 1 M = 3 −2 −1 . 3 −4 −1 Hatarozzunk ´ meg egy S SNF matrixot, ´ amely ekvivalens az M matrixszal, ´ illetve hatarozzunk ´ meg P, Q ∈ GL3 (Z) matrixokat ´ melyekkel P MQ = S teljesul. ¨ Az 1.7.2 t´etelben ismertetett eljar ´ as ´ szerint az M matrix ´ elemi sor- e´ s oszlopmuveletekkel ˝ diagonalis ´ alakra hozhato: ´ 0 4 1 0 4 1 0 4 1 0 4 1 (4) (3) (2) (1) 2 0 −→ 3 2 0 −→ 0 2 0 −→ 3 −2 −1 −→ 3 3 0 0 3 0 0 3 −4 −1 3 −4 −1 3 0 0 3 0 0 (5) 0 2 0 −→ 0 2 0 . 0 0 1 0 4 1
Jel¨olje S1 a fenti sorban l´ev˝o utolso´ matrixot. ´ Az S1 matrix ´ diagonalis, ´ de m´eg nem SNF. Miel˝ott tovabbl´ ´ epunk, ¨ hatarozzunk ´ meg olyan P1 , Q1 ∈ GL3 (Z) matrixokat ´ melyekkel P1 MQ1 = S1 teljesul. ¨ Ilyen matrixokat ´ a k¨ovetkez˝o egyszeru ˝ eljar ´ assal ´ talalunk. ´ Legyenek el˝osz¨or P1 = Q1 = I, majd a fenti l´ep´eseket imitaljuk ´ a P1 e´ s Q1 matrixokon ´ a k¨ovetkez˝ok´eppen. Amikor a fenti eljar ´ asban ´ sormuveletet ˝ hajtunk v´egre, hajtsuk v´egre ugyanazt a sormuveletet ˝ a P1 matrixon., ´ ha pedig oszlopmuveletet ˝ v´egzunk, ¨ v´egezzuk ¨ el ugyanazt az oszlopmuveletet ˝ a Q1 matrixon. ´ Jegyezzuk ¨ meg, hogy az (1), (2), (3), e´ s (4) Jegyzet friss´ ıtve:
2006. december 12.
´ Csoportelmeleti algoritmusok
27
l´ep´esekben v´egeztunk ¨ sormuveleteket, ˝ az (5) l´ep´esben pedig oszlopmuveletet ˝ (az (5) l´ep´es valoj ´ aban ´ sormuveletk´ ˝ ent is felfoghato, ´ de tekintsuk ¨ most itt oszlopmuveletnek). ˝ V´egezzuk ¨ tehat ´ a fenti sormuveleteket ˝ a P1 matrixon: ´ 1 0 0 1 0 0 1 0 0 1 0 0 (3) (2) (1) 0 1 0 −→ 1 1 0 −→ 1 1 0 −→ 0 1 −1 1 0 1 1 0 1 0 0 1 0 0 1 1 0 1
(4) −→
0 1 1 −1 = P1 . 0 0
Most pedig v´egezzuk ¨ el a fenti egyetlen oszlopmuveletet ˝ a Q1 matrixon: ´ 1 0 0 1 0 0 (5) 1 0 = Q1 . 0 1 0 −→ 0 0 −4 1 0 0 1
Ezek utan ´
3 0 0 1 0 0 0 4 1 1 0 1 P1 MQ1 = 0 1 −1 3 −2 −1 0 1 0 = 0 2 0 = S1 0 0 1 0 −4 1 3 −4 −1 1 0 0
teljesul. ¨ A 1.7.2 t´etel bizony´ıtas ´ aban ´ ismertetett eljar ´ as ´ szerint az S1 matrixot ´ tovabb ´ transzformalhatjuk. ´ Alkalmazzuk az eljar ´ ast ´ az S1 matrix ´ els˝o k´et diagonalis ´ elem´ere. Ekkor gcd(3, 2) = 1, e´ s 3 − 2 = 1 teljesul, ¨ tehat ´ a d = 1, u = 1, e´ s v = −1 szereposztassal ´ dolgozunk: 1 0 0 1 2 0 3 0 0 1 −1 0 3 0 0 2 0 1 3 0 = 0 6 0 . −2 0 0 1 0 0 1 0 0 1 0 0 1
Legyen
1 −1 2 1 0 1 1 −1 0 P2 = −2 3 −5 3 0 0 1 −1 = −2 1 0 0 1 0 0 0 0 1
Jegyzet friss´ ıtve:
2006. december 12.
28 e´ s
Abel-csoportok
1 2 0 1 2 0 1 0 0 Q2 = 0 3 0 1 0 1 3 0 = 1 −4 −12 1 0 0 1 0 −4 1
A fentiek szerint 1 −1 2 P2 MQ2 = −2 3 −5 1 0 0 1 1 −1 0 = −2 3 0 0 1 0 0 1
1 2 0 4 1 3 3 −2 −1 1 −4 −12 3 −4 −1 1 0 4 1 0 1 1 −1 3 −2 −1 0 0 3 −4 −1 0 0 1 3 0 0 1 −1 0 = −2 3 0 0 2 0 1 0 0 0 1 0 0 1
0 0 1
1 0 0 1 0 1 0 −4 1 1 2 0 3 0 = 0 0 0 1
2 0 3 0 0 1 0 0 6 0 0 1
A fenti egyenlet jobb oldalan ´ l´ev˝o matrixb ´ ol ´ a masodik ´ e´ s harmadik sorok, illetve ugyanezen oszlopok cser´eje utan ´ kapjuk az SNF matrixot, ´ a P e´ s Q matrixokat ´ pedig a P2 -b˝ol e´ s Q2 -b˝ol kapjuk, ha P2 -n v´egrehajtjuk ugyanezt a sormuveletet, ˝ Q2 -n pedig ugyanezt az oszlopmuveletet. ˝ Tehat ´ 1 0 2 1 −1 2 1 0 0 S = 0 1 0 , P = 1 3 0 0 , e´ s Q = 1 0 −4 1 −12 −2 3 −5 0 0 6
Egyszeruen ˝ ellen˝orizhetjuk, ¨ hogy P, Q ∈ GL3 (Z) 1 0 4 1 1 −1 2 P MQ = 1 0 0 3 −2 −1 1 −4 3 −4 −1 −2 3 −5
e´ s, hogy 1 0 0 0 2 0 3 = 0 1 0 = S. 0 0 6 1 −12
´ e´ s invari´ans faktorok 1.8. Elemi osztok Azt a t´enyt, hogy, a HNF-hez hasonloan, ´ az SNF is egy´ertelmu, ˝ az invarians ´ faktorok seg´ıts´eg´evel igazoljuk. Tegyuk ¨ fel, hogy A ∈ Mm,n (Z), legyenek I ⊆ {1, . . . , m}, J ⊆ {1, . . . , n} e´ s jel¨olje AI,J az I-beli indexu ˝ sorok, illetve a Jegyzet friss´ ıtve:
2006. december 12.
´ Csoportelmeleti algoritmusok
29
J-beli indexu ˝ oszlopok altal ´ meghatarozott ´ almatrixot. ´ Ha 1 6 k 6 min{m, n}, akkor jel¨olje δk (A) a det AI,J aldeterminansok ´ legnagyobb k¨oz¨os osztoj ´ at, ´ ahol |I| = |J| = k. Specialisan ´ δ1 (A) jel¨oli a matrix ´ elemek legnagyobb k¨oz¨os osztoj ´ at, ´ δ2 (A) jel¨oli a (2 × 2)-es aldeterminansok ´ legnagyobb k¨oz¨os osztoj ´ at, ´ e´ s ´ıgy tovabb. ´
Lemma 1.8.1 Ha A es ´ B ekvivalens egesz ´ matrixok, ´ akkor minden alkalmas k eseten, ´ δk (A) = δk (B). ´ . Tegyuk B IZONY´I T AS ¨ fel, hogy A, B ∈ Mm,n (Z). Elegend˝o belatni, ´ hogy egy sor- illetve oszlopmuvelet ˝ nem valtoztat ´ a δk mennyis´egeken. Itt ezt az all´ ´ ıtast ´ csak sormuveletekre ˝ igazoljuk, mivel oszlopmuveletekre ˝ a bizony´ıtas ´ ugyanugy ´ t¨ort´enik. Legyenek I ⊆ {1, . . . , m} e´ s J ⊆ {1, . . . , n}, ugy ´ hogy |I| = |J| = k. Legyen B az a matrix ´ melyet A-bol ´ kapunk az i-dik sor (−1)-gyel t¨ort´en˝o szorzas ´ aval. ´ Ekkor, ha i ∈ I, akkor det BI,J = − det AI,J , ha pedig i 6∈ I, akkor det BI,J = det AI,J . Tehat ´ ebben az esetben δk (A) = δk (B) teljesul. ¨ Legyen most B az a matrix ´ melyet az A-bol ´ kapunk az i-dik e´ s a j-dik sorok cser´ej´evel. Ha i, j 6∈ I, akkor det BI,J = det AI,J , illetve ha i, j ∈ I, akkor pedig det BI,J = − det AI,J . Ha i ∈ I, de j 6∈ I, akkor det BI,J = ± det AI1 ,J , ahol I1 jel¨oli azt a halmazt melyet az I-b˝ol kapunk az i e´ s j indexek kicser´el´es´evel. Tehat ´ ebben az esetben is δk (A) = δk (B). Tegyuk ¨ most fel, hogy a B matrixot ´ ugy ´ kapjuk az A-bol, ´ hogy az i-dik sor αszorosat ´ adjuk a j-dik sorhoz. Ha j 6∈ I, akkor det AI,J = det BI,J . Tegyuk ¨ fel az altal ´ anoss ´ ag ´ megs´ert´ese n´elkul, ¨ hogy j az I els˝o eleme. Legyen AI,J = (au,v )ku,v=1 e´ s legyenek c1 , . . . , ck az A matrix ´ i-dik soraban ´ a J altal ´ indexelt oszlopokban l´ev˝o elemek. Ekkor
BI,J
=
a1,1 + αc1 · · · a1,k + αck a2,1 ··· a2,k .. .. . . ak,1 ··· ak,k
Jegyzet friss´ ıtve:
2006. december 12.
30
Abel-csoportok
e´ s az els˝o sor szerint kifejtve kapjuk, hogy det BI,J = det AI,J + α det C, ahol
C=
c1 · · · a2,1 · · · .. .
ck a2,k .. .
ak,1 · · · ak,k
.
Ha i ∈ I, akkor a C matrixnak ´ k´et sora megegyezik, e´ s ´ıgy det C = 0. Ha ez nem teljesul, ¨ akkor det C = ± det AI1 ,J , ahol I1 indexhalmazt ugy ´ kapjuk az Ib˝ol, hogy a j indexet az i-vel helyettes´ıtjuk. ¨ Tehat ´ mindk´et esetben det BI,J eg´esz egyutthat ¨ os ´ linearis ´ kombinaci ´ oja ´ det AI1 ,J1 alaku ´ mennyis´egeknek, ahol |I1 | = |J1 | = k, e´ s δk (A)|δk (B) k¨ovetkezik. Mivel az elemi sormuveletek ˝ megford´ıthatok, ´ hasonloan ´ kapjuk, hogy δk (B)|δk (A), tehat ´ δk (A) = δk (B). 2 Ezek utan ´ igazolhatjuk, hogy az SNF valoban ´ egy´ertelmu. ˝ K¨ ovetkezm´eny 1.8.2 Legyen A ∈ Mm,n (Z) egy SNF matrix ´ melynek atl ´ obeli ´ elemei a1 , . . . , ar . Ekkor k ∈ {1, . . . , min{m, n}} eseten, ´ δk (A) = a1 · · · ak . K¨ovetkezesk ´ epp, ´ egy egesz ´ matrix ´ M ekvivalens pontosan egy SNF matrixszal. ´ ´ . Legyenek I ⊆ {1, . . . , m} e´ s J ⊆ {1, . . . , n} melyekre |I| = |J| = k telB IZONY´I T AS jesul. ¨ Ha I 6= J, akkor AI,J egy sora csupa nullakb ´ ol ´ all, ´ e´ s ´ıgy det AI,J = 0. Q Tehat, ´ δk (A) a det AI,I = ´ aldeterminansok ´ legnagyobb k¨oz¨os i∈I ai alaku osztoja. ´ Ha I0 = {1, . . . , k}, akkor az SNF defin´ıcioja ´ szerint det AI0 ,I0 osztoja ´ a det AI,I -nek e´ s det AI0 ,I0 nem-negat´ıv, tehat ´ δk (A) = det AI0 ,I0 = a1 · · · ak . Tegyuk ¨ fel, hogy A e´ s B SNF matrixok ´ melyek ekvivalensek az M matrixszal. ´ Legyenek a1 , . . . , ar az A matrix ´ nem-nulla atl ´ obeli ´ elemei, b1 , . . . , bs pedig a B matrix ´ nem-nulla atl ´ obeli ´ elemei. Igazoljuk i szerinti indukcioval, ´ hogy ai = bi . Az SNF defin´ıcioj ´ ab ´ ol ´ k¨ovetkezik, hogy a1 = δ1 (A), illetve b1 = δ1 (B). Mivel A e´ s B ekvivalens matrixok, ´ ´ıgy a1 = b1 adodik, ´ tehat ´ az all´ ´ ıtas ´ igaz i = 1 eset´en. Tegyuk ¨ fel, hogy az all´ ´ ıtas ´ igaz i − 1-re. A k¨ovetkezm´eny els˝o all´ ´ ıtasa ´ miatt, a1 · · · ai = δi (A), illetve b1 · · · bi = δi (B). Mivel δi (A) = δi (B) e´ s, az indukcios ´ feltev´es miatt, a1 · · · ai−1 = b1 · · · bi−1 , azt kapjuk, hogy ai = bi . 2 Ha A ∈ Mm,n (Z), akkor az A-val ekvivalens SNF matrix ´ atl ´ obeli ´ elemeit az A elemi osztoinak ´ vagy mask´ ´ eppen invarians ´ faktorainak nevezzuk. ¨ A Jegyzet friss´ ıtve:
2006. december 12.
´ Csoportelmeleti algoritmusok
31
1.8.1 lemma e´ s a 1.8.2 k¨ovetkezm´eny szerint ezek a mennyis´egek az jellemzik ekvivalencia osztalyokat, ´ abban az e´ rtelemben, hogy k´et matrixr ´ ol ´ ezen mennyis´egek ismeret´eben eld¨onthet˝o, hogy ekvivalensek-e.
1.9. V´egesen gener´alt Abel-csoportok Legyen G egy Abel-csoport, e´ s legyen hx1 , . . . , xn i egy generator-rendszer. ´ Len gyen e1 , . . . , en a Z csoport standard bazisa. ´ Ekkor a 1.2.6 k¨ovetkezm´eny szerint, a ϕ : ei 7→ xi lek´epez´es egy´ertelmuen ˝ kiterjeszthet˝o egy ϕ : Zn → G epimorfizmussa. ´ A kiterjeszt´est defin´ıcioja: ´ ϕ(α1 , . . . , αn ) = α1 x1 + · · · + αn xn . n Mivel ϕ szurjekt´ ¨ ıv, G ∼ = Z / ker ϕ. A 1.3.1 lemma szerint, a ker ϕ csoport v´eges sok elemmel generalhat ´ o, ´ tehat ´ l´etezik egy M ∈ Mm,n (Z) matrix ´ mellyel ker ϕ = hMi. Ez a gondolatmenet mutatja, hogy a k¨ovetkez˝o lemma helyes.
Lemma 1.9.1 Minden vegesen ´ generalt ´ Abel-csoport elo˝ all ´ Zn / hMi alakban, ahol M ∈ Mm,n (Z). A 1.3.1 lemma egyik all´ ´ ıtasa, ´ hogy a 1.9.1 lemmaban ´ altal ´ aban ´ m 6 n is feltehet˝o. Tekintsunk ¨ el˝osz¨or egy egyszeru, ˝ majd k´et bonyolultabb p´eldat. ´ P´elda 1.9.2 Legyen G = Z3 ⊕Z5 ⊕Z = hai⊕hbi⊕hci. Ekkor a G csoport megadhato´ G = ha, b, c | 3a = 0, 5b = 0i 3 alakban, tehat ´ G∼ = Z / hAi, ahol
A=
3 0 0 0 5 0
!
.
P´elda 1.9.3 Legyenek a, b, c pozit´ıv eg´eszek, e´ s definialjuk ´ az D E F a,b,c = r, s | r 2 = 1, rsa rsb rsc = 1 e´ s a
H
a,b,c
D
2
= r, s | r = 1, s
2(a+b+c)
Jegyzet friss´ ıtve:
a
b
c
= 1, rs rs rs = 1
2006. december 12.
E
32
Abel-csoportok
csoportokat. (Vigyazzunk: ´ ezek nem Abel-csoportok!) Legyenek Aa,b,c e´ s B a,b,c az F a,b,c e´ s a H a,b,c csoportok legnagyobb Abel-f´ele faktorai, azaz, Aa,b,c = F a,b,c /(F a,b,c )′
e´ s
B a,b,c = H a,b,c /(H a,b,c)′
ahol (F a,b,c )′ e´ s (H a,b,c )′ jel¨olik a szobanforg ´ o´ csoportok kommutator ´ r´eszcsoportjait. Ekkor Aa,b,c = hr, s | 2r = 0, 3r + (a + b + c)s = 0i e´ s B a,b,c = hr, s | 2r = 0, 2(a + b + c)s = 0, 3r + (a + b + c)s = 0i .
2 a,b,c ∼ 2 Tehat ´ Aa,b,c ∼ = Z / hAi e´ s B = Z / hBi, ahol
A=
2 0 3 a+b+c
!
2 0 e´ s B = 0 2(a + b + c) 3 a+b+c
P´elda 1.9.4 Legyenek l, m, n eg´esz szamok, ´ e´ s jel¨olje ∆(l, m, n) a D E 2 2 2 l m n ∆(l, m, n) = a, b, c | a = 1, b = 1, c = 1, (ab) = 1, (ca) = 1, (bc) = 1
csoportot. A ∆(l, m, n) csoport neve haromsz¨ ´ og csoport. K¨onnyu ˝ latni, ´ hogy a ∆(l, m, n) haromsz¨ ´ og csoport kommutator ´ r´eszcsoport szerinti faktora a ha, b, c | 2a = 0, 2b = 0, 2c = 0, la + lb = 0, ma + mc = 0, nb + nc = 0i csoport. Jel¨olje ezt az Abel-csoportot A(l, m, n). A fentiek szerint az A(l, m, n) csoport megadhato´ mint Z3 / hAi ahol 2 0 0 0 2 0 0 0 2 A= l l 0 . m 0 m 0 n n
Ezekkel a csoportokkal a k´es˝obbiekben tovabbi ´ muveleteket ˝ fogunk v´egezni, p´eldaul ´ meghatarozzuk ´ a kommutator ´ szerinti faktorcsoportok izomorfia-osztaly ´ at. ´ Igazoljuk most, hogy ekvivalens matrixok ´ izomorf csoportokhoz vezetnek. Jegyzet friss´ ıtve:
2006. december 12.
´ Csoportelmeleti algoritmusok
33
T´etel 1.9.5 Tegyuk ¨ fel, hogy A, B ∈ Mm,n (Z) ekvivalens matrixok ´ es ´ legyenek P ∈ GLm (Z), Q ∈ GLn (Z) unimodularis ´ matrixok ´ melyekkel P AQ = B. Definialjuk ´ n n a f : Z / hAi → Z / hBi lekepez ´ est ´ a k¨ovetkezok ˝ eppen: ´ f ((x1 , . . . , xn ) + hAi) = (x1 , . . . , xn )Q + hBi . Ekkor f egy izomorfizmus, tehat ´ a Zn / hAi es ´ Zn / hBi csoportok izomorfak. ´ . Az 1.4.2 lemma szerint, hP AQi = hAQi, ez´ert feltehetjuk, B IZONY´I T AS ¨ hogy P egy egys´egmatrix, ´ e´ s AQ = B, ahol Q egy unimodularis ´ matrix. ´ Definialjuk ´ n n ¯ az f : Z → Z lek´epez´est a k¨ovetkez˝ok´eppen: x = (x1 , . . . , xn ) eset´en legyen f¯(x) = xQ. Mivel a matrixszorz ´ as ´ linearis, ´ f¯ egy endomorfizmus. Ha y ∈ Zn , akkor y = f¯(yQ−1 ), tehat ´ f¯ szurjekt´ ¨ ıv. Ha f¯(x) = f¯(y), akkor xQ = yQ, tehat ´ −1 ¯ ¯ xQQ = y, azaz x = y. Tehat, ´ f injekt´ıv, azaz f egy automorfizmus. Mivel, ¯ ¯ f (hAi) = hAQi = hBi, ez´ert f -b˝ol szarmaztathat ´ o´ az f : Zn / hAi → Zn / hBi izomorfizmus: f (x + hAi) = f¯(x) + hBi (igazoljuk gyakorlatk´ent, hogy f jol ´ definialt ´ n n ∼ ´ ıtas ´ aban ´ szerepl˝o e´ s t´enyleg izomorfizmus). Tehat ´ Z / hAi = Z / hBi e´ s a t´etel all´ f lek´epez´es valoban ´ izomorfizmus. 2 P´elda 1.9.6 Tekintsuk ¨ az alabbi ´ Abel-csoportot: G = ha, b, c | 4b + c = 0, 3a − 2b − c = 0, 3a − 4b − c = 0i .
(1.4)
3 ´ szerepl˝o matrix. ´ Vegyuk ¨ e´ szre, hogy G ∼ = Z / hMi ahol M a 1.7.3 p´eldaban Hasznaljuk ´ tovabb ´ ebben a p´eldaban ´ a 1.7.3 p´elda jel¨ol´eseit. Kiszamoltuk, ´ hogy
1 0 0 1 0 2 0 4 1 1 −1 2 P MQ = 1 3 = 0 1 0 = S, 0 0 3 −2 −1 1 0 0 0 6 −4 1 −12 3 −4 −1 −2 3 −5
tehat ´ az M matrix ´ ekvivalens a fenti egyenlet jobb oldalan ´ szerepl˝o S matrix´ 3 3 3 ∼ ∼ szal. Az 1.9.5 t´etel miatt, G = Z / hMi = Z / hSi. A Z / hSi csoportot a k¨ovetkez˝ok´eppen adhatjuk meg: Z3 / hSi = hx, y, z | x = 0, y = 0, 6z = 0i ∼ = Z6 . = hz | 6z = 0i ∼ Jegyzet friss´ ıtve:
2006. december 12.
(1.5)
34
Abel-csoportok
´ hogy a G csoportnak valoj ´ aban ´ egyszeru ˝ a struktur ´ aja, ´ Tehat ´ G∼ = Z6 . Latjuk, azonban ez a csoport eredeti (1.4) megadas ´ ab ´ ol ´ nem felt´etlen derul ¨ ki. Az 1.9.5 t´etel szerint a G csoport (1.4) e´ s (1.5) alakjai k¨oz¨ott a Q matrix ´ adja meg a kapcsolatot. Valoban, ´ n´emi munkaval ´ ellen˝orizhet˝o, hogy az f : a 7→ 1x + 2z = 2z, b 7→ y + 3z = 3z, c 7→ −4x + y − 12z = −12z = 0 lek´epez´es kiterjeszthet˝o az (1.4) e´ s (1.5) csoportok k¨oz¨otti izomorfizmussa. ´ Mivel a (1.5) csoport ciklikus, a (1.4) csoport is az kell, hogy legyen. Valoban, ´ mivel, f (−a + b) = −2z + 3z = z, ´ıgy az (1.4) csoportot a −b + c elem generalja. ´ Az (1.9.5) t´etel miatt, elemi sor- e´ s oszlopmuveletek ˝ nem valtoztatj ´ ak ´ meg a matrixhoz ´ tartozo´ elemi Abel-csoport izomorfia osztaly ´ at. ´ Ezeken k´ıvul ¨ m´eg egy muveletet ˝ v´egezhetunk ¨ a matrixunkkal ´ az izomorfia osztaly ´ megvaltoz´ tatasa ´ n´elkul. ¨ Lemma 1.9.7 Legyen A ∈ Mm,n (Z), es ´ legyen Aˆ ∈ Mm+1,n+1 (Z) az alabbi ´ matrix: ´
D E n+1 Ekkor Zn / hAi ∼ = Z / Aˆ .
1 0 ··· 0 0 . .. . A 0
´ . Legyenek Ai,j az A matrix B IZONY´I T AS ´ elemei. A Zn / hAi csoport nem mas ´ mint
a1 , . . . , an | A1,1 a1 + · · · + A1,n an = 0, . . . , Am,1 a1 + · · · + Am,n an = 0 ,
n+1
m´ıg a Z
D E / Aˆ csoport fel´ırhato´ a k¨ovetkez˝o alakban:
a0 , a1 , . . . , an | a0 = 0, A1,1 a1 + · · · + A1,n an = 0, . . . , Am,1 a1 + · · · + Am,n an = 0 .
A k´et prezentaci ´ ob ´ ol ´ latszik, ´ hogy a k´et csoport egymassal ´ term´eszetesen izomorf. 2 Jegyzet friss´ ıtve:
2006. december 12.
´ Csoportelmeleti algoritmusok
35
1.10. V´egesen gener´alt Abel-csoportok alapt´etele Ebben a fejezetben belatjuk, ´ hogy minden v´egesen generalt ´ Abel-csoport megadhato´ egy kanonikus alakban. A kanonikus alak a Smith normal ´ formaval ´ mutat majd hasonlos ´ agot. ´ Lemma 1.10.1 Legyen M ∈ Mn,n (Z). Ha det M 6= 0, akkor |Zn / hMi | = | det M|, m´ıg det M = 0 eseten ´ Zn / hMi egy vegtelen ´ csoport. ´ . Legyen A az M-mel ekvivalens SNF matrix. B IZONY´I T AS ´ Ekkor l´eteznek P, Q ∈ GLn (Z) unimodularis ´ matrixok ´ melyekkel A = P MQ e´ s det A = (det P )(det M)(det Q) = | det M| teljesul. ¨ Legyenek a1 , . . . , ak az A nem-nulla diagonalis ´ elemei. Ekkor n−k Zn / hAi ∼ = Za1 ⊕ · · · ⊕ Zak ⊕ Z .
Ha det M 6= 0, akkor det A 6= 0 e´ s ´ıgy az A matrix ´ minden diagonalis ´ eleme nem-nulla, azaz k = n. Ekkor |Zn / hMi | = |Zn / hAi | = a1 · · · an = det A = | det M|. Ha det M = 0, akkor det A = 0, e´ s ´ıgy az A atl ´ oj ´ aban ´ van nulla-elem, azaz, k < n. n n Ebben az esetben a Z / hAi fenti fel´ırasa ´ miatt, Z / hAi egy v´egtelen csoport, e´ s n ´ıgy a Z / hMi is az. 2 Legyen G egy Abel-csoport. Ha x, y ∈ G e´ s α, β ∈ Z melyekkel αx = βy = 0, akkor nyilvan ´ αβ(x + y) = 0. Tehat ´ G-ben a v´egesrendu ˝ elemek egy r´eszcsoportot alkotnak. Ennek a r´eszcsoportnak a neve G-beli torziocsoport, ´ jele pedig T (G). T´etel 1.10.2 (V´egesen gener´alt Abel-csoportok alapt´etele) Minden vegesen ´ generalt ´ Abel-csoport fel´ırhato´ Zn1 ⊕ Zn2 ⊕ · · · ⊕ Znk ⊕ Zs
(1.6)
alakban, ahol s > 0, ni > 2 es, ´ i ∈ {1, . . . , k − 1} eseten, ´ ni |ni+1 . Tovabb ´ a, ´ ezekkel a feltetelekkel ´ a (1.6) fel´ıras ´ egyertelm ´ u. ˝ Jegyzet friss´ ıtve:
2006. december 12.
36
Abel-csoportok
´ . Legyen G egy n elem altal B IZONY´I T AS ´ generalt ´ Abel-csoport. Ekkor az 1.9.1 n lemma szerint G ∼ = Z / hMi, ahol M ∈ Mm,n (Z). Jel¨olje A az M-mel ekvivalens SNF matrixot, ´ e´ s legyenek a1 , . . . , ak az A nullat ´ ol ´ kul¨ ¨ onb¨oz˝o diagonalis ´ elemei. Ekkor n n n−k G∼ = Z / hMi = Z / hAi ∼ = Za1 ⊕ · · · ⊕ Zak ⊕ Z . Mivel A egy SNF matrix, ´ a fenti fel´ırasb ´ ol ´ a Z1 faktorokat elhagyva kapjuk a k´ıvant ´ felbontast. ´ Igazoljuk, most a felbontas ´ egy´ertelmus´ ˝ eg´et. Az egy´ertelmus´ ˝ eget el˝osz¨or v´eges csoportokra mutatjuk meg. Tegyuk ¨ fel, hogy G∼ = Zm1 ⊕ Zm2 ⊕ · · · ⊕ Zmℓ , = Zn1 ⊕ Zn2 ⊕ · · · ⊕ Znk ∼ ahol az ni e´ s az mj szamok ´ kiel´eg´ıtik a t´etel felt´eteleit. Az altal ´ anoss ´ ag ´ megs´ert´ese n´elkul ¨ tegyuk ¨ fel, hogy ℓ 6 k, e´ s legyen A ∈ Mk,k (Z) az az diagonalis ´ matrix ´ melynek atl ´ obeli ´ elemei n1 , . . . , nk , B ∈ Mk,k (Z) pedig legyen az a diagonalis ´ matrix ´ melynek atl ´ obeli ´ elemei 1, . . . , 1, m1 , . . . , mℓ (a vezet˝o egyesek szama ´ k − ℓ). Jel¨olj´ek r1 , . . . , rk a B diagonalis ´ matrix ´ atl ´ obeli ´ elemeit. Legyen k k G1 = Z / hAi e´ s G2 = Z / hBi. Megjegyezzuk, ¨ hogy A is e´ s B is SNF matrixok, ´ e´ s a 1.9.7 lemma miatt, k G1 = Zk / hAi ∼ = Z / hBi = G2 ,
´ıgy l´etezik egy ϕ : Zk / hAi → Zk / hBi izomorfizmus. Mivel, az A matrix ´ diagonalis, ´ a G1 csoportnak l´etezik egy x1 , . . . , xk generator-rendszere, ´ mellyel G1 = hx1 i ⊕ · · · ⊕ hxk i ∼ = Zn1 ⊕ · · · ⊕ Znk . Hasonloan, ´ a G2 csoportban l´etezik egy y1 , . . . , yk generator-rendszer ´ melyre G2 = hy1 i ⊕ · · · ⊕ hyk i ∼ = Zr1 ⊕ · · · ⊕ Zrk
teljesul. ¨ Tegyuk ¨ fel, hogy i, j ∈ {1, . . . , k} eset´en, qi,j ∈ Z olyan szamok ´ melyekre ϕ (xi ) = qi,1 y1 + · · · + qi,k yk . Legyen Q a (qi,j ) matrix. ´ Ekkor G2 = ϕ(G1 ) = hϕ(x1 )i ⊕ · · · ⊕ hϕ(xk )i
= q1,1 y1 + · · · + q1,k yk ⊕ · · · ⊕ qk,1 y1 + · · · + qk,k yk ∼ = Zn1 ⊕ · · · ⊕ Znk . Jegyzet friss´ ıtve:
2006. december 12.
´ Csoportelmeleti algoritmusok
37
Mivel a G2 = ϕ(G1 ) csoport a ϕ(xi ) = qi,1 y1 + · · · + qi,k yk elemek altal ´ generalt ´ ciklikus csoportok direkt o¨ sszege, e´ s ezeknek a ciklikus csoportoknak a rendje ni , a G2 csoportot megadhatjuk a k¨ovetkez˝ok´eppen:
G2 = y1 , . . . , yk | n1 q1,1 y1 + · · · + n1 q1,k yk = 0, . . . , nk qk,1 y1 + · · · + nk qk,k yk = 0 .
´ Eszrevessz uk, ¨ hogy a ni qi,j elemek altal ´ alkotott matrix ´ megegyezik az AQ k matrixszal, ´ tehat ´ G2 ∼ = Z / hAQi. Mivel G2 v´eges, ´ıgy a 1.10.1 lemma miatt, | det A|| det Q| = | det(AQ)| = |G2 | = |G1 | = | det A|, e´ s ´ıgy Q egy unimodularis ´ matrix. ´ k k Legyen ψ : Z → Z az a linearis ´ transformaci ´ o´ melyre a ∈ Zk eset´en ψ(a) = aQ. Mivel Q unimodularis, ´ az 1.9.5 t´etel bizony´ıtas ´ aban ´ latott ´ modon ´ igazolhatjuk, hogy ψ egy izomorfizmus. Ha a ∈ hAi, akkor a + hAi = 0 + hAi, e´ s ez´ert 0 + hBi = ϕ(0 + hAi) = ϕ(a + hAi) = aQ + hBi = ψ(a) + hBi , tehat ´ ψ(a) ∈ hBi, e´ s ´ıgy ψ(hAi) 6 hBi. Tovabb ´ a´ a |Zk / hAi | = |Zk / hBi | egyenl˝os´eg miatt, |Zk : ψ(hAi)| = |Zk : hAi | = |Zk : hBi |, tehat ´ ψ(hAi) = hBi. Mivel hBi = ψ(hAi) = hAQi, ez´ert, az 1.5.8 t´etel miatt, AQ ekvivalens a B matrixszal, ´ e´ s ´ıgy a 1.7.1 lemma miatt A e´ s B ekvivalensek. Mivel mindk´et matrix ´ SNF alaku, ´ A = B, amib˝ol, 1 6 i 6 k eset´en, ni = ri k¨ovetkezik. K¨ovetkez´esk´epp az ri -k k¨oz¨ott nincsenek egyesek, e´ s ´ıgy ni = mi minden i-re. Tehat ´ a t´etelben szerepl˝o fel´ıras ´ v´eges csoportok eset´en egy´ertelmu. ˝ Tegyuk ¨ most fel, hogy G egy nem felt´etlenul ¨ v´eges csoport e´ s G felbonthato´ k´etf´elek´eppen: s Zn1 ⊕ Zn2 ⊕ · · · ⊕ Znk ⊕ Zr ∼ = Zm1 ⊕ Zm2 ⊕ · · · ⊕ Zmℓ ⊕ Z .
A Zn1 ⊕ Zn2 ⊕ · · · ⊕ Znk ⊕ Zr csoport egy (x1 , . . . , xk , xk+1 , . . . , xk+r ) eleme pontosan akkor v´eges rendu, ˝ ha xk+1 = · · · = xk+r = 0. Tehat ´ T (G) ∼ = Zn1 ⊕ Zn2 ⊕ · · · ⊕ Znk , ∼ illetve hasonloan ´ kapjuk, hogy T (G) = Zm1 ⊕ Zm2 ⊕ · · · ⊕ Zmℓ , amib˝ol a fentiek miatt k = ℓ e´ s ni = mi k¨ovetkezik. Masr´ ´ eszr˝ol viszont r s G/T (G) ∼ =Z ∼ =Z,
Jegyzet friss´ ıtve:
2006. december 12.
38
Abel-csoportok
a 1.2.6 lemma pedig adja, hogy r = s. 2 Vizsgaljuk ´ meg, az 1.9.2–1.9.4 p´eldakban ´ szerepl˝o Abel-csoportokat az 1.10.2 szempontjab ´ ol. ´ P´elda 1.10.3 Az 1.9.2 t´etelben szerepl˝o G Abel-csoport Z3 ⊕Z5 ⊕Z fel´ırasa ´ nem felel meg a 1.10.2 t´etel felt´eteleinek. Legyenek, sorrendben, a, b, e´ s c a fenti felbontasban ´ szerepl˝o Z3 , Z5 e´ s a Z csoportok generatorai. ´ Az a + b elem rendje 15, ami megegyezik a Z3 ⊕Z5 = hai⊕hbi csoport rendj´evel, tehat ´ Z3 ⊕Z5 = ha + bi, e´ s ´ıgy G = ha + bi ⊕ Z ∼ ´ fel´ıras ´ mar ´ pontosan olyan mint az = Z15 ⊕ Z. Ez utobbi alapt´etelben szerepl˝o. P´elda 1.10.4 Szam´ ´ ıtsuk ki az 1.9.3 p´eldaban ´ szerepl˝o Aa,b,c e´ s B a,b,c csoportok kanonikus alakjat. ´ Az 1.10.2 t´etel szerint, ehhez meg kell hataroznunk ´ a p´eldakban ´ szerepl˝o A e´ s B matrixokhoz ´ tartozo´ SNF matrixokat. ´ Legyen S az A matrixhoz ´ tartozo´ SNF matrix, ´ e´ s legyenek s1 , s2 az A matrix ´ atl ´ obeli ´ elemei. Az 1.8.1 lemma e´ s az 1.8.2 k¨ovetkezm´eny szerint, s1 megegyezik az A matrix ´ elemeinek legnagyobb k¨oz¨os osztoj ´ aval, ´ az s2 pedig az A matrix ´ determinans ´ aval. ´ Ez´ert, s1 = 1 e´ s s2 = 2(a + b + c), az A matrix ´ pedig ekvivalens a k¨ovetkez˝o SNF matrixszal: ´ ! 1 0 S= . 0 2(a + b + c) K¨ovetkez´esk´epp, ha a + b + c 6= 0, akkor Aa,b,c ∼ = Z2(a+b+c) , ha pedig a + b + c = 0, a,b,c ∼ akkor A ´ ha a + b + c = 0, akkor F a,b,c egy v´egtelen csoport. = Z. Specialisan, Az eredeti A matrixb ´ ol ´ azt is le lehet olvasni, hogy az a + b + c = 0 esetben az a,b,c F -beli s elem v´egtelen rendu. ˝ Legyen most R a B-vel ekvivalens SNF matrix, ´ e´ s legyenek r1 e´ s r2 az R atl ´ obeli ´ elemei. Az el˝oz˝o bekezd´eshez hasonloan ´ kapjuk, hogy r1 = 1, r2 pedig a B-beli (2 × 2)-es aldeterminansok ´ legnagyobb k¨oz¨os osztoja. ´ Azaz, r2 = gcd(4(a + b + c), 2(a + b + c), 6(a + b + c)) = 2(a + b + c). Azaz B ekvivalens az 1 0 R = 0 2(a + b + c) . 0 0 a,b,c matrixszal, ´ e´ s ´ıgy minden a, b, c param´eter eset´en fennall, ´ hogy Aa,b,c ∼ =B .
Jegyzet friss´ ıtve:
2006. december 12.
´ Csoportelmeleti algoritmusok
39
P´elda 1.10.5 Tekintsuk ¨ most az 1.9.4 p´eldaban ´ szerepl˝o A(l, m, n) csoportot. Legyen S az A matrixszal ´ ekvivalens SNF matrix, ´ e´ s legyenek s1 , s2 , s3 az S atl ´ obeli ´ elemei. Az 1.8.1 lemmab ´ ol ´ e´ s az 1.8.2 k¨ovetkezm´enyb˝ol azt kapjuk, hogy s1 = gcd(2, l, m, n), s2 e´ s s3 pedig kiszam´ ´ ıthatok ´ az A-beli (2 × 2)es e´ s (3 × 3)-as aldeterminansok ´ legnagyobb k¨oz¨os osztoj ´ ab ´ ol. ´ Az aldeterminansokat ´ vizsgalva ´ kapjuk, hogy s2 = gcd(4, 2l, 2m, 2n, lm, ln, mn)/s1 e´ s s3 = gcd(8, 4l, 4m, 4n, 2lm, 2ln, 2mn, 2lmn)/(s1s2 ). Tehat ´ ( 1, ha l, m, e´ s n k¨ozul ¨ legalabb ´ egy paratlan; ´ s1 = 2, ha l, m, e´ s n k¨ozul ¨ mindegyik paros; ´ e´ s s2 =
(
1, ha l, m, e´ s n k¨ozul ¨ legalabb ´ kett˝o paratlan; ´ 2, ha l, m, e´ s n k¨ozul ¨ legfeljebb egy paratlan. ´
Hasonlo´ megfontolasokb ´ ol ´ kapjuk, hogy s3 = 2. Mivel, A(l, m, n) ∼ = Zs1 ⊕Zs2 ⊕Zs3 , a A(l, m, n) csoportra azt kapjuk, hogy ha l, m, e´ s n k¨ozul ¨ legalabb ´ kett˝o paratlan; ´ Z2 , A(l, m, n) ∼ = Z2 ⊕ Z2 , ha l, m, e´ s n k¨ozul ¨ pontosan egy paratlan; ´ Z2 ⊕ Z2 ⊕ Z2 ha l, m, e´ s n k¨ozul ¨ mindegyik paros. ´
Tehat, ´ az A(l, m, n) csoport minden esetben egy nemtrivialis ´ v´eges csoport, melynek rendje, az l, m, e´ s n param´eterekt˝ol fugg˝ ¨ oen, 2, 4, vagy 8.
1.11. Modul´aris HNF e´ s SNF Ebben a fejezetben egy olyan technikat ´ ismertetunk, ¨ mellyel a 1.5.3 t´etel el˝ott ismertetett jelens´eg, nevezetesen, hogy a HNF szam´ ´ ıtasa ´ soran ´ a k¨ozbuls˝ ¨ o matrixok ´ elemei kezelhetetlenul ¨ nagyok lesznek, elkerulhet˝ ¨ o. A Hermite normal ´ format ´ szam´ ´ ıto´ 1. algoritmus e´ s az 1.7.2 t´etel bizony´ıtas ´ aban ´ szerepl˝o Smith normal ´ format ´ szam´ ´ ıto´ algoritmus inkabb ´ csak elm´eleti jelent˝os´egu, ˝ a gyakorlatban el˝ofordulo´ probl´emakra ´ egyik sem igazan ´ alkalmazhato. ´ P´eldaul, ´ a Smith normal ´ formara ´ vonatkozo´ algoritmus, mar ´ (20 × 20)-as egyszamjegy ´ u ˝ elemeket tartalmazo´ input matrix ´ eset´en sem praktikus, mivel a szam´ ´ ıtas ´ soran ´ a matrixban ´ akar ´ t¨obb szazezer ´ szamjegy ´ u ˝ elemek is keletkeznek. Az Jegyzet friss´ ıtve:
2006. december 12.
40
Abel-csoportok
output matrix ´ azonban mindk´et algoritmus eset´en viszonylag kis elemekb˝ol all. ´ Term´eszetes tehat, ´ hogy megprob ´ aljuk ´ a HNF e´ s SNF matrixokat ´ modulo´ valamilyen jol ´ megvalasztott ´ eg´esz szam ´ szerint szam´ ´ ıtani. Ehhez a strat´egiahoz ´ tartalmaz n´ehany ´ o¨ tletet a jelen fejezet. Egy korabbi ´ defin´ıcio´ szerint, ha A ∈ Mm,n (Z) e´ s k 6 min{m, n}, akkor δk (M) jel¨oli az M-beli (k × k)-s aldeterminansok ´ legnagyobb k¨oz¨os osztoj ´ at. ´ Eml´ekezzunk ¨ tovabb ´ a, ´ hogy az M-mel ekvivalens SNF matrix ´ diagonalis ´ elemeit az M invarians ´ faktorainak nevezzuk ¨ e´ s az invarians ´ faktorok meghatarozhat ´ ok ´ a δk mennyis´egekb˝ol az 1.8.2 k¨ovetkezm´enyben latott ´ modon. ´ Legyen M egy eg´esz e´ rt´eku ˝ matrix ´ e´ s tegyuk ¨ fel, hogy meg szeretn´enk hatarozni ´ M Smith normal ´ formaj ´ at. ´ A SNFben talalhat ´ o´ nem-nulla elemek szam ´ at ´ az alabbi ´ lemma alapjan ´ el˝ojelezhetjuk. ¨ Lemma 1.11.1 Ha M egy egesz ´ matrix, ´ akkor rang M megegyezik az M nem nulla invarians ´ faktorainak a szam ´ aval. ´ ´ . Az M rangja pontosan akkor r, ha M-ben van (r × r)-es nem nulla B IZONY´I T AS aldeterminans, ´ de nincs enn´el nagyobb. Mas ´ szoval, ´ δr (M) 6= 0, de, minden k > r eset´en, δk (M) = 0. A 1.8.2 k¨ovetkezm´eny miatt, ekkor r pontosan a nem nulla invarians ´ faktorok szama. ´ 2 A bevezet´esben eml´ıtettuk, ¨ hogy a HNF e´ s SNF matrixokat ´ modulo´ egy jol ´ megvalasztott ´ eg´esz szam ´ szerint szam´ ´ ıtjuk. A k¨ovetkez˝o lemma seg´ıt a modulus megvalaszt ´ as ´ aban ´ Lemma 1.11.2 (Hadamard korl´at) Ha A ∈ Mn,n (R), akkor | det A| 6
n n Y X i=1
Ai,j
j=1
2
!1/2
.
Eg´esz matrixok ´ eset´en az el˝oz˝o lemmab ´ ol ´ a k¨ovetkezik az alabbi ´ all´ ´ ıtas. ´ K¨ ovetkezm´eny 1.11.3 Ha m 6 n es ´ A ∈ Mm,n (Z), akkor egy A-beli aldeterminans ´ abszolut ´ ert ´ eke ´ az alabbi ´ ert ´ ekek ´ egyiket ´ ol ˝ sem nagyobb: !1/2 !1/2 m n m Y X X 2 2 max , Ai,j es ´ Ai,j i
j=1
Jegyzet friss´ ıtve:
j
i=1
2006. december 12.
´ Csoportelmeleti algoritmusok
41
ahol a szorzat a matrix ´ nem-nulla soraira t¨ortenik. ´ Ha m 6 n e´ s A ∈ Mm,n (Z), akkor az el˝oz˝o k¨ovetkezm´enyben szerepl˝o korlatot ´ az A matrixra ´ vonatkozo´ Hadamard korlatnak ´ mondjuk. Ha m > n, akkor az A-ra vonatkozo´ Hadamard korlat, ´ defin´ıcio´ szerint, megegyezik az A transzponaltj ´ ara ´ vonatkozo´ 1.11.3 k¨ovetkezm´eny szerinti korlattal. ´ Ha n e´ s k tetsz˝oleges eg´esz szamok, ´ akkor jel¨olje [k]n azt az egyetlen 0 e´ s n − 1 k¨oz¨otti eg´esz szamot ´ melyre [k]n ≡ k mod n teljesul. ¨ A [k]n szamot ´ a k szam ´ n szerinti redukaltj ´ anak ´ mondjuk. Egy R gyur ˝ u ˝ eset´en, az R egys´egeit, mas ´ szoval ´ invertalhat ´ o´ elemeit, az U(R) szimbolum ´ jel¨oli. Egy n pozit´ıv eg´esz szam ´ eset´en, tekintsuk ¨ most a Zn halmazt gyur ˝ uk´ ˝ ent, e´ s jel¨oljuk ¨ elemeit a 0 e´ s n − 1 k¨oz¨otti eg´esz szamokkal. ´ Ha k ∈ Z, akkor a [k]n szamot ´ ´ıgy tekinthetjuk, ¨ mint a Zn gyur ˝ u ˝ elem´et. Jol ´ ismert, hogy a Zn gyur ˝ uben ˝ egy [k]n elem egys´eg, akkor e´ s csakis akkor, ha gcd(k, n) = 1. Lemma 1.11.4 Legyenek n es ´ m egeszek, ´ melyekre n | m teljesul ¨ es ´ legyen fm,n : Zm → Zn az a lekepez ´ es ´ melyre k ∈ Z eseten ´ fm,n ([k]m ) = [k]n . Ekkor fm,n egy jol ´ definialt ´ epimorfizmus es ´ fm,n (U(Zm )) = U(Zn ). ´ . A lemma els˝o all´ B IZONY´I T AS ´ ıtasa ´ egyszeruen ˝ ellen˝orizhet˝o, ´ıgy azt nem bizony´ıtjuk. Legyen u ∈ U(Zm ). Ekkor, a fentiek miatt, gcd(u, m) = 1, e´ s ´ıgy gcd(u, n) = 1, tehat, ´ [u]n ∈ U(Zn ). ´Igy fm,n (U(Zm )) ⊆ U(Zn ). Jel¨olje, f¯m,n a fm,n |U (Zm ) lek´epez´est. Be kell latnunk, ´ hogy f¯m,n : U(Zm ) → U(Zn ) szurjekt´ ¨ ıv. Az all´ ´ ıtast ´ m/n szerinti indukcioval ´ igazoljuk. Nyilvan, ´ m/n = 1 eset´en az all´ ´ ıtas ´ ¯ ¯ ¯ igaz. Ha l ∈ Z olyan szam ´ melyre n | l e´ s l | m teljesul, ¨ akkor fm,n a fm,l e´ s fl,n homomorfizmusok kompoz´ıcioja. ´ Mivel, az indukcios ´ feltev´es miatt, f¯m,l e´ s f¯l,n szurjekt´ ¨ ıvek, f¯m,n is az. A f¯m,n lek´epez´es szurjektivit ¨ as ´ at ´ ´ıgy most abban az esetben kell igazolnunk, amikor m/n egy p pr´ım. Legyen u ∈ U(Zn ), azaz gcd(u, n) = 1. Ha p | n, akkor gcd(u, m) = 1 k¨ovetkezik, e´ s ´ıgy u ∈ U(Zm ) e´ s u ∈ f¯m,n (U(Zm )). Ha p ∤ n, akkor a k´ınai marad´ekt´etel k¨ovetkezt´eben a k¨ovetkez˝o szimultan ´ kongruenciarendszer megoldhato: ´ a ≡ u mod n
a ≡ 1 mod p. Jegyzet friss´ ıtve:
2006. december 12.
42
Abel-csoportok
Ekkor gcd(a, n) = 1 e´ s gcd(a, p) = 1 tehat, ´ gcd(a, m) = 1 azaz, [a]m ∈ U(Zm ) e´ s f ([a]m ) = [a]n = u. Tehat, ´ u ∈ f¯m,n (U(Zm )), e´ s ´ıgy f¯m,n valoban ´ szurjekt´ ¨ ıv. 2 Legyen A ∈ Mm,n (Z) e´ s legyen r az A matrix ´ rangja. Ekkor az A matrixnak ´ pontosan r nem-nulla invarians ´ faktora van, e´ s a legnagyobb is legfeljebb δr (M). Tehat, ´ ha d a δr (M) egy tetsz˝oleges t¨obbsz¨or¨ose, akkor elegend˝o az invarians ´ faktorok d szerinti marad´ekosztalyait ´ meghatarozni. ´ A δr (M) szam ´ egy t¨obbsz¨or¨os´et talalhatunk ´ p´eldaul ´ ugy, ´ hogy keresunk ¨ n´ehany ´ nem-nulla M-beli (r×r)-s aldeterminanst, ´ e´ s kiszamoljuk ´ azok legnagyobb k¨oz¨os osztoj ´ at. ´ A k¨ovetkez˝okben azt targyaljuk, ´ hogyan lehet, ilyen aldeterminansokat ´ talalni. ´ Ha M ∈ Mm,n (Z), akkor jel¨olje [M]d azt a matrixot ´ melyet ugy ´ kapunk, hogy M minden elem´et redukaljuk ´ d szerint. Az alabbi ´ sormuveleteket ˝ modulo´ d elemi sormuveleteknek ˝ h´ıvjuk: (i) k´et sor felcser´el´ese; (ii) egy sor szorzasa ´ egy d-hez relat´ıv pr´ım eg´esszel; (iii) egy sor eg´esz t¨obbsz¨or¨os´enek hozzaad ´ asa ´ egy masik ´ sorhoz. A fenti sormuveleteket ˝ modulo´ d v´egezzuk, ¨ azaz, a sormuveletek ˝ elv´egz´ese utan ´ a kiszam´ ´ ıtjuk matrixelemek ´ d szerinti redukaltj ´ at. ´ K´et matrixot ´ sorekvivalensnek mondunk modulo´ d, ha a masodik ´ megkaphato´ az els˝ob˝ol modulo´ d elemi sormuveletek ˝ seg´ıts´eg´evel. Azt mondjuk, hogy egy A ∈ Mm,n (Z) matrix ´ Hermite normal ´ formaban ´ van modulo´ d, ha (i) A = [A]d ; (ii) A HNF matrix; ´ (iii) az A soraiban a vez´erelemek osztjak ´ d-t. T´etel 1.11.5 A modulo´ d sor-ekvivalencia egy ekvivalencia relaci ´ o´ az Mm,n (Z) halmazon. Tovabb ´ a, ´ minden matrix ´ sor-ekvivalens modulo´ d pontosan egy modulo´ d HNF matrixszal. ´ ´ . Az els˝o all´ B IZONY´I T AS ´ ıtas ´ igazolasa, ´ l´enyeg´eben a 1.4.2 els˝o all´ ´ ıtas ´ anak ´ bizony´ıtas ´ aval ´ egyezik meg. Az egyetlen elt´er´es, hogy ha c a d-hez relat´ıv pr´ım, Jegyzet friss´ ıtve:
2006. december 12.
´ Csoportelmeleti algoritmusok
43
akkor c-nak l´etezik inverze modulo´ d, tehat ´ egy sor c-vel valo´ szorzasa ´ invertalhat ´ o´ muvelet ˝ modulo´ d. A masodik ´ all´ ´ ıtast ´ a 1.5.4 e´ s a 1.5.9 k¨ovetkezm´enyekhez hasonloan ´ bizony´ıtjuk. Az egyetlen l´enyeges kul¨ ¨ onbs´eg, hogy a vez´erelemek d osztoi ´ kell, hogy legyenek. Tegyuk ¨ fel, hogy a az i-dik sor vez´ereleme e´ s a ∤ d. Ekkor 0 < a < d e´ s a = uv, ahol u = gcd(a, d) e´ s, mivel gcd(a/ gcd(a, d), d/ gcd(a, d)) = 1, kapjuk, hogy gcd(v, d/u) = 1. Tehat ´ v invertalhat ´ o´ modulo´ d/u e´ s ´ıgy l´etezik egy w ∈ Z melyre wv ≡ 1 (mod d/u) tejlesul. ¨ Ekkor w egys´eg a Zd/u gyur ˝ uben, ˝ ez´ert a 1.11.4 lemma miatt feltehetjuk, ¨ hogy w egys´eg Zd -ben, azaz gcd(w, d) = 1. Ebben az esetben aw = uvw ≡ u (mod d), ´ıgy ha az i-dik sort w-vel szorozzuk e´ s d szerint redukaljuk, ´ akkor a sor vez´ereleme u lesz, ami a felt´etelek szerint osztoja ´ d-nek. 2 Legyen M ∈ Mm,n (Z) e´ s legyen d egy eg´esz szam. ´ Jel¨olje A az M matrixszal ´ modulo´ d sor-ekvivalens HNF matrixot. ´ Az A matrixban ´ l´ev˝o nem-nulla sorok szama ´ az M matrix ´ d-rangja. A d-rang jele rangd M. Mivel egy matrix ´ rangja megegyezik a vele sor-ekvivalens, HNF matrix ´ nem nulla sorainak a szam ´ aval ´ (1.5.5 t´etel), k¨ovetkezik, hogy rang d M 6 rang M. Egy matrix ´ d-rangjat ´ meghatarozhatjuk ´ modularis ´ aritmetika seg´ıts´eg´evel, ´ıgy a szamol ´ as ´ soran ´ csak olyan eg´eszekkel kell dolgoznunk melyek abszolut ´ e´ rt´eke legfeljebb d. Ha d-t egy el´eg nagy pr´ımnek valasztjuk, ´ akkor nagy valosz´ ´ ınus´ ˝ eggel a d-rang megegyezik a ranggal. A k¨ovetkez˝okben azt vizsgaljuk, ´ hogyan valasszuk ´ meg a d szamot, ´ hogy ebben biztosak legyunk. ¨ Lemma 1.11.6 Legyen A ∈ Mm,n (Z) es ´ legyenek p1 , . . . , ps kul¨ ¨ onb¨ozo˝ pr´ımek, melyekre teljesul, ¨ hogy p1 · · · ps nagyobb mint az A-ra vonatkozo´ Hadamard korlat. ´ Ekkor rang A = maxi rangpi A. ´ . Legyen r = maxi rangpi A e´ s legyen K a 1.11.3 k¨ovetkezm´enybeli B IZONY´I T AS korlat. ´ Legyen C egy A-beli n´egyzetes almatrix ´ melyben a sorok szama ´ t¨obb mint r. Ekkor, minden i eset´en, det C ≡ 0 (mod pi ) e´ s ´ıgy det C ≡ 0 (mod p1 · · · ps ). Mivel | det C| 6 K < p1 · · · ps , ´ıgy kapjuk, hogy det C = 0. Tehat ´ az M matrix ´ rangja legfeljebb r. Tegyuk ¨ fel, hogy rangpi = r. Ekkor lemma el˝otti bekezd´esben mondottak miatt, rang A > r, ez´ert az A rangja pontosan r. 2 Az el˝oz˝o lemma seg´ıts´eg´evel k¨onnyen meghatarozhatjuk ´ egy A eg´esz matrix ´ Jegyzet friss´ ıtve:
2006. december 12.
44
Abel-csoportok
rangjat: ´ meghatarozunk ´ elegend˝oen sok pi pr´ım szamot, ´ e´ s kiszam´ ´ ıtjuk a pi rangokat. A k¨ovetkez˝o lemma egy hasonlo´ o¨ tletet tartalmaz a determinans ´ kiszam´ ´ ıtas ´ ara. ´ Lemma 1.11.7 Legyen A ∈ Mn,n (Z) es ´ legyenek p1 , . . . , ps kul¨ ¨ onb¨ozo˝ pr´ımek, melyekre teljesul, ¨ hogy p1 · · · ps nagyobb mint az A-ra vonatkozo´ Hadamard korlat ´ ketszerese. ´ Legyen di = [det A]pi , minden i ∈ {1, . . . , s} eseten. ´ Ekkor det A az a legkisebb abszolut ´ ert ´ ek ´ u˝ d egesz ´ szam ´ melyre d ≡ di (mod pi ) teljesul ¨ minden i ∈ {1, . . . , s} eseten. ´ ´ . A k´ınai marad´ekt´etel szerint az B IZONY´I T AS x ≡ d1 mod p1 .. . x ≡ ds mod ps kongruencia-rendszernek l´etezik x megoldasa, ´ e´ s x egy´ertelmu ˝ modulo´ p1 · · · ps . Ha K jel¨oli a Hadamard korlatot, ´ akkor 2| det A| 6 2K < p1 · · · p2 , e´ s ´ıgy −K e´ s K k¨oz´e a kongruencia-rendszernek legfeljebb egy megoldasa ´ esik, ami megegyezik a det A mennyis´eggel. 2 Az el˝obbi t´etelben szerepl˝o d determinanst ´ meghatarozhatjuk ´ a modulo´ pi marad´ekaibol ´ a k¨ovetkez˝o lemma alapjan. ´ A lemma bizony´ıtas ´ at ´ gyakorlatnak hagyjuk. Lemma 1.11.8 Legyenek p1 , . . . , ps egymast ´ ol ´ kul¨ ¨ onb¨ozo˝ paratlan ´ pr´ımek es ´ legyenek a1 , . . . , as egesz ´ szamok ´ melyekre |ai | < pi /2 teljesul. ¨ Legyen, 2 6 i 6 s eseten ´ qi az a pozit´ıv egesz ´ mely kisebb mint pi es ´ melyre p1 · · · pi−1 qi ≡ 1 (mod pi ) teljesul. ¨ Ekkor a 3 algoritmus outputja az a legkisebb abszolut ´ ert ´ ek ´ u˝ x egesz ´ szam ´ melyre x ≡ ai (mod pi ) teljesul ¨ minden 1 6 i 6 s eseten. ´ Ha p egy pr´ımszam, ´ akkor egy n´egyzetes M matrix ´ determinansa ´ modulo´ p k¨onnyen meghatarozhat ´ o. ´ A matrixot ´ HNF alakra hozzuk, de a HNF alak szam´ ´ ıtasa ´ k¨ozben a k¨ovetkez˝okre ugyel ¨ unk. ¨ A HNF szam´ ´ ıtasa ´ elej´en egy d valtoz ´ ot ´ 1-nek inicializalunk, ´ majd minden sorcsere utan ´ d-t megszorozzuk −1-gyel, illetve, ha egy sort c-vel szorzunk akkor d-t is megszorozzuk c-vel. Jegyzet friss´ ıtve:
2006. december 12.
´ Csoportelmeleti algoritmusok
45
3. algoritmus: S OLVE C HINESE Input: p1 , . . . , ps e´ s a1 , . . . , as (lasd ´ 1.11.8 lemma) Output: x (lasd ´ 1.11.8 lemma) set x := a1 for i ∈ {2, . . . , s} do set y :≡ qi (x − ai ) (mod pi ) e´ s |y| 6 pi /2 set x := x − yp1 · · · pi−1 end for return x Algorithm 3: K´ınai marad´ekt´etel algoritmus Ek¨ozben d-t mindig redukaljuk ´ p szerint. Ha A a HNF alak modulo´ p, akkor [det M]p = [det A]p /d, a det A mennyis´eg pedig egyszeruen ˝ az A matrix ´ diagonalis ´ elemeinek a szorzata. Ezek utan ´ a 1.11.7 lemma alapjan ´ egy n´egyzetes matrix ´ determinansa ´ kiszam´ ´ ıthato. ´ A fentiek alapjan, ´ egy A matrix ´ invarians ´ faktoraira k¨onnyen adhatunk fels˝o korlatot. ´ El˝osz¨or kiszamoljuk ´ az A rangjat ´ az 1.11.6 lemma utan ´ ismertetett modon. ´ Legyen a rang r. Utana ´ keresunk ¨ egy (r × r)-es aldeterminanst. ´ Az 1. algoritmus k¨onnyen modos´ ´ ıthato´ ugy, ´ hogy inputja egy M eg´esz e´ rt´eku ˝ matrix, ´ outputja pedig az M matrix ´ r olyan sora melyek egy r rangu ´ matrixot ´ alkotnak. Utana ´ a transzponaltra ´ lefuttatva ugyanezt az eljar ´ ast, ´ egy (r × r)-es invertalhat ´ o´ almatrixot ´ kapunk. Az ´ıgy kapott almatrix ´ D determinans ´ at ´ kiszam´ ´ ıthatjuk az el˝oz˝o bekezd´esben ismertetett modon. ´ A D szam ´ rendelkezik azzal a tulajdonsaggal, ´ hogy t¨obbsz¨or¨ose az A invarians ´ faktorainak (1.8.2 k¨ovetkezm´eny). Ha D tul ´ nagy, akkor az A sorainak e´ s oszlopainak permutaci ´ oi ´ utan ´ megprob ´ alhatunk ´ meghatarozni ´ mas ´ (r × r)-es aldeterminansokat, ´ e´ s vehetjuk ¨ azok legnagyobb k¨oz¨os osztoj ´ at. ´ Az invarians ´ faktorokat modulo´ D szerint hatarozzuk ´ meg, ahol D az el˝oz˝o bekezd´esben definialt ´ szam. ´ Ehhez elemi sor- e´ s oszlopmuveleteket ˝ hajtunk v´egre modulo´ d. A modulo´ d elemi oszlopmuveletek ˝ a modulo´ d elemi sormuveletek ˝ analogjai. ´ K´et eg´esz matrixot ´ ekvivalensnek mondunk modulo´ Jegyzet friss´ ıtve:
2006. december 12.
46
Abel-csoportok
d, ha a masodik ´ megkaphato´ az els˝ob˝ol modulo´ d sor- e´ s oszlopmuveletek ˝ seg´ıts´eg´evel. Azt mondjuk, hogy egy A ∈ Mm,n (Z) matrix ´ Smith normal ´ formaj ´ u´ modulo´ d, ha (i) A = [A]d ; (ii) A egy SNF matrix; ´ (iii) az A nem-nulla elemei osztjak ´ a d szamot. ´ Az k¨ovetkez˝o t´etelt a 1.7.2 t´etel e´ s a 1.8.2 k¨ovetkezm´eny megfelel˝o all´ ´ ıta´ saihoz hasonloan ´ bizony´ıtjuk, illetve felhasznaljuk ´ a 1.11.5 t´etel bizony´ıta´ san ´ al ´ targyalt ´ e´ szrev´eteleket.
T´etel 1.11.9 Minden egesz ´ matrix ´ modulo´ d ekvivalens pontosan egy modulo´ d SNF matrixszal. ´ Ha A egy eg´esz matrix, ´ akkor az A-val ekvivalens modulo´ d SNF matrix ´ diagonalis ´ elemeit az A modulo´ d invarians ´ faktorainak h´ıvjuk.
T´etel 1.11.10 Legyen M ∈ Mm,n (Z), legyenek d1 , . . . , dr az M matrix ´ nem-nulla invarians ´ faktorai, legyen d a dr egy pozit´ıv t¨obbsz¨or¨ose, es ´ legyenek c1 , . . . , cs az M nem-nulla invarians ´ faktorai modulo´ d. Ekkor, i ∈ {1, . . . , s} eseten ´ d i = ci , i ∈ {s + 1, . . . , r} eseten ´ pedig di = d. ´ . Legyen A az M-mel ekvivalens SNF matrix. B IZONY´I T AS ´ Mivel, minden i est´en, di | d, a modulo´ d SNF megegyezik az [A]d matrixszal. ´ Mivel d > dr , a [d]d = 0 az egyetlen lehets´eges redukcio´ melyet az SNF matrixon ´ el kell v´egeznunk. ¨ 2 A fenti eljar ´ ast ´ alkalmazva immar ´ viszonylag nagy m´eretu ˝ eg´esz matrixok ´ SNF alakjat ´ is meghatarozhatjuk. ´ Lassunk ´ egy p´eldat. ´ Jegyzet friss´ ıtve:
2006. december 12.
´ Csoportelmeleti algoritmusok
47
P´elda 1.11.11 Szam´ ´ ıtsuk ki a k¨ovetkez˝o matrixszal ´ ekvivalens SNF matrixot: ´ 0 B B B B B B B B B B B B B B B B B B B B B B B B B B B B B B @
1 1 −4 5 −4 0 −1 −1 2 1 −1 −2 −1 1 1 −2
0 −2 2 0 2 1 1 1 −1 1 1 1 1 0 −2 1
0 0 −1 2 −1 1 0 −3 −3 2 −3 0 0 0 0 0
−4 0 2 3 2 3 1 0 −2 −2 0 0 1 −4 0 0
1 1 −4 5 −4 0 −1 −1 2 1 −1 −2 −1 1 1 −2
0 −5 1 5 1 1 −4 5 0 0 5 0 −4 0 −5 0
−1 0 0 −2 0 −3 −1 2 −1 4 2 0 −1 −1 0 0
1 1 2 −1 2 1 −2 2 −2 −2 2 2 −2 1 1 2
0 −3 2 −1 2 0 −2 −2 −1 2 −2 −2 −2 0 −3 −2
−3 2 3 −7 3 −1 0 0 4 −2 0 2 0 −3 2 2
0 −5 1 5 1 1 −4 5 0 0 5 0 −4 0 −5 0
3 −1 4 1 4 3 0 −3 1 0 −3 −2 0 3 −1 −2
3 −1 4 1 4 3 0 −3 1 0 −3 −2 0 3 −1 −2
0 −2 2 0 2 1 1 1 −1 1 1 1 1 0 −2 1
−3 2 3 −7 3 −1 0 0 4 −2 0 2 0 −3 2 2
−4 0 2 3 2 3 1 0 −2 −2 0 0 1 −4 0 0
1 1 2 −1 2 1 −2 2 −2 −2 2 2 −2 1 1 2
−1 0 0 −2 0 −3 −1 2 −1 4 2 0 −1 −1 0 0
0 0 −1 2 −1 1 0 −3 −3 2 −3 0 0 0 0 0
0 −3 2 −1 2 0 −2 −2 −1 2 −2 −2 −2 0 −3 −2
1
C C C C C C C C C C C C C C C C. C C C C C C C C C C C C C C A
Ha a 1.7.2 t´etelben ismertetett eljar ´ as ´ GAP implementaci ´ oj ´ at ´ hasznaljuk, ´ akkor kevesebb mint harom ´ perc futas ´ utan ´ a programot leall´ ´ ıtva lathatjuk, ´ hogy a szam´ ´ ıtas ´ soran ´ a matrixban ´ szerepl˝o szamok ´ kezelhetetlenul ¨ nagyok lettek: a legnagyobb abszolut ´ e´ rt´eku ˝ elem t¨obb mint 150.000 szamjegy ´ u. ˝ Prob ´ aljuk ´ meg hat ´ az ebben a fejezetben ismertetett modularis ´ technikat. ´ A matrixra ´ vonatkozo´ Hadamard korlat ´ 2.762.238.134.958.316.012.567.889.543.430.144.000.000.000.000.000.000. ´ıgy elegend˝o a matrix ´ rangjat ´ mondjuk a 26.828.803.997.912.886.929.710.867.041.891.989.490.486.893.845.712.448.833 ´ pr´ımszam ´ szerint meghatarozni. ´ Igy kapjuk, hogy a rang 10. A k¨ovetkez˝o l´ep´es, hogy, az 1.11.7 utan ´ ismertetett modszerrel, ´ keressunk ¨ a matrixban ´ egy (10 × 10)-es nem-nulla aldeterminanst. ´ Ilyet alkotnak p´eldaul ´ az 1, 2, 3, 4, 6, 7, 8, 9, 10, 12 indexu ˝ sorok e´ s az ugyanezen indexu ˝ oszlopok metszet´eben l´ev˝o elemek; a kapott aldeterminans ´ 720.954. A 1.7.2 t´etelben ismertetett eljar ´ ast ´ elv´egezzuk ¨ modulo´ 720.954, e´ s kapjuk, hogy a modularis ´ SNF nemnulla atl ´ oelemei ´ 1, 1, 1, 1, 1, 1, 1, 1, 1 (9 darab egyes). ´Igy az 1.11.10 t´etel alapjan, ´ a fenti matrix ´ invarians ´ faktorai: 1, 1, 1, 1, 1, 1, 1, 1, 1, 720.954. A szam´ ´ ıtas ´ a GAP rendszerben n´ehany ´ tized masodperc ´ CPU id˝ot vesz ig´enybe.
1.12. R´acsok Legyen G a Zk csoport egy r´eszcsoportja. Ebben a fejezetben szeretn´enk r¨ovid vektorokbol ´ all ´ o´ bazis ´ at ´ talalni ´ a G csoportnak. A probl´emat ´ tagabban ´ is Jegyzet friss´ ıtve:
2006. december 12.
48
Abel-csoportok
vizsgalhatjuk, ´ e´ s tekinthetjuk ¨ a Rn vektort´er szabad Abel-r´eszcsoportjait. Ebben a szakaszban az Rn halmaz egy R feletti n-dimenzios ´ vektort´er. Ezen a vektort´eren e´ rtelmezzuk ¨ a skalarszorz ´ ast ´ vagy mas ´ n´even bels˝o szorzast: ´ P n v = (v1 , . . . , vn ), u = (u1 , . . . , un ) ∈ R eset´en v · u = i vi ui. Egy v vektor |v| hossza √ a v · v mennyis´eg. Eml´ekezzunk, ¨ hogy az R egy X r´eszhalmazat ´ diszkretnek ´ nevezzuk, ¨ ha Xnek nincs torlod ´ asi ´ pontja. Lemma 1.12.1 Legyen X egy reszcsoportja ´ az Rn csoportnak. Ekkor X akkor es ´ csakis akkor diszkret, ´ ha letezik ´ az origo´ k¨orul ¨ egy kompakt B g¨omb melyre X ∩ B veges. ´ ´ . Ha X diszkr´et akkor az origo´ nem torlod B IZONY´I T AS ´ asi ´ pontja az X halmaznak, e´ s a k´ıvant ´ g¨omb l´etezik. Tegyuk ¨ fel most, hogy B az origo´ k¨oruli ¨ ε sugaru ´ kompakt g¨omb. Legyen x egy torlod ´ asi ´ pontja az X csoportnak. Ekkor l´etezik y csoportelem melyre igaz, hogy az y k¨oz´eppontu, ´ ε sugaru ´ C g¨omb bels˝o pontk´ent tartalmazza az x-et, ´ıgy az is igaz, hogy C v´egtelen sok csoportelemet tartalmaz. Ekkor azonban, B = C − y = {c − y | c ∈ C} e´ s ´ıgy B is v´egtelen sok csoportelemet tartalmaz. Mivel B valaszt ´ asa ´ tetsz˝oleges volt, az all´ ´ ıtas ´ k¨ovetkezik. 2 Lemma 1.12.2 Legyen L az Rn csoport egy reszcsoportja. ´ Ekkor L diszkret ´ akkor es ´ csakis akkor, ha leteznek ´ x1 , . . . , xk ∈ L linearisan ´ fuggetlen ¨ vektorok melyekre L = {α1 x1 + · · · + αk xk | α1 , . . . , αk ∈ Z}. ´ . Tegyuk B IZONY´I T AS ¨ fel el˝osz¨or, hogy l´eteznek x1 , . . . , xk ∈ L linearisan ´ fugget¨ len vektorok melyekre igaz, hogy L = {α1 x1 + · · · + αk xk | α1 , . . . , αk ∈ Z}. Legyen ϕ : Rk → Rn a ϕ(α1 , . . . , αk ) = (α1 x1 , . . . , αk xk ) szabaly ´ altal ´ definialt ´ lek´epez´es. Mivel ϕ linearis, ´ ϕ egy homeomorfizmus. Legyen M = {|α1 x1 + · · · + αk xk | | α1 , . . . , αk ∈ R, α12 + · · · + αk2 = 1}. Jegyezzuk ¨ meg, hogy M az egys´egg¨omb ϕ altali ´ k´epe. Mivel az egys´egg¨omb kompakt, M is kompakt. Mivel x1 , . . . , xk linearisan ´ fuggetlenek, ¨ a nullvektor nem eleme M-nek. Ez´ert l´etezik a nullvektor k¨orul ¨ egy µ sugaru ´ B g¨omb Jegyzet friss´ ıtve:
2006. december 12.
´ Csoportelmeleti algoritmusok
49
melyre B ∩ M = ∅, e´ s ´ıgy minden M-beli vektor hossza legalabb ´ µ. Tetsz˝oleges β1 x1 + · · · + βk xk 6= 0 eset´en, q βk β1 2 2 x1 + · · · + p 2 xk > |β1 x1 + · · · + βk xk | = β1 + · · · + βk p 2 2 2 β1 + · · · + βk β1 + · · · + βk q > β12 + · · · + βk2 µ > µ.
Tehat ´ tetsz˝oleges nem nulla x elem eset´en kapjuk, hogy |x| > µ. A 1.12.1 lemmab ´ ol ´ k¨ovetkezik, hogy ebben az esetben L diszkr´et. Tegyuk ¨ most fel, hogy L diszkr´et e´ s legyen k a L altal ´ generalt ´ alt´er dimenzioja. ´ Legyenek w1 , . . . , wk ∈ L linearisan ´ fuggetlen ¨ vektorok. Legyen F = {α1 w1 + · · · + αk wk ∈ L | α1 , . . . , αk ∈ R, 0 6 α1 , . . . , αk 6 1}.
Mivel L diszkr´et, F egy v´eges halmaz. Minden i = 1, . . . , k eset´en legyen vi egy αi wi + · · · + αk wk alaku ´ eleme az F halmaznak melyben αi 6= 0 e´ s az αi egyutthat ¨ o´ minimalis. ´ Jegyezzuk ¨ meg, hogy wi ∈ F miatt, ilyen elem mindig l´etezik. Mivel a vi elemekb˝ol mint sorokbol ´ all ´ o´ matrix ´ fels˝o haromsz¨ ´ og alaku, ´ a vi elemek linearisan ´ fuggetlenek ¨ R felett. Be kell latnunk, ´ hogy a L minden eleme el˝oall ´ a vi vektorok eg´esz egyutthat ¨ os ´ linearis ´ kombinaci ´ ojak´ ´ ent. Legyen v ∈ L e´ s ´ırjuk fel a v vektort v = β1 v1 + · · · + βk vk alakban. Jel¨olje [βi ] e´ s {βi } a βi eg´esz- e´ s t¨ortr´esz´et, azaz [βi ] ∈ Z, 0 6 {βi } < 1, e´ s [βi ] + {βi } = βi . Ekkor v ′ = {β1 }v1 + · · · + {βk }vk ∈ L. Azt all´ ´ ıtjuk, hogy v ′ = 0. Legyen i a legkisebb index melyre {βi } = 6 0. Ekkor a v ′ vektor {βi }αi wi + · · · alaku, ´ ami ellentmond a vi valaszt ´ as ´ anak. ´ Ez´ert, minden i eset´en, {βi } = 0 e´ s βi ∈ Z. 2
Az Rn csoport egy diszkr´et r´eszcsoportjat ´ racsnak ´ nevezzuk. ¨ Ha L egy racs, ´ akkor az 1.12.2 lemmaban ´ szerepl˝o generatorrendszert ´ racsb ´ azisnak ´ nevezzuk. ¨ Vegyuk ¨ e´ szre, hogy az el˝oz˝o lemma szerint egy racs ´ szabad Abelcsoport, a racsb ´ azis ´ pedig szabad generatorrendszer. ´ Egy L racs ´ rangja, az altala ´ kifesz´ıtett alt´er dimenzioja, ´ ami megegyezik az L szabad Abel-csoportk´ent tekintett rangjaval. ´ Egy racsot ´ teljesnek mondunk, ha a racs ´ rangja megn egyezik az alapt´er R dimenzioj ´ aval. ´ Mivel, minden racs ´ teljes az altala ´ generalt ´ R feletti vektort´erben, a tovabbiakban ´ csak teljes racsokkal ´ foglalkozunk. Egy k R -beli L (teljes) racs ´ megadhato´ egy M ∈ Mk,k (R) matrixszal ´ melynek sorai generalj ´ ak ´ L-et. ´Irasban ´ L = hMi. Jegyzet friss´ ıtve:
2006. december 12.
50
Abel-csoportok
Lemma 1.12.3 Legyen v1 , . . . , vk es ´ w1 , . . . , wk egy L racs ´ ket ´ bazisa ´ es ´ legyenek A es ´ B azok a matrixok ´ melyeknek a sorai, rendre, v1 , . . . , vk es ´ w1 , . . . , wk . Ekkor letezik ´ egy P unimodularis ´ matrix ´ mellyel P A = B. ´ . Mivel a vi e´ s a wi vektorok bazist B IZONY´I T AS ´ alkotnak, l´eteznek pi,j e´ s qi,j eg´esz szamok ´ melyekkel wi =
k X
pi,j vj
e´ s vi =
j=1
k X
qi,j wj
j=1
teljesul. ¨ Legyen P = (pi,j ) e´ s Q = (qi,j ). Ekkor P, Q ∈ Mk,k (Z), P A = B, QB = A, tehat ´ P Q = I e´ s det P = ±1, azaz, a 1.6.3 lemma miatt, P ∈ GLk (Z). 2 Legyen L egy racs ´ e´ s legyen v1 , . . . , vk egy bazis ´ L-ben. A (vi · vj ) elemekb˝ol all ´ o´ matrixot ´ a L Gram-matrix ´ anak ´ h´ıvjuk. Jele G(L). A Gram-matrix ´ term´eszetesen fugg ¨ a bazis ´ valaszt ´ as ´ at ´ ol. ´ Ha M a v1 , . . . , vk sorvektorokbol ´ all ´ o´ t t matrix, ´ akkor a Gram-matrix ´ megegyezik a MM matrixszal, ´ ahol M az M transzponaltja. ´ Lemma 1.12.4 Ha L egy racs, ´ akkor G(L) szimmetrikus matrix. ´ Tovabb ´ a, ´ a det G(L) mennyiseg ´ fuggetlen ¨ a bazis ´ valaszt ´ as ´ at ´ ol ´ es ´ det G(L) > 0. ´ . Mivel az Rk t´eren vett bels˝o szorzat szmmetrikus, a GramB IZONY´I T AS matrix ´ defin´ıcioj ´ ab ´ ol ´ k¨ovetkezik, hogy a G(L) szimmetrikus. Legyen v1 , . . . , vk e´ s w1 , . . . , wk az L k´et bazisa ´ e´ s legyenek, rendre, A e´ s B azok a matrixok ´ melyeknek sorai v1 , . . . , vk , illetve w1 , . . . , wk . Ekkor az L racs ´ vi bazis ´ szerint t t vett Gram-matrixa ´ AA ahol A a matrix ´ transzponaltja, ´ a wi bazis ´ szerint vett t Gram-matrix ´ pedig BB . A 1.12.3 lemma szerint, l´etezik egy P ∈ GLk (Z) unimodularis ´ matrix ´ mellyel P A = B e´ s ´ıgy det(BB t ) = det(P AAt P t ) = det P det P t det(AAt ) = (det P )2 det(AAt ) = det(AAt ). Tehat ´ a racs ´ determinansa ´ valoban ´ fuggetlen ¨ a bazis ´ valaszt ´ as ´ at ´ ol. ´ Ha feltesszuk ¨ az altal ´ anoss ´ ag ´ megs´ert´ese n´elkul, ¨ hogy L teljes racs, ´ akkor a fenti A t egy invertalhat ´ o´ n´egyzetes matrix, ´ e´ s det G(L) = det A det A = (det A)2 > 0. 2 Ha v1 , . . . , vk az L racs ´ egy bazisa ´ e´ s G a bazishoz ´ tartozo´ Gram-matrix, ´ akkor √ ´ ans. ´ A racsdetermin ´ ans ´ hasznalhat ´ o´ a det G mennyis´eg neve racsdetermin r¨ovid racsvektorok ´ hosszanak ´ a becsl´es´ere. Jegyzet friss´ ıtve:
2006. december 12.
´ Csoportelmeleti algoritmusok
51
T´etel 1.12.5 (Minkowski konvex test t´etele) Legyen L egy racs, ´ es ´ legyen K egy origora ´ szimmetrikus, kompakt es ´ konvex halmaz melynek terfogata ´ n legalabb ´ 2 det L. Ekkor L ∩ K 6= ∅. K¨ ovetkezm´eny 1.12.6 Egy L racsnak ´ van olyan racsvektora ´ melynek hossza √ √ n legfeljebb n det L √ n ´ . Legyen K az origo´ k¨oz´eppontu ´ ag ´ u ´ kocka. EkB IZONY´I T AS ´ 2 det L e´ lhosszus n kor K t´erfogata 2 det L, tovabb ´ a´ K kiel´eg´ıti az el˝obbi t´etel k¨ovetelm´enyeit. √ √ Tehat ´ L ∩ K 6= ∅. Mivel K-ban minden vektor hossza legfeljebb n n det L, az all´ ´ ıtas ´ k¨ovetkezik. 2 Az el˝obbi k¨ovetkezm´enyben m´eg jobb korlatot ´ is lehetne adni, ha nem kockat ´ hanem g¨omb¨ot hasznaln ´ ank. ´
´ e1.13. A legr¨ ovidebb r´acsvektor a k´etdimenzios setben Jel¨olj¨on L ebben a fejezetben egy R2 -beli racsot. ´ Megmutatjuk, hogy L egy legr¨ovidebb vektora hat´ekonyan megkereshet˝o. Ez az eljar ´ as ´ adja majd az alapot a k¨ovetkez˝o szakaszban targyaland ´ o´ Lovasz ´ redukciohoz. ´ T´etel 1.13.1 Legyenek v1 , v2 ∈ R2 es ´ legyen L a v1 , v2 vektorok altal ´ generalt ´ racs. ´ Ekkor a 4. algoritmus veges ´ sok lep ´ es ´ utan ´ veget ´ er. ´ Tovabb ´ a´ az algoritmus futasa ´ utan ´ a v1 vektor egy legr¨ovidebb L-beli racsvektor, ´ a v2 pedig egy legr¨ovidebb v1 -tol ˝ fuggetlen ¨ racsvektor. ´ ´ . El˝osz¨or megjegyezzuk, B IZONY´I T AS ¨ hogy az algoritmus v´egrehajtasa ´ soran ´ a v1 , v2 elemek altal ´ generalt ´ racs ´ valtozatlan ´ marad. Valoban, ´ mivel k ∈ Z a v2 := v2 − kv1 utas´ıtas ´ sem valtoztatja ´ azt meg, illetve a v1 ↔ v2 csere sem. ´ ıtjuk, hogy az algoritmus v´eges sok l´ep´es utan All´ ´ v´eget e´ r. Legyen B az origo´ sugaru ´ |v1 | sugaru ´ g¨omb. Mivel L diszkr´et, L ∩ B v´eges halmaz. A ciklus minden v´egrehajtasa ´ utan ´ a v1 vektor hossza cs¨okken e´ s az uj ´ v1 vektor is eleme B-nek, az algoritmus v´eges sok l´ep´es utan ´ v´eget e´ r. Jegyzet friss´ ıtve:
2006. december 12.
52
Abel-csoportok
4. algoritmus: S HOR TEST V ECTOR Input: v1 , v2 ∈ R2 (lasd ´ 1.13.1 t´etel) Output: a hv1 , v2 i racs ´ egy r¨ovid vektorokbol ´ all ´ o´ bazisa ´ repeat legyen k ∈ Z melyre −(v1 · v1 )/2 < (v2 − kv1 ) · v1 6 (v1 · v1 )/2 set v2 := v2 − kv1 if |v2 | > |v1 | then return v1 , v2 csere v1 ↔ v2 until Algorithm 4: Gauss algoritmus Tegyuk ¨ fel, hogy a v1 e´ s v2 vektorok alkotjak ´ az algoritmus outputjat. ´ Ebben 2 az esetben |v2 · v1 | 6 |v1 | /2 e´ s |v1 | 6 |v2 |. Legyen v = αv1 + βv2 az L egy tetsz˝oleges nem-nulla vektora. Ekkor |v|2 = (αv1 + βv2 ) · (αv1 + βv2 ) = α2 |v1 | + 2αβ(v1 · v2 ) + β 2 |v2 | >
> α2 |v1 |2 − |αβ||v1|2 + β 2 |v2 |2 > (α2 − |αβ| + β 2 )|v1 |2 > |v1 |2 .
Tehat ´ v1 valoban ´ egy legr¨ovidebb racsvektor. ´ Tegyuk ¨ most fel, hogy v = αv1 +βv2 fuggetlen ¨ v1 -t˝ol, azaz β 6= 0. Ekkor, ha |β| > 2, akkor |v|2 > α2 |v1 |2 − |αβ||v1|2 + (β 2 /4)|v2 |2 + (3/4)β 2|v2 |2 >
> α2 |v1 |2 − |αβ||v1|2 + (β 2 /4)|v1 |2 + (3/4)β 2|v2 |2 =
= (|α| − |β/2|)2|v1 |2 + (3/4)β 2|v2 |2 > |v2 |2 .
Ha β = ±1 akkor
|v|2 > α2 |v1 |2 − |α||v1|2 + |v2 |2 > |v2 |2 .
Tehat ´ v2 valoban ´ egy legr¨ovidebb v1 -t˝ol fuggetlen ¨ vektor. 2 A 4. algoritmus a gyakorlatban is igen jol ´ hasznalhat ´ o. ´ Meg lehet ugyanis mutatni, hogy az algoritmus futasa ´ soran, ´ a ciklus minden v´egrejtasa ´ a v1 Jegyzet friss´ ıtve:
2006. december 12.
´ Csoportelmeleti algoritmusok
53
p vektor hosszat ´ 3/4-szeres´ere vagy m´eg kisebbre cs¨okkenti. ´Igy a v1 vektor hossza exponencialisan ´ gyorsan cs¨okken e´ s az algoritmus hamar v´eget e´ r.
´ (LLL) 1.14. Lenstra-Lenstra-Lov´asz redukcio Ez el˝oz˝o szakaszban megmutattuk, hogy egy k´etdimenzios ´ racsban ´ egy legr¨ovidebb vektor hat´ekonyan megtalalhat ´ o. ´ Sajnos egy magasabb dimenzioj ´ u ´ racsban ´ ez nem ilyen egyszeru, ˝ de egy r¨ovid vektort (azaz olyan vektort ami egy legr¨ovidebbt˝ol csak valamilyen ismert faktorral hosszabb) itt is talalhatunk ´ az LLL (Lenstra-Lenstra-Lovasz) ´ racsredukci ´ os ´ algoritmus seg´ıts´eg´evel. n Az R t´er v, u vektorait ortogonalisnak ´ (vagy merolegesnek) ˝ mondjuk, ha n u · v = 0. Legyen v ∈ R egy vektor, legyenek v1 , . . . , vk paronk´ ´ ent ortogonalis ´ P vektorok, e´ s jel¨olje v a v vektor hv1 , . . . , vk i alt´erre t¨ort´en˝o mer˝oleges vet´ıt´es´et. Linearis ´ algebrab ´ ol ´ ismert, hogy v P az alabbi ´ k´eplettel meghatarozhat ´ o: ´ k X v · vi v, v = v · vi i i=1 i P
e´ s a vet´ıt´es eredm´enye fuggetlen ¨ az ortogonalis ´ bazis ´ valaszt ´ as ´ at ´ ol. ´ Nyilvan ´ P v ∈ hv1 , . . . , vk i, tovabb ´ a´ k¨onnyu ˝ szamol ´ as ´ mutatja, hogy, minden 1 6 i 6 k P P eset´en, (v − v ) · vi = 0, azaz v − v mer˝oleges a hv1 , . . . , vk i alt´erre. A k¨ovetkez˝o eljar ´ as ´ neve Gram-Schmidt ortogonalizaci ´ os ´ eljar ´ as ´ e´ s linearis ´ algebrab ´ ol ´ ismert. Tegyuk ¨ fel, hogy v1 , . . . , vn linearisan ´ fuggetlen ¨ vektorok az n ∗ R t´erben. Definialjuk ´ a vi vektorokat a k¨ovetkez˝ok´eppen. Legyen v1∗ = v1 e´ s, i > 2 eset´en legyen vi∗ = vi − viP ahol viP a vi vektor hv1 , . . . , vi−1 i t´erre t¨ort´en˝o ∗ i t´erre mer˝oleges kommer˝oleges vet´ıt´ese. Mas ´ szoval, ´ vi∗ a vi vektor hv1∗ , . . . , vi−1 ∗ ponense. Egyszeru ˝ szamol ´ assal ´ lathat ´ o, ´ hogy a v1 , . . . , vk∗ vektorok paronk´ ´ ent mer˝olegesek, illetve, hogy az alabbi ´ tulajdonsag ´ fennall: ´ minden 1 6 i 6 n ∗ ∗ eset´en hv1 , . . . , vi i = hv1 , . . . , vi i. A fentiek miatt, vi∗ = vi −
i−1 X vi · vj∗ ∗ ∗ ∗ vj . v · v j j j=1
A v1∗ , . . . , vn∗ rendszert a v1 , . . . , vn rendszer Gram-Schmidt ortogonalizaci ´ oj ´ anak ´ nevezzuk. ¨ A fenti egyenletben szerepl˝o egyutthat ¨ ok ´ fontos szerepet jatszanak ´ Jegyzet friss´ ıtve:
2006. december 12.
54
Abel-csoportok
ez´ert ezekre kul¨ ¨ on jel¨ol´est vezetunk ¨ be. Legyen i ∈ {1, . . . , n} e´ s j ∈ {1, . . . , i − 1} eset´en vi · vj∗ µi,j = ∗ ∗ . vj · vj ´ 1.14.1 Legyen L egy racs, Defin´ıcio ´ e´ s legyen v1 , . . . , vn az L egy bazisa. ´ Ekkor az v1 , . . . , vn bazist ´ redukaltnak, ´ Lovasz-reduk ´ altnak, ´ vagy LLL-redukaltnak ´ nevezzuk, ¨ ha |µi,j | 6 1/2 minden 1 6 j < i 6 n eset´en, e´ s ∗ ∗ |vi∗ + µi,i−1vi−1 |2 > (3/4)|vi−1 |2
minden 1 < i 6 n eset´en.
(1.7)
A fenti defin´ıcioban ´ szerepl˝o (1.7) felt´etel neve Lovasz ´ feltetel ´ e´ s ekvivalens 2 2 ∗ 2 ´ etelb˝ol a k¨ovetkez˝ovel: |vi | > (3/4 − µi,i−1 )|vi−1 | . Mivel |µi,j | 6 1/2, a Lovasz-felt´ ∗ 2 ∗ 2 ´ kapjuk, hogy adodik, ´ hogy 2|vi | > |vi−1 | e´ s indukcioval 2i−j |vi∗ |2 > |vj∗ |2
minden i > j eset´en.
(1.8)
Mivel v1∗ = v1 a fenti egyenletb˝ol kapjuk, hogy 2i−1 |vi∗ |2 > |v1 |2
minden i > 1 eset´en.
Vegyuk ¨ e´ szre, hogy n = 2 eset´en a Gauss-algoritmus outputja redukalt. ´ A redukalt ´ bazisokat ´ jellemzi a k¨ovetkez˝o t´etel. T´etel 1.14.2 Legyen v1 , . . . , vn egy redukalt ´ bazisa ´ az L racsnak. ´ Ekkor √ (i) |v1 | 6 2(n−1)/4 n det L; (ii) minden v ∈ L eseten ´ |v1 | 6 2(n−1)/2 |v|; (iii) |v1 | · · · |vn | 6 2n(n−1)/4 det L. ´ . El˝osz¨or is all´ B IZONY´I T AS ´ ıtjuk, hogy 2
(det L) =
n Y i=1
Jegyzet friss´ ıtve:
vi∗ · vi∗ .
2006. december 12.
(1.9)
´ Csoportelmeleti algoritmusok
55
Az all´ ´ ıtas ´ igazolas ´ ahoz, ´ 1 6 j < i 6 n eset´en legyen µi,j a Gram-Schmidt egyutt¨ hato, ´ 1 6 i 6 n eset´en legyen µi,i = 1 e´ s i < j eset´en legyen µi,j = 0. Ha i ∈ {1, . . . , n}, akkor n X vi∗ = µi,j vj , j=1
tehat ´ vi∗ · vj∗ =
n X
µi,k vk
k=1
!
·
n X k=1
µj,k vk
!
.
´ Legyen A a v1 , . . . , vn , B pedig a v1∗ , . . . , vn∗ rendszerekhez tartozo´ Gram-matrix, legyen tovabb ´ a´ M a µi,j elemek altal ´ alkotott matrix. ´ Ekkor a fenti egyenl˝os´eget fel´ırhatjuk matrixos ´ alakban a k¨ovetkez˝ok´eppen: B = MAM t . Mivel M fels˝oharomsz¨ ´ og matrix ´ melynek atl ´ oj ´ aban ´ egyesek szerepelnek, kapjuk, hogy ´ ent det M = 1 e´ s ez´ert det L = det A = det B. Mivel a v1∗ , . . . , vn∗ vektorok paronk´ ∗ ∗ ortogonalisak, ´ a B matrix ´ diagonalis, ´ i-dik atl ´ oeleme ´ pedig vi · vi . A fentiek Q ∗ ∗ 2 miatt, (det L) = det B = vi · vi . Ezzel az all´ ´ ıtast ´ igazoltuk. Az el˝oz˝o bekezd´esben igazolt all´ ´ ıtast ´ e´ s az 1.8 egyenl˝otlens´eget hasznalva ´ kapjuk, hogy (det L)2 =
n Y i=1
vi∗ · vi∗ >
n Y i=1
21−i (v1 · v1 ) = 2−n(n−1)/2 (v1 · v1 ),
amib˝ol az (i) all´ ´ ıtas ´ k¨ovetkezik. A (ii) all´ ´ ıtas ´ igazolas ´ ahoz ´ tegyuk ¨ fel, hogy v = α1 v1 + · · · + αn vn e´ s legyen j ∈ {1, . . . , n} az a legnagyobb index melyre αj 6= 0. Mivel vj∗ = vj + u ahol
u ∈ v1 , . . . , vj−1 , kapjuk, hogy v = αj vj∗ + w ahol w ∈ v1 , . . . , vj−1 . ´Igy v · v = αj2 vj∗ · vj∗ + w · w > vj∗ · vj∗ > 21−j v1 · v1 > 21−n v1 · v1 ,
amib˝ol a (ii) all´ ´ ıtas ´ k¨ovetkezik. A (iii) all´ ´ ıtas ´ igazolas ´ ahoz ´ mutassuk el˝osz¨or meg, hogy vi · vi 6 2i−1 vi∗ · vi∗ . Mivel v1∗ = v1 , az all´ ´ ıtas ´ i = 1 eset´en nyilvanval ´ o. ´ Tegyuk ¨ fel, hogy az all´ ´ ıtas ´ igaz az els˝o i − 1 bazisvektorra, ´ e´ s igazoljuk az vi -re. A fenti tulajdonsagokat ´ Jegyzet friss´ ıtve:
2006. december 12.
56
Abel-csoportok
felhasznalva ´ kapjuk, hogy vi · vi =
2 n X vi · vj∗ j=1
vj∗ · vj∗
i−1
vj∗ · vj∗ 6 vi∗ · vi∗ +
1X ∗ ∗ v ·v 4 j=1 j j
i−1
6
vi∗
·
vi∗
·
vi∗
1 X i−j ∗ ∗ + 2 vi · vi 6 (2i−2 + 1)vi∗ · vi∗ 6 2i−1 vi∗ · vi∗ , 4 j=1
tehat ´ az all´ ´ ıtas ´ igaz. ´Igy n Y i=1
vi · vi 6
n Y i=1
2i−1 vi∗
=2
n(n−1)/2
n Y i=1
vi∗ · vi∗ = 2n(n−1)/2 (det L)2 .
Amib˝ol az all´ ´ ıtas ´ k¨ovetkezik, ezzel a t´etel bizony´ıtasa ´ teljes. 2 A fenti t´etelben szerepl˝o (ii) tulajdonsag ´ l´enyeg´eben azt mondja, hogy egy redukalt ´ bazis ´ els˝o vektoranak ´ hossza jol ´ k¨ozel´ıti a legr¨ovidebb vektorok hosszat. ´ A redukalt ´ bazis ´ jelent˝os´eg´et, jo´ tulajdonsagai ´ mellett, az a t´eny adja, hogy hat´ekonyan kiszam´ ´ ıthato. ´ Ezzel a t´ennyel most nem foglalkozunk b˝ovebben, csak egy egyszeru ˝ bazisredukci ´ os ´ algoritmust ismertetunk. ¨ Az algoritmus v´egrehajtas ´ ahoz ´ ismerni kell a µi,j Gram-Schmidt egyutthat ¨ okat. ´ Ezeket a Gram-Schmidt eljar ´ asban ´ ismertetett modon ´ meg lehet hatarozni. ´ T´etel 1.14.3 Az 5. algoritmus veges ´ sok lep ´ es ´ utan ´ veget ´ er, ´ outputja pedig az inputvektorok altal ´ generalt ´ racs ´ egy redukalt ´ bazisa. ´
Jegyzet friss´ ıtve:
2006. december 12.
´ Csoportelmeleti algoritmusok
57
5. algoritmus: LLL Input: egy L racs ´ v1 , . . . , vn bazisa ´ Output: L egy redukalt ´ bazisa ´ repeat for j ∈ {n − 1, . . . , 1} do for i ∈ {j + 1, . . . , n} do set vi := vi − λvj , λ a µi,j szamhoz ´ legk¨ozelebbi eg´esz. end for end for if (1.7) teljesul ¨ minden i-re then return v1 , . . . , vn else set i := olyan index melyre (1.7) nem teljesul ¨ set vi ↔ vi−1 end if until false Algorithm 5: LLL racsredukci ´ o´
Jegyzet friss´ ıtve:
2006. december 12.