A kurzus során először az Abel-csoportokkal kapcsolatos algoritmikus kérdésekkel

1. fejezet Abel-csoportok 1.1. Algoritmikus kérdések Abel-csoportokban A kurzus soran ´ el˝oször az Abel-csoportokkal kapcsolatos algoritmikus kérdésekkel foglalkozunk. Abel-csoportokban altal ´ aban ´ addit´ıv jelölést haszna´ lunk, tehat ´ a csoportmuveletet ˝ a + szimbolum ´ jelöli.

1.2. Szabad Abel-csoportok A szabad objektumok fontos szerepet jatszanak ´ az algebraban, ´ hiszen bel˝oluk ¨ faktorképzés seg´ıtségével el˝oall´ ´ ıthato´ az o¨ sszes algebrai struktura. ´ Példaul ´ egy tetsz˝oleges csoport fel´ırhato´ egy alkalmas szabad csoport faktorcsoportjaként. 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észhalDefin´ı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épezés esetén létezik 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élda 1.2.2 Tekintsuk ¨ az egész szamok ´ Z csoportjat ´ az o¨ sszeadasra ´ nézve. Nyilvan ´ az X = {1} halmaz generalja ´ a csoportot. Legyen G egy tetsz˝oleges ¯ Abel-csoport, e´ s tekintsunk ¨ egy f : X → G leképezést; tegyuk ¨ fel, hogy f¯(1) = g. Ha létezik f : Z → G homomorfizmus melyre f |X = f¯ teljesul, ¨ akkor n ∈ Z esetén ! 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étezik, akkor az egyértelmu. ˝ A létezés igazolas ´ ahoz ´ meg kell mutatni, hogy a fenti f leképezés 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élda 1.2.3 Legyen Z2 = {02 , 12 }, a 2-vel valo´ osztas ´ maradékainak kételemu ˝ ´ ıtjuk, hogy az csoportja. Ennek generator-rendszere ´ az X = {12 } halmaz. All´ X halmaz nem szabad generator-rendszer. ´ Legyen példaul ´ Z3 = {03 , 13 , 23 } a haromelem ´ u ˝ maradékosztaly ´ csoport, e´ s legyen f¯ : 12 7→ 13 . Ha f a f¯ egy kiterjesztése, 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ölje Z2 a kételemu B IZONYÍ 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épezések szam ´ aval. ´ Ezek szama ´ 2|X| , illetve 2|Y | . Így, |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éldaban ´ szerepl˝o csoport rangja 1. Az 1.2.3 példa gondolatmenetét hasznalva ´ nem nehéz latni, ´ hogy véges Abel-csoportok nem lehetnek szabadok. Valoj ´ aban ´ a végesen generalt ´ szabad Abel-csoportok egyszeruen ˝ meghatarozhat ´ ok, ´ a következ˝oképpen. Jol ´ ismert, hogy az egész szamok ´ Z halmaza Abel-csoportot alkot az o¨ sszeadasra ´ nézve. 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észek. Az (a1 , . . . , ak ) e´ s a (b1 , . . . , bk ) elemek o¨ sszege (a1 + b1 , . . . , ak + bk ). Ennek a csoportnak a zéro-eleme ´ a (0, . . . , 0) elem, az (a1 , . . . , ak ) elem inverze pedig a (−a1 , . . . , −ak ). A csoportok direkt szorzatanak ´ defin´ıcioja ´ miatt, két csoportbeli elem (a1 , . . . , ak ) e´ s (b1 , . . . , bk ) akkor e´ s csakis akkor egyenl˝o, ha ai = bi teljesul ¨ minden i-re. Tétel 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ölje ei a Zk csoportnak azt az elemét B IZONYÍ T AS amelynek minden koordinat ´ aja ´ 0, kivéve 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épezés 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épében, f szurjekt´ ¨ ıv. Tegyuk ¨ fel, hogy α1 , . . . , αk ∈ Z esetén 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ért, ker f = 0, ami azt jelenti, hogy f injekt´ıv. Tehat ´ f valoban ´ bijekcio. ´ 2 K¨ ovetkezmény 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Í T AS ´ is hasznaljuk ´ az el˝oz˝o bizony´ıtas ´ jelöléseit, 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épezés. Mivel X = {x1 , . . . , xk } szabad generator´ ¯ : xi 7→ g¯(ei ) leképezés rendszere az el˝oz˝o tételben szerepl˝o F csoportnak, a h kiterjeszthet˝o egy h : F → G homomorfizmussa. ´ Definialjuk ´ az g leképezést k −1 a következ˝oképpen: 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épezés is az. Tovabb ´ a, ´ g(ei ) = h(f −1 (ei )) = h(xi ) = g¯(ei ). Ezért g kiterjesztése a g¯ leképezésnek e´ s ´ıgy a k´ıvant ´ leképezés létezik. Tegyuk ¨ k fel, hogy g1 , g2 : Z → G homomorfizmusok melyek kiterjesztik a g¯ leképezést. Ekkor az f g1 , f g2 leképezések kiterjesztik a xi 7→ g(ei) leképezést. Mivel X szabad generator-rendszer, ´ f g1 = f g2 , azaz g1 = g2 . Tehat ´ a g¯ leképezés kiterjesztése egyértelmu, ˝ a {e1 , . . . , ek } halmaz szabad generator-rendszer, ´ az Zk pedig szabad csoport. 2 Természetesen 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ény 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Í T AS ˝ generator-rendszere ´ a G csok portnak, e´ s definialjuk ´ az f : Z → G homomorfizmust a ei 7→ xi leképezés kiterjesztéseként. Mivel X generalja ´ a G csoportot, f szurjekt´ ¨ ıv, e´ s ´ıgy, a hok momorfizmus tétel szerint, G ∼ = Z /(ker f ). 2 Példa 1.2.8 Legyen G = Z3 ⊕ Z5 = hai ⊕ hbi. Legyen f : Zk → G az e1 7→ a, e2 7→ b leképezés kiterjesztése. 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 Így G ∼ = Z / h(3, 0), (0, 5)i.

Jegyzet friss´ ıtve:

2006. december 12.


5

A szabad generator-rendszer ´ defin´ıcioja ´ nem teszi lehet˝ové, hogy egyszeruen ˝ ellen˝orizzuk, ¨ hogy egy szabad Abel-csoportbeli halmaz szabad generator-rendszer-e. ´ A következ˝o lemma, egy könnyebben kezelhet˝o szuks´ ¨ eges e´ s elegend˝o feltételt 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Í T AS ¨ fel el˝oször, 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ételben definialt ´ izomorfizmus. Tegyuk ¨ fel, hogy α1 , . . . , αk e´ s β1 , . . . , βk egész 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övetkezik. Tehat ´ az α1 x1 + · · · + αk xk elem fel´ırasa ´ egyértelmu. ˝ Tegyuk ¨ most fel, hogy X rendelkezik a tételben megkövetelt tulajdonsaggal. ´ Legyen G egy Abel-csoport, e´ s legyen g¯ : X → G egy leképezés. Definialjuk ´ az k f : F → Z leképezést: f (α1 x1 + · · · + αk xk ) = (α1 , . . . , αk ). A feltétel 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épében, ´ı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épezést melyre h(e ¯ i ) = g¯(xi ). Ekkor a h ¯ kiterjesztJelölje h k het˝o egy h : Z → G homomorfizmussa, ´ e´ s definialhatjuk ´ a g leképezést a következ˝oképpen: x ∈ F esetén 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épezések, melyekre g1 f −1 |Y = g2 f −1 |Y . Mivel Y szabad generator-rendszer, ´ g1 f −1 = g2 f −1 következik, tehat ´ g1 = g2 . 2 Jegyzet friss´ ıtve:

2006. december 12.

6

Abel-csoportok

1.3. Szabad Abel-csoportok részcsoportjai Egy szabad Abel-csoport minden részcsoportja is szabad Abel-csoport. Mi ezt az eredményt csak végesen generalt ´ szabad Abel-csoportok esetén bizony´ıtjuk. Tétel 1.3.1 Egy k rangu´ szabad Abel-csoport tetszoleges ˝ reszcsoportja ´ is egy legfeljebb k rangu´ szabad Abel-csoport. ´ . A 1.2.5 tétel miatt, elegend˝o belatni, B IZONYÍ T AS ´ hogy az F = Zk csoport tetsz˝oleges H részcsoportja szabad Abel-csoport melynek rangja legfeljebb k. Legyen i ∈ {0, . . . , k} e´ s jelölje Fi azon k-asok halmazat, ´ amelyekben az els˝o i koordinata ´ 0. Ezzel definialtuk ´ következ˝o F -beli részcsoportlancot: ´ F = F0 > F1 > · · · > Fk−1 > Fk = 0; tovabb ´ a´ i ∈ {0, . . . , k − 1} esetén 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ért Hi /Hi+1 izomorf a Fi /Fi+1 ∼ ´ A Z egy = Z csoport egy részcsoportjaval. részcsoportja vagy trivialis, ´ vagy pedig izomorf Z-vel, ezért 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észcsoportlancot ´ amelynek faktorai vagy trivialisak ´ vagy pedig izomorfak a Z csoporttal. A lancb ´ ol ´ hagyjuk el az ismétl˝odéseket, e´ s alkossunk egy H0 = H > H1 > · · · > Hm−1 > Hm = 0 részcsoportlancot ´ amelyben minden faktor izomorf a Z csoporttal. Jegyezzuk ¨ itt meg, hogy m 6 k. Valasszunk, ´ i ∈ {1, . . . , m} esetén, egy ai ∈ Hi−1 elemet ugy, ´ hogy hai + Hi i = Hi−1 /Hi . Ilyen elem létezik, 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.


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észcsoport pontosan egy mellékosztaly ´ aban ´ talalhat ´ o, ´ ezért egyéretelmuen ˝ léteznek 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és all´ ´ ıtasa ´ szerint létezik pontosan egy α1 ∈ Z e´ s pontosan egy y1 ∈ H1 ugy ´ hogy x = α1 a1 + y1 . Hasonloan, ´ létezik 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értelmuen ˝ léteznek α1 , . . . , αm ∈ Z amelyek kielég´ı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ész mátrixokkal Jelölje Mm,k (Z) az m sorbol ´ e´ s k oszlopbol ´ all ´ o´ Z feletti matrixok ´ halmazat. ´ A Zk csoport egy G részcsoportjat ´ megadhatjuk egy A ∈ Mm,k (Z) matrix ´ seg´ıtségével, melynek a sorai generaljak ´ a G csoportot. Szimbolumokkal ´ ezt a tényt ugy ´ fejezzuk ¨ ki, hogy G = hAi. A fenti 1.3.1 tétel szerint, feltehetjuk, ¨ hogy m 6 k. Vilagos, ´ hogy az hAi csoport megegyezik az A matrix ´ soraibol ´ all ´ o´ egész egyutthat ¨ os ´ linearis ´ kombinaci ´ ok ´ a halmazaval. ´ Ebben a szakaszban olyan modszereket ´ ismertetunk, ¨ amik az alabbi ´ kérdésekre 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örében a következ˝o muveleteket ˝ elemi (egesz) ´ sormuveleteknek ˝ nevezzuk: ¨ (i) két sor felcserélése; (ii) egy sor szorzasa ´ −1-gyel; Jegyzet friss´ ıtve:

2006. december 12.

8

Abel-csoportok

(iii) egy sor valamely egész többszörösének hozzaad ´ asa ´ egy masik ´ sorhoz. Példa 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élése 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égul ¨ pedig adjuk a masodik ´ sor −2-szeresét 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égével. 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Í T AS ´ hogy a relaci ´ o´ reflex´ıv, mert az A matrixb ´ ol ´ o¨ nmagat ´ kapjuk, ha példaul ´ egy sorat ´ kétszer 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égével, akkor ezeket a sormuveleteket ˝ egymas ´ utan ´ elvégezve az A matrixb ´ ol ´ a C-t nyerjuk. ¨ Az ekvivalencia relaci ´ o´ igazolas ´ ahoz ´ tehat ´ csak a szimmetriat ´ kell belatni. ´ El˝oször megmutatjuk, hogy a fenti Jegyzet friss´ ıtve:

2006. december 12.


9

sormuveletek ˝ megford´ıthatoak, ´ azaz ha B megkaphato´ A-bol ´ egyetlen sormuvelet ˝ seg´ıtségével, akkor A is megkaphato´ B-b˝ol szintén egyetlen sormuve˝ let seg´ıtségével. Az all´ ´ ıtas ´ nyilvanval ´ o, ´ ha a sormuvelet ˝ két sor felcserélése, 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égrehajtva. A fenti okoskodas ´ miatt, ha most a B-b˝ol indulunk ki, e´ s a sormuveletek ˝ ellentettjét hajtjuk végre ford´ıtott sorrendben, akkor visszakapjuk az A matrixot. ´ Tehat ´ a relaci ´ o´ szimmetrikus. A masodik ´ all´ ´ ıtas ´ bizony´ıtas ´ ahoz ´ el˝oször belatjuk, ´ hogy ha a B matrix ´ megkaphato´ az A matrixb ´ ol ´ egy sormuvelet ˝ seg´ıtségével, akkor hBi 6 hAi. Az all´ ´ ıtas ´ nyilvanval ´ o, ´ ha a sormuvelet ˝ két sor felcserélése 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ételével, a B matrix ´ minden sora szerepel az A matrixban ´ is. Ezek a sorok tehat ´ benne vannak az hAi részcsoportban. A B matrix ´ i-dik sora fel´ırhato´ ai + αaj alakban, ahol ai e´ s aj jelöli 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észcsoportban, tehat ´ valoban ´ hBi 6 hAi. Ha most feltesszuk, ¨ hogy B megkaphato´ az A-bol ´ egyetlen sormuvelet ˝ seg´ıtségével, akkor az el˝oz˝o bekezdésben bizony´ıtottak miatt, hBi 6 hAi. Ekkor azonban A is megkaphato´ az B matrixb ´ ol ´ egy hasonlo´ sormuvelet ˝ seg´ıtségével, ´ıgy hAi 6 hBi. Tehat ´ hAi = hBi következik. Végul, ¨ ha A e´ s B ekvivalens matrixok, ´ akkor B megkaphato´ az A-bol ´ sormuveletek ˝ egy sorozatanak ´ seg´ıtségével. Ezek a sormuveletek ˝ azonban ´ nem valtoztatj ´ ak ´ meg a sorok altal ´ generalt ´ részcsoportot. Igy hAi = hBi teljesul. ¨ 2

A 1.4.1 példaban ´ szerepl˝o négy matrix ´ egymassal ´ paronk´ ´ ent sor-ekvivalens. Jegyzet friss´ ıtve:

2006. december 12.

10

Abel-csoportok

1.5. A Hermite normál forma Az el˝oz˝o fejezetben lattuk, ´ hogy az elemi sormuveletek ˝ nem valtoztatnak ´ egy Mm,k (Z)-beli matrix ´ sorai altal ´ generalt ´ részcsoporton. Így ha A ∈ Mm,k (Z), akkor elemi sormuveletek ˝ seg´ıtségével szeretnénk egy szép” B ∈ Mm,k (Z) ” matrixot ´ kapni melyre hAi = hBi teljesul. ¨ Lassunk ´ erre egy példat. ´ Példa 1.5.1 Legyen A a következ˝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öbbi sorhoz, elérhetjuk, ¨ 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ét, hogy vezéreleme (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öbbi sorhoz, csökkenthetjuk ¨ a masodik ´ oszlopban, a masodik ´ sortol ´ lefelé lév˝o elemek abszolut ´ Jegyzet friss´ ıtve:

2006. december 12.

´ Csoportelmeleti algoritmusok e´ rtékét:

       

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ödik soraban ´ lév˝o elemeit:  1 2 1 2   0 0 2 23   0 0 −4 −2    0 1 −1 −12 0 0 −4 6 Cseréljuk ¨ 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ét az els˝o sorhoz adva elérjuk, ¨ hogy a masodik ´ sor vezéreleme 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égével lenullazzuk ´ a harmadik oszlop harmadik e´ s o¨ tödik soraban ´ lév˝o elemeit, felcseréljuk ¨ a negyedik e´ s a harmadik sorokat, majd gondoskodunk rola, ´ hogy a harmadik sor vezéreleme felett csak a vezérelemnél kisebb abszolut ´ e´ rtéku ˝ elemek legyenek. Jegyzet friss´ ıtve:

2006. december 12.

12

Abel-csoportok

Így a következ˝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ödik sorokat addig adogatjuk egymashoz, ´ vagy vonogatjuk egymasb ´ ol, ´ m´ıg az egyikben a negyedik oszlopban lév˝o elem 0 lesz. Aztan ´ sorcserével elérjuk, ¨ hogy a negyedik sorban e´ s negyedik oszlopban lév˝o elem nem-nulla, majd a negyedik sor vezéreleme 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égul ¨ az o¨ tödik sor seg´ıtségével redukaljuk ´ az o¨ tödik oszlopban lév˝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égeredménye egy fels˝o haromsz¨ ´ og matrix, ´ melyben a vezérelemek nem-negat´ıvak, illetve a vezérelemek felett t˝olik kisebb abszolut ´ e´ rtéku ˝ 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övetkez˝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.


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év˝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éreleme pozit´ıv. (iv) Ha k < i 6 r akkor 0 6 Ak,ji < Ai,ji . Azaz, a egy nem-nulla sor vezéreleme felett kisebb, nem-negat´ıv elemek talalhat ´ ok. ´ Az 1.5.1 példaban ´ az szamol ´ as ´ végén kapott matrix ´ HNF alaku. ´ A példa jol ´ szemlélteti, azt az eljar ´ ast, ´ amivel barmely ´ egész e´ rtéku ˝ 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öli az M matrix ´ i-dik sorat, ´ Mi,j pedig az i-dik sor j-dik elemét. Ha a, b ∈ Z, akkor egyértelmuen ˝ léteznek q e´ s r egész szamok ´ melyekre a = qb + r e´ s 0 6 r < |b| (euklideszi osztas) ´ e´ s a div b jelöli az osztas ´ q hanyados ´ at. ´ Sajnos a HNF algoritmus nem tuls ´ agosan ´ hatékony. Tekintsuk ¨ példaul ´ 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égével 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ékuek), ˝ e´ s az eredmény maximalis ´ abszolut ´ e´ rtéku ˝ eleme is 2073, addig a közbuls˝ ¨ o matrixokban ´ el˝ofordulo´ legmagasabb abszolut ´ e´ rtéku ˝ elem 2.386.233. Mivel, nagyobb matrixokban ´ ez a probléma még e´ lesebben jelentkezik, fontos feladat, hogy olyan HNF algoritmusokat tervezzunk, ¨ amelyekben a közbuls˝ ¨ 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értelmu ˝ */ 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 ´


2006. december 12.


15

Tétel 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Í T AS ˝ hajtottunk végre, a program futasa ´ soran ´ minden lépés az eredetivel sor-ekvivalens matrixot ´ eredményez. Tehat ´ a végs˝o matrix ´ szintén sor-ekvivalens lesz az eredeti M matrixszal. ´ Ha i ∈ {1, . . . , n}, akkor jelölje M (i) azt a matrixot ´ melyet az M els˝o i oszlopab ´ ol ´ kapunk. Teljes indukcioval ´ belatjuk, ´ hogy a következ˝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égzése utan, ´ e´ s lassuk ´ be, hogy az j-dik lefutas ´ utan ´ is igaz marad. A while utani ´ if utas´ıtas ´ feltétele pontosan akkor teljesul, ¨ ha a j-dik oszlopban az i-dik sortol ´ (j−1) (j) lefelé, 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öveljuk, ¨ az i valtoz ´ ot ´ nem valtoztatjuk, ´ e´ s a while ciklus végére ugrunk. Így ebben az esetben a fenti (i)–(ii) all´ ´ ıtasok ´ tovabbra ´ is fennallnak. ´ Ezt tesszuk ¨ egészen addig, m´ıg az if utas´ıtas ´ feltétele 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ét kul¨ ¨ onböz˝o k ∈ {i, . . . , m} esetén. Amennyiben ez a feltétel teljesul, ¨ ugy ´ az algoritmus kivalaszt ´ ezen elemek közul ¨ két 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ékos osztast ´ végzunk: ¨ Ml,j = qMk,j + r, ahol q e´ s r egész 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ökkenteni az Ml,j elem abszolut ´ e´ rtékét. A bels˝o while ciklus minden iteraci ´ oja ´ utan ´ az |Mi,j | + · · · + |Mm,j | o¨ sszeg csökken, ´ıgy a ciklus véges sok lépés utan ´ véget e´ r. Jegyzet friss´ ıtve:

2006. december 12.

16

Abel-csoportok

A fentiek miatt, a bels˝o while ciklus befejezése utan ´ Mk,j 6= 0 pontosan egy k ∈ {i, . . . , m} esetén. Ha k 6= i akkor felcseréljuk ¨ 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éreleme Mi,j , amelyre teljesul, ¨ hogy j > i, Mi,j > 0, e´ s az is, hogy a vezérelem alatt csupa nulla elem talalhat ´ o. ´ Tehat ´ a 1.5.2 defin´ıcio´ (i)–(ii) feltételeit belattuk. ´ A (iii) feltétel az algoritmus végén talalhat ´ o´ for ciklus miatt teljesul. ¨ Ha ugyanis, valamely l ∈ {1, . . . , i−1} esetén Ml,j -re az (iii) feltétel nem teljesul, ¨ akkor ismét maradékos osztast ´ végzunk, ¨ 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ég´ıti a 1.5.2 defin´ıcio´ (iii) feltételét is. Ha a matrix ´ oszlopainak szama ´ n, akkor a while ciklus n lefutasa ´ utan ´ M = M HNF alaku ´ lesz. 2 (n)

K¨ ovetkezmény 1.5.4 Minden egesz ´ matrix ´ sor-ekvivalens egy Hermite normal ´ formaban ´ lev ´ o˝ matrixszal. ´ ´ . Az el˝oz˝o tétel szerint, a HNF algoritmus outputja e´ pp megfelel˝o. 2 B IZONYÍ T AS Emlékezzunk, ¨ hogy a 1.3.1 tétel szerint a Zn csoport minden részcsoportja szabad csoport, ´ıgy egy A ∈ Mm,n (Z) matrix ´ esetén is igaz, hogy hAi szabad. A HNF seg´ıtségével meghatarozhatjuk ´ ennek a csoportnak egy bazis ´ at. ´ Tétel 1.5.5 Ha A egy HNF matrix, ´ akkor A nem-nulla sorai az hAi csoport egy bazis ´ at ´ alkotjak. ´ ´ . Tegyuk B IZONYÍ 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éleképpen ´ırhato´ fel az A matrix ´ nem-nulla sorainak egész egyutthat ¨ os ´ linearis ´ kombinaci ´ ojak´ ´ ent. Legyen r az A-beli nem-nulla sorok szama, ´ e´ s i ∈ {1, . . . , r} esetén legyen Ai,ji az i-dik sor vezéreleme. 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ész szamok. ´ ´ r egyenletb˝ol all ´ o´ egyenletrendA (1.1) egyenletb˝ol r szam ´ u ´ vji elemre az alabbi Jegyzet friss´ ıtve:

2006. december 12.


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égyzet alaku ´ also´ haromsz¨ ´ og matrix, ´ ´ıgy ennek a matrixnak ´ a determinansa ´ k nem-zéro. ´ Ezért, ennek az egyenletrendszernek pontosan egy Q -beli megoldasa ´ van: (α1 , . . . , αr ). Következésképp, a (1.1) fel´ıras ´ egyértelmu, ˝ tehat ´ az A nem-nulla sorai az hAi csoport egy bazis ´ at ´ adjak. ´ 2

Ha A ∈ Mm,k (Z), akkor szeretnénk eldönteni példaul, ´ hogy egy Zk -beli v elem benne van-e az hAi csoportban. A 1.5.5 tétel bizony´ıtasa ´ azt sugallja, hogy a Hermite normal ´ forma seg´ıtségével ezt a problémat ´ is hatékonyan meg tudjuk oldani. Példa 1.5.6 Legyen A a következ˝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érdés, hogy a v vektor eleme-e az hAi csoportnak. Egy A matrixszal ´ ekvivalens HNF matrix ´ a HNF algoritmus seg´ıtségével könnyen 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égével. A fenti linearis ´ kombinaci ´ o´ els˝o koordinat ´ aja ´ mindenképp 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önnyu ˝ szamol ´ as ´ mutatja, hogy valoban ´ v = A1 − A2 + 2A3 − 3A4 , tehat ´ v ∈ hAi. A fenti példa alapjan ´ könnyu ˝ egy altal ´ anos ´ algoritmust létrehozni. Az algoritmus le´ıras ´ aban ´ a HNF algoritmusnal ´ hasznalt ´ jelölést alkalmazzuk, a v vektor i-dik komponensét pedig vi jelöli.

2. algoritmus: I S M EMBER Input: A ∈ Mm,n (Z) HNF matrix ´ e´ s v ∈ Zn Output: (x1 , . . . , xm ) ha v ∈ hAi; egyébként false set r := a nem-nulla sorok szama ´ for i ∈ {1, . . . , r} do set Ai,j := az i-dik sor vezéreleme 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étel 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)


19

´ . Az r valtoz B IZONYÍ T AS ´ o´ jelöli a nem-nulla sorok szam ´ at. ´ A for ciklus belsejében Ai,j az i-dik sor els˝o nem nulla eleme. Tegyuk ¨ fel el˝oször, hogy v ∈ hAi e´ s ´ıgy v = x1 A1 + · · · + xm Am , ahol x1 , . . . , xm ∈ Z. Az 1.5.5 tétel szerint az A matrix ´ els˝o r sora az hAi csoport egy bazis ´ at ´ adja, ezért az x1 , . . . , xr egyutthat ¨ ok ´ egyértelmuen ˝ 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én, vi = xi+1 Ai+1 + · · · + xr Ar , e´ s legyen vr = 0. ´ ıtjuk, hogy ha for ciklus i-szer sikeresen végigfut (azaz a ciklusbeli return All´ utas´ıtas ´ nem hajtodik ´ végre), az x1 , . . . , xi egyutthat ¨ ok ´ e´ rtéke helyes, az algoritmusbeli v valtoz ´ o´ e´ rtéke 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övet˝o set parancs miatt, v = vi−1 − xi Ai = vi . Ha a v vektor nem eleme a hAi csoportnak akkor két eset lehetséges. Az els˝o esetben a for cikluson beluli ¨ if feltétele nem teljesul, ¨ e´ s ´ıgy az output false. Ha ez nem igaz, akkor a for ciklus elvégzése 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ész matrix ´ sor-ekvivalens egy HNF mat´ rixszal. Most igazoljuk, hogy ez a matrix ´ lényegében egyértelmuen ˝ meghatarozott. ´ Tétel 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Í T AS ´ zéro´ sorok nélkul ¨ melyekre H = hAi = hBi teljesul. ¨ Az 1.5.5 tétel 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öljuk ¨ 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össze egy sorbol ´ allnak. ´ Mivel, A ∈ hBi, létezik α ∈ Z, melyre A = αB teljesul. ¨ Hasonloan, ´ B = βA valamely β ∈ Z egész 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érelemei nem-negat´ıvak, α = β = 1 következik. 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érelemei. 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ében az els˝o j1 − 1 koordinata ´ 0, tehat ´ a b elem oszlopszama ´ legalabb ´ j1 . Tehat ´ j1 6 j2 . Az e´ rvelést megford´ıtva kapjuk, hogy j2 6 j1 , azaz j1 = j2 következik; jelölje j ezt a szamot. ´ Legyen A1 az a matrix ´ melyet A-bol ´ kapunk az els˝o sor törlése utan; ´ képezzuk ¨ 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övetkezik, hogy hA1 i = hB1 i. Jelölje H1 ezt a csoportot. Mivel az A1 e´ s B1 matrixok ´ HNF alakuak, ´ az indukcios ´ feltevés miatt, A1 = B1 . Legyen u az A els˝o sora, v pedig a B els˝o sora. Jelölje D a H-beli elemek j-dik komponenseinek a halmazat. ´ A D halmaz a Z egy részcsoportja, melyet a is e´ s b is general. ´ Ezért a = ±b, de mivel a is e´ s b is pozit´ıv, a = b következik. Tehat ´ u − v ∈ H1 . Tegyuk ¨ fel, hogy u 6= v, e´ s legyen c az u − v vektor els˝o nem-nulla komponense. Tételezzuk ¨ fel, hogy c a k-dik oszlopban van. Ekkor az A1 matrix ´ egyik soranak ´ vezéreleme d szintén a k-dik oszlopban van, e´ s d|c. Azonban a HNF defin´ıcioja ´ szerint, a d felett csak d-nél kisebb nem-negat´ıv elemek lehetnek, ezért az u e´ s v matrixok ´ k-dik komponense kisebb mint d, ´ıgy a kul¨ ¨ onbséguk ¨ abszolut ´ e´ rteke is legfeljebb d − 1, ami ellentmondas. ´ Tehat ´ u = v, e´ s ´ıgy A = B. 2 K¨ ovetkezmény 1.5.9 Minden egesz ´ matrix ´ sor-ekvivalens pontosan egy HNF matrixszal. ´ ´ . Korabban B IZONYÍ T AS ´ lattuk, ´ hogy létezik egy ilyen HNF matrix. ´ Tegyuk ¨ ˆ a nulla sorok elhagyasa fel, hogy A e´ s B ilyen matrixok, ´ e´ s jelölje Aˆ e´ s B ´ utan ´ Jegyzet friss´ ıtve:

2006. december 12.


21

D E D E ˆ , e´ s ´ıgy az el˝oz˝o tételb˝ol Aˆ = B ˆ következik. kapott matrixokat. ´ Ekkor Aˆ = B Mivel A-nak e´ s B-nek ugyanannyi sora van, A = B szintén teljesul. ¨ 2

1.6. Unimoduláris mátrixok Legyen A ∈ Mm,n (Z), e´ s tegyuk ¨ fel, hogy a B matrixot ´ az A-bol ´ egy elemi sormuvelet ˝ seg´ıtségével kaptuk. Legyen P ∈ Mm,m (Z) az a matrix ´ melyet az m × m-es egységmatrixb ´ ol ´ kapunk ugyanannak az elemi sormuveletnek ˝ az elvégzése utan. ´ Az ilyen P matrix ´ neve elemi matrix. ´ A haromf´ ´ ele elemi sormuveletet ˝ egyenként megvizsgalva, ´ könnyu ˝ ellen˝orizni, hogy B = P A teljesul. ¨ Azaz egy elemi sormuvelet ˝ realizalhat ´ o´ mint egy elemi matrixszal ´ balrol ´ történ˝o szorzas ´ eredménye. Ha most a B matrix ´ sor-ekvivalens az A matrixszal, ´ akkor a B megkaphato´ az A-bol ´ elemi sormuveletek ˝ sorozatos elvégzése 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én −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övetkez˝o eredményt 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ését adja a következ˝o lemma. Jegyzet friss´ ıtve:

2006. december 12.

22

Abel-csoportok

Lemma 1.6.3 Ha B ∈ Mm,m (Z), akkor a következok ˝ 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Í T AS ´ matrix ´ defin´ıcioj ´ an ´ al ´ belattuk, ´ hogy egy ilyen matrix ´ determinansa ´ 1 vagy −1. Tehat ´ (i)-b˝ol (ii) következik. Tegyuk ¨ fel, hogy det B = ±1. Legyen A a B-hez tartozo´ HNF matrix. ´ Ekkor, az 1.6.2 lemma miatt, létezik 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érelemei az atl ´ oban ´ talalhat ´ ok. ´ Mivel det A = ±1, az atl ´ oban ´ lév˝o elemek abszolut ´ e´ rtéke 1, e´ s ´ıgy a HNF defin´ıcioja ´ miatt, egyrészt A diagonalis ´ matrix, ´ masr´ ´ eszt a diagonalisban ´ minden elem 1. Tehat ´ A az egységmatrix, ´ e´ s ´ıgy (ii)-b˝ol következik (iii). Ha B ekvivalens az m × m-es egységmatrixszal, ´ akkor 1.4.2 lemma miatt, hBi = Zm , tehat ´ (iv) következik a (iii)-bol. ´ Tegyuk ¨ fel most, hogy hBi = Zm . Jelölje A a B-vel ekvivalens HNF matrixot. ´ Ekkor A ∈ Mm,m (Z) melyre hBi = hAi = Zm teljesul. ¨ Mivel az I egységmatrix ´ sorai a Zm csoportot generalj ´ ak, ´ e´ s az egységmatrix ´ HNF alaku, ´ 1.5.8 tétel miatt A = I, azaz B sor-ekvivalens I-vel. Ekkor azonban, 1.6.1 lemma szerint léteznek P1 , . . . , Pk ∈ GLm (Z) melyekkel, A = Pk · · · P1 = Pk · · · P1 teljesul, ¨ azaz (iv)-b˝ol következik (v). Mivel az elemi matrixok ´ unimodularisak, ´ (v)-b˝ol nyilvan ´ következik (i). 2 K¨ ovetkezmény 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Í T AS ´ ıtas ´ az egyik iranyban ´ teljesul. ¨ Tegyuk ¨ fel, hogy létezik a feltételeket kielég´ı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.


23

megfelel egy elemi sormuveletnek, ˝ ezeket a sormuveleteket ˝ ford´ıtott sorrendben az A matrixon ´ végrehajtva 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övetkezményben talalhat ´ o´ P transzformal ´ o´ matrix ´ meghataroz ´ as ´ ara ´ is. A transzformal ´ o´ matrixot ´ a 1. algoritmus egyszeru ˝ modos´ ´ ıtasa ´ seg´ıtségével megkaphatjuk. Az algoritmus elején a P matrixot ´ az egységmatrixnak ´ inicializaljuk. ´ Kés˝obb az algoritmus futasa ´ soran ´ minden M matrixszal ´ végzett sor-muvelet ˝ utan ´ a P matrixszal ´ is elvégezzuk ¨ ugyanazt a sor-muveletet. ˝ Az algoritmus végén a P matrix ´ valoban ´ a transzformal ´ o´ matrix ´ lesz.

1.7. Smith normál forma Ebben a részben az egész 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ét egész matrix ´ ekvivalens, ha az egyik megkaphato´ a masikb ´ ol ´ elemi sor- e´ s oszlopmuveletek ˝ seg´ıtségével. A következ˝o all´ ´ ıtas ´ a HNF-nél 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égrehajtva egy matrixot ´ kanonikus alakra hozhatunk. Azt mondjuk, hogy egy egész matrix ´ A Smith normal ´ formaj ´ u, ´ ha (i) létezik r, ugy ´ hogy Ai,i > 0 minden i 6 r esetén; (ii) A minden mas ´ eleme zéro´ (azaz A diagonalis ´ matrix ´ e´ s a nulla sorok a végén talalhat ´ ok); ´ (iii) i ∈ {1, . . . , r − 1} esetén, Ai,i osztoja ´ Ai+1,i+1 -nek. Jegyzet friss´ ıtve:

2006. december 12.

24

Abel-csoportok

Tétel 1.7.2 Minden egesz ´ matrix ´ ekvivalens egy Smith normal ´ formaban ´ lev ´ o˝ matrixszal. ´ ´ . Az alabbiakban B IZONYÍ 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ör egy nem-nulla Mi,j elemet a matrixban. ´ Ha nincs ilyen elem, akkor M a zéro-m ´ atrix, ´ ami SNF alaku, ´ tehat ´ nincs több tennivalonk. ´ Legyen tehat ´ Mi,j 6= 0. Célunk, hogy elemi sor- e´ s oszlopmuveletekkel ˝ elérjuk, ¨ hogy a matrix ´ i-dik soraban ´ e´ s j-dik oszlopaban ´ lév˝o elemek az Mi,j elem többszörösei legyenek. Tegyuk ¨ fel, hogy Mi,j nem osztoja ´ az Mk,j elemnek. Végezzunk ¨ maradékos 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ékét k-ra. Ezek utan ´ az Mi,j tovabbra ´ is nem-nulla, de az abszolut´ ´ ertéke csökkent az el˝oz˝oekhez képest. Ha Mi,j nem osztoja ´ valamely Mi,k elemnek, akkor az el˝oz˝oekhez hasonloan, ´ maradékos osztast ´ végzunk: ¨ 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ékét k-ra valtoztatjuk. ´ Ezt addig csinaljuk, ´ m´ıg Mi,j osztoja ´ lesz minden i-dik sorbeli e´ s j-dik oszlopbeli elemnek. Ez véges id˝o utan ´ nyilvan ´ teljesulni ¨ fog, mert minden fenti lépés utan ´ csökken az Mi,j abszolut ´ e´ rtéke anélkul, ¨ hogy nullav ´ a´ valna. ´ Ha egyszer elértuk, ¨ 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égével elérhetjuk, ¨ 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égével kapunk egy (1.3) alaku ´ matrixot. ´ A fenti gondolatmenetet rekurz´ıvan ismételve a C matrixra, ´ egy diagonalis ´ matrixot ´ kapunk, melyre az SNF defin´ıcioj ´ anak ´ (i)–(ii) feltételei teljesulnek. ¨ Legyenek d1 = M1,1 , . . . , dr = Mr,r a diagonalis ´ matrix ´ nem-nulla elemei. Ha Jegyzet friss´ ıtve:

2006. december 12.


25

di |di+1 minden i ∈ {1, . . . , r − 1} esetén, akkor a matrixunk ´ mar ´ SNF, tehat ´ az all´ ´ ıtasunkat ´ igazoltuk. Tegyuk ¨ fel, hogy ez nem teljesul ¨ valamely i esetén. Jelölje d a gcd(Mi,i , Mi+1,i+1 ) legnagyobb közös 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önnyu ˝ szamol ´ as ´ mutatja, hogy | det R| = | det L| = 1, tehat ´ L e´ s R unimodularis ´ matrixok. ´ Tovabb ´ a, ´ a LMR matrix ´ pontosan ugyanugy ´ néz ki mint az M matrix, ´ csak az i-dik atl ´ oelem ´ helyén gcd(Mi,i , Mi+1,i+1 ) az (i + 1)-dik atl ´ oelem ´ helyén pedig lcm(Mi,i , Mi+1,i+1 ) talalhat ´ o. ´ Megmutatjuk, hogy a fenti eljar ´ as ´ seg´ıtségével egy diagonalis ´ matrixb ´ ol ´ SNF matrixot ´ nyerhetunk. ¨ Legyenek d1 , . . . , dr a diagonalis ´ matrixunk ´ elemei. Hajtsuk végre az eljar ´ ast ´ el˝oször a (d1 , d2 ), majd a (d1 , d3 ), e´ s sorban minden (d1 , di ) parra, ´ ahol i 6 r. Az eljar ´ as ´ végen az uj ´ d1 elem a régi d1 , . . . , dr elemek legnagyobb közös osztoja ´ lesz, i > 2 esetén pedig az uj ´ di elem a régi d1 e´ s di elemek legnagyobb közös többszöröse. Specialisan, ´ ezzel azt is elértuk, ¨ hogy d1 |di teljesul ¨ minden i ∈ {1, . . . , r} esetén. Tegyuk ¨ fel tehat, ´ hogy a diagonalis ´ matrixunkban ´ d1 osztoja ´ minden di elemnek. Végezzuk ¨ 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égi d2 , . . . , dr elemek legnagyobb közös osztoja ´ lesz, illetve, hogy, az uj ´ d2 osztoja ´ lesz az uj ´ d3 , . . . , dr elemeknek. Jegyezzuk ¨ meg, hogy a d1 elemet ebben a lépésben nem valtoztattuk ´ meg. Mivel d1 osztoja ´ volt a régi d2 , . . . , dr elemeknek, az uj ´ d2 pedig ezek legnagyobb ¨ közös osztoja, ´ ´ıgy kapjuk, hogy d1 osztja az uj ´ d2 -t. Osszefoglalva, a masodik ´ lépés utan ´ egy olyan diagonalis ´ matrixot ´ kapunk melyben d1 |d2 e´ s, minden i ∈ {3, . . . , r} esetén, d2 |di. Ezek utan ´ nyilvanval ´ o, ´ hogy az eljar ´ ast ´ folytatva valoban ´ SNF matrixot ´ nyerunk. ¨ 2 Példa 1.7.3 Tekintsuk ¨ a következ˝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ételben 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ölje S1 a fenti sorban lév˝o utolso´ matrixot. ´ Az S1 matrix ´ diagonalis, ´ de még nem SNF. Miel˝ott tovabbl´ ´ epunk, ¨ hatarozzunk ´ meg olyan P1 , Q1 ∈ GL3 (Z) matrixokat ´ melyekkel P1 MQ1 = S1 teljesul. ¨ Ilyen matrixokat ´ a következ˝o egyszeru ˝ eljar ´ assal ´ talalunk. ´ Legyenek el˝oször P1 = Q1 = I, majd a fenti lépéseket imitaljuk ´ a P1 e´ s Q1 matrixokon ´ a következ˝oképpen. Amikor a fenti eljar ´ asban ´ sormuveletet ˝ hajtunk végre, hajtsuk végre ugyanazt a sormuveletet ˝ a P1 matrixon., ´ ha pedig oszlopmuveletet ˝ végzunk, ¨ végezzuk ¨ el ugyanazt az oszlopmuveletet ˝ a Q1 matrixon. ´ Jegyezzuk ¨ meg, hogy az (1), (2), (3), e´ s (4) Jegyzet friss´ ıtve:

2006. december 12.


27

lépésekben végeztunk ¨ sormuveleteket, ˝ az (5) lépésben pedig oszlopmuveletet ˝ (az (5) lépés valoj ´ aban ´ sormuveletk´ ˝ ent is felfoghato, ´ de tekintsuk ¨ most itt oszlopmuveletnek). ˝ Végezzuk ¨ 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égezzuk ¨ 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étel bizony´ıtas ´ aban ´ ismertetett eljar ´ as ´ szerint az S1 matrixot ´ tovabb ´ transzformalhatjuk. ´ Alkalmazzuk az eljar ´ ast ´ az S1 matrix ´ els˝o két diagonalis ´ elemére. 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 


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év˝o matrixb ´ ol ´ a masodik ´ e´ s harmadik sorok, illetve ugyanezen oszlopok cseréje 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égrehajtjuk 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áns faktorok 1.8. Elemi osztok Azt a tényt, hogy, a HNF-hez hasonloan, ´ az SNF is egyértelmu, ˝ az invarians ´ faktorok seg´ıtségével igazoljuk. Tegyuk ¨ fel, hogy A ∈ Mm,n (Z), legyenek I ⊆ {1, . . . , m}, J ⊆ {1, . . . , n} e´ s jelölje AI,J az I-beli indexu ˝ sorok, illetve a Jegyzet friss´ ıtve:

2006. december 12.


29

J-beli indexu ˝ oszlopok altal ´ meghatarozott ´ almatrixot. ´ Ha 1 6 k 6 min{m, n}, akkor jelölje δk (A) a det AI,J aldeterminansok ´ legnagyobb közös osztoj ´ at, ´ ahol |I| = |J| = k. Specialisan ´ δ1 (A) jelöli a matrix ´ elemek legnagyobb közös osztoj ´ at, ´ δ2 (A) jelöli a (2 × 2)-es aldeterminansok ´ legnagyobb közös 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Í T AS ¨ fel, hogy A, B ∈ Mm,n (Z). Elegend˝o belatni, ´ hogy egy sor- illetve oszlopmuvelet ˝ nem valtoztat ´ a δk mennyiségeken. Itt ezt az all´ ´ ıtast ´ csak sormuveletekre ˝ igazoljuk, mivel oszlopmuveletekre ˝ a bizony´ıtas ´ ugyanugy ´ történik. 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örtén˝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éjével. 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öli azt a halmazt melyet az I-b˝ol kapunk az i e´ s j indexek kicserélésével. 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értése nélkul, ¨ 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év˝o elemek. Ekkor

BI,J



  =  

a1,1 + αc1 · · · a1,k + αck a2,1 ··· a2,k .. .. . . ak,1 ··· ak,k


     

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ét 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ét esetben det BI,J egész egyutthat ¨ os ´ linearis ´ kombinaci ´ oja ´ det AI1 ,J1 alaku ´ mennyiségeknek, ahol |I1 | = |J1 | = k, e´ s δk (A)|δk (B) következik. 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értelmu. ˝ K¨ ovetkezmény 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övetkezesk ´ 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Í 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özös 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övetkezik, 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én. Tegyuk ¨ fel, hogy az all´ ´ ıtas ´ igaz i − 1-re. A következmény els˝o all´ ´ ıtasa ´ miatt, a1 · · · ai = δi (A), illetve b1 · · · bi = δi (B). Mivel δi (A) = δi (B) e´ s, az indukcios ´ feltevés 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.


31

1.8.1 lemma e´ s a 1.8.2 következmény szerint ezek a mennyiségek az jellemzik ekvivalencia osztalyokat, ´ abban az e´ rtelemben, hogy két matrixr ´ ol ´ ezen mennyiségek ismeretében eldönthet˝o, hogy ekvivalensek-e.

1.9. Végesen generált 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övetkezmény szerint, a ϕ : ei 7→ xi leképezés egyértelmuen ˝ kiterjeszthet˝o egy ϕ : Zn → G epimorfizmussa. ´ A kiterjesztést 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éges sok elemmel generalhat ´ o, ´ tehat ´ létezik egy M ∈ Mm,n (Z) matrix ´ mellyel ker ϕ = hMi. Ez a gondolatmenet mutatja, hogy a következ˝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ör egy egyszeru, ˝ majd két bonyolultabb példat. ´ Példa 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élda 1.9.3 Legyenek a, b, c pozit´ıv egészek, 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)


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éle 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ölik a szobanforg ´ o´ csoportok kommutator ´ részcsoportjait. 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élda 1.9.4 Legyenek l, m, n egész szamok, ´ e´ s jelölje ∆(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önnyu ˝ latni, ´ hogy a ∆(l, m, n) haromsz¨ ´ og csoport kommutator ´ részcsoport szerinti faktora a ha, b, c | 2a = 0, 2b = 0, 2c = 0, la + lb = 0, ma + mc = 0, nb + nc = 0i csoport. Jelölje 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és˝obbiekben tovabbi ´ muveleteket ˝ fogunk végezni, példaul ´ meghatarozzuk ´ a kommutator ´ szerinti faktorcsoportok izomorfia-osztaly ´ at. ´ Igazoljuk most, hogy ekvivalens matrixok ´ izomorf csoportokhoz vezetnek. Jegyzet friss´ ıtve:

2006. december 12.


33

Tétel 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övetkezok ˝ 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ért feltehetjuk, B IZONYÍ T AS ¨ hogy P egy egységmatrix, ´ e´ s AQ = B, ahol Q egy unimodularis ´ matrix. ´ Definialjuk ´ n n ¯ az f : Z → Z leképezést a következ˝oképpen: x = (x1 , . . . , xn ) esetén 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ért f -b˝ol szarmaztathat ´ o´ az f : Zn / hAi → Zn / hBi izomorfizmus: f (x + hAi) = f¯(x) + hBi (igazoljuk gyakorlatként, hogy f jol ´ definialt ´ n n ∼ ´ ıtas ´ aban ´ szerepl˝o e´ s tényleg izomorfizmus). Tehat ´ Z / hAi = Z / hBi e´ s a tétel all´ f leképezés valoban ´ izomorfizmus. 2 Példa 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éldaban Hasznaljuk ´ tovabb ´ ebben a példaban ´ a 1.7.3 példa jelöléseit. 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étel miatt, G = Z / hMi = Z / hSi. A Z / hSi csoportot a következ˝oképpen 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étlen derul ¨ ki. Az 1.9.5 tétel szerint a G csoport (1.4) e´ s (1.5) alakjai között a Q matrix ´ adja meg a kapcsolatot. Valoban, ´ némi 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épezés kiterjeszthet˝o az (1.4) e´ s (1.5) csoportok közötti 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étel miatt, elemi sor- e´ s oszlopmuveletek ˝ nem valtoztatj ´ ak ´ meg a matrixhoz ´ tartozo´ elemi Abel-csoport izomorfia osztaly ´ at. ´ Ezeken k´ıvul ¨ még egy muveletet ˝ végezhetunk ¨ a matrixunkkal ´ az izomorfia osztaly ´ megvaltoz´ tatasa ´ nélkul. ¨ 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Í 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övetkez˝o alakban:

a0 , a1 , . . . , an | a0 = 0, A1,1 a1 + · · · + A1,n an = 0, . . . , Am,1 a1 + · · · + Am,n an = 0 .

A két prezentaci ´ ob ´ ol ´ latszik, ´ hogy a két csoport egymassal ´ természetesen izomorf. 2 Jegyzet friss´ ıtve:

2006. december 12.


35

1.10. Végesen generált Abel-csoportok alaptétele Ebben a fejezetben belatjuk, ´ hogy minden végesen 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Í T AS ´ Ekkor léteznek 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égtelen 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égesrendu ˝ elemek egy részcsoportot alkotnak. Ennek a részcsoportnak a neve G-beli torziocsoport, ´ jele pedig T (G). Tétel 1.10.2 (Végesen generált Abel-csoportok alaptétele) 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Í T AS ´ generalt ´ Abel-csoport. Ekkor az 1.9.1 n lemma szerint G ∼ = Z / hMi, ahol M ∈ Mm,n (Z). Jelölje A az M-mel ekvivalens SNF matrixot, ´ e´ s legyenek a1 , . . . , ak az A nullat ´ ol ´ kul¨ ¨ onböz˝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értelmus´ ˝ egét. Az egyértelmus´ ˝ eget el˝oször véges csoportokra mutatjuk meg. Tegyuk ¨ fel, hogy G∼ = Zm1 ⊕ Zm2 ⊕ · · · ⊕ Zmℓ , = Zn1 ⊕ Zn2 ⊕ · · · ⊕ Znk ∼ ahol az ni e´ s az mj szamok ´ kielég´ıtik a tétel feltételeit. Az altal ´ anoss ´ ag ´ megsértése nélkul ¨ 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öljék 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étezik egy ϕ : Zk / hAi → Zk / hBi izomorfizmus. Mivel, az A matrix ´ diagonalis, ´ a G1 csoportnak létezik egy x1 , . . . , xk generator-rendszere, ´ mellyel G1 = hx1 i ⊕ · · · ⊕ hxk i ∼ = Zn1 ⊕ · · · ⊕ Znk . Hasonloan, ´ a G2 csoportban létezik egy y1 , . . . , yk generator-rendszer ´ melyre G2 = hy1 i ⊕ · · · ⊕ hyk i ∼ = Zr1 ⊕ · · · ⊕ Zrk

teljesul. ¨ Tegyuk ¨ fel, hogy i, j ∈ {1, . . . , k} esetén, 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.


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övetkez˝oképpen:

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éges, ´ı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én ψ(a) = aQ. Mivel Q unimodularis, ´ az 1.9.5 tétel bizony´ıtas ´ aban ´ latott ´ modon ´ igazolhatjuk, hogy ψ egy izomorfizmus. Ha a ∈ hAi, akkor a + hAi = 0 + hAi, e´ s ezért 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ég miatt, |Zk : ψ(hAi)| = |Zk : hAi | = |Zk : hBi |, tehat ´ ψ(hAi) = hBi. Mivel hBi = ψ(hAi) = hAQi, ezért, az 1.5.8 tétel miatt, AQ ekvivalens a B matrixszal, ´ e´ s ´ıgy a 1.7.1 lemma miatt A e´ s B ekvivalensek. Mivel mindkét matrix ´ SNF alaku, ´ A = B, amib˝ol, 1 6 i 6 k esetén, ni = ri következik. Következésképp az ri -k között nincsenek egyesek, e´ s ´ıgy ni = mi minden i-re. Tehat ´ a tételben szerepl˝o fel´ıras ´ véges csoportok esetén egyértelmu. ˝ Tegyuk ¨ most fel, hogy G egy nem feltétlenul ¨ véges csoport e´ s G felbonthato´ kétféleképpen: 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éges 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övetkezik. Masr´ ´ eszr˝ol viszont r s G/T (G) ∼ =Z ∼ =Z,


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éldakban ´ szerepl˝o Abel-csoportokat az 1.10.2 szempontjab ´ ol. ´ Példa 1.10.3 Az 1.9.2 tételben szerepl˝o G Abel-csoport Z3 ⊕Z5 ⊕Z fel´ırasa ´ nem felel meg a 1.10.2 tétel feltételeinek. 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ével, tehat ´ Z3 ⊕Z5 = ha + bi, e´ s ´ıgy G = ha + bi ⊕ Z ∼ ´ fel´ıras ´ mar ´ pontosan olyan mint az = Z15 ⊕ Z. Ez utobbi alaptételben szerepl˝o. Példa 1.10.4 Szam´ ´ ıtsuk ki az 1.9.3 példaban ´ szerepl˝o Aa,b,c e´ s B a,b,c csoportok kanonikus alakjat. ´ Az 1.10.2 tétel szerint, ehhez meg kell hataroznunk ´ a példakban ´ 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övetkezmény szerint, s1 megegyezik az A matrix ´ elemeinek legnagyobb közös osztoj ´ aval, ´ az s2 pedig az A matrix ´ determinans ´ aval. ´ Ezért, s1 = 1 e´ s s2 = 2(a + b + c), az A matrix ´ pedig ekvivalens a következ˝o SNF matrixszal: ´ ! 1 0 S= . 0 2(a + b + c) Következésképp, 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égtelen 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égtelen 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éshez hasonloan ´ kapjuk, hogy r1 = 1, r2 pedig a B-beli (2 × 2)-es aldeterminansok ´ legnagyobb közös 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éter esetén fennall, ´ hogy Aa,b,c ∼ =B .


2006. december 12.


39

Példa 1.10.5 Tekintsuk ¨ most az 1.9.4 példaban ´ 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övetkezményb˝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özös 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özul ¨ legalabb ´ egy paratlan; ´ s1 = 2, ha l, m, e´ s n közul ¨ mindegyik paros; ´ e´ s s2 =

(

1, ha l, m, e´ s n közul ¨ legalabb ´ kett˝o paratlan; ´ 2, ha l, m, e´ s n közul ¨ 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özul ¨ legalabb ´ kett˝o paratlan; ´  Z2 , A(l, m, n) ∼ = Z2 ⊕ Z2 , ha l, m, e´ s n közul ¨ pontosan egy paratlan; ´   Z2 ⊕ Z2 ⊕ Z2 ha l, m, e´ s n közul ¨ mindegyik paros. ´

Tehat, ´ az A(l, m, n) csoport minden esetben egy nemtrivialis ´ véges csoport, melynek rendje, az l, m, e´ s n paraméterekt˝ol fugg˝ ¨ oen, 2, 4, vagy 8.

1.11. Moduláris HNF e´ s SNF Ebben a fejezetben egy olyan technikat ´ ismertetunk, ¨ mellyel a 1.5.3 tétel el˝ott ismertetett jelenség, nevezetesen, hogy a HNF szam´ ´ ıtasa ´ soran ´ a közbuls˝ ¨ o matrixok ´ elemei kezelhetetlenul ¨ nagyok lesznek, elkerulhet˝ ¨ o. A Hermite normal ´ format ´ szam´ ´ ıto´ 1. algoritmus e´ s az 1.7.2 tétel bizony´ıtas ´ aban ´ szerepl˝o Smith normal ´ format ´ szam´ ´ ıto´ algoritmus inkabb ´ csak elméleti jelent˝oségu, ˝ a gyakorlatban el˝ofordulo´ problémakra ´ egyik sem igazan ´ alkalmazhato. ´ Példaul, ´ a Smith normal ´ formara ´ vonatkozo´ algoritmus, mar ´ (20 × 20)-as egyszamjegy ´ u ˝ elemeket tartalmazo´ input matrix ´ esetén sem praktikus, mivel a szam´ ´ ıtas ´ soran ´ a matrixban ´ akar ´ több szazezer ´ szamjegy ´ u ˝ elemek is keletkeznek. Az Jegyzet friss´ ıtve:

2006. december 12.

40

Abel-csoportok

output matrix ´ azonban mindkét algoritmus esetén viszonylag kis elemekb˝ol all. ´ Természetes tehat, ´ hogy megprob ´ aljuk ´ a HNF e´ s SNF matrixokat ´ modulo´ valamilyen jol ´ megvalasztott ´ egész szam ´ szerint szam´ ´ ıtani. Ehhez a stratégiahoz ´ tartalmaz néhany ´ 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öli az M-beli (k × k)-s aldeterminansok ´ legnagyobb közös osztoj ´ at. ´ Emlékezzunk ¨ 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égekb˝ol az 1.8.2 következményben latott ´ modon. ´ Legyen M egy egész e´ rtéku ˝ matrix ´ e´ s tegyuk ¨ fel, hogy meg szeretnénk 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Í T AS aldeterminans, ´ de nincs ennél nagyobb. Mas ´ szoval, ´ δr (M) 6= 0, de, minden k > r esetén, δk (M) = 0. A 1.8.2 következmény miatt, ekkor r pontosan a nem nulla invarians ´ faktorok szama. ´ 2 A bevezetésben eml´ıtettuk, ¨ hogy a HNF e´ s SNF matrixokat ´ modulo´ egy jol ´ megvalasztott ´ egész szam ´ szerint szam´ ´ ıtjuk. A következ˝o lemma seg´ıt a modulus megvalaszt ´ as ´ aban ´ Lemma 1.11.2 (Hadamard korlát) Ha A ∈ Mn,n (R), akkor | det A| 6

n n Y X i=1

Ai,j

j=1

2

!1/2

.

Egész matrixok ´ esetén az el˝oz˝o lemmab ´ ol ´ a következik az alabbi ´ all´ ´ ıtas. ´ K¨ ovetkezmény 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


j

i=1

2006. december 12.


41

ahol a szorzat a matrix ´ nem-nulla soraira törtenik. ´ Ha m 6 n e´ s A ∈ Mm,n (Z), akkor az el˝oz˝o következményben 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övetkezmény szerinti korlattal. ´ Ha n e´ s k tetsz˝oleges egész szamok, ´ akkor jelölje [k]n azt az egyetlen 0 e´ s n − 1 közötti egész 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én, az R egységeit, mas ´ szoval ´ invertalhat ´ o´ elemeit, az U(R) szimbolum ´ jelöli. Egy n pozit´ıv egész szam ´ esetén, tekintsuk ¨ most a Zn halmazt gyur ˝ uk´ ˝ ent, e´ s jelöljuk ¨ elemeit a 0 e´ s n − 1 közötti egész szamokkal. ´ Ha k ∈ Z, akkor a [k]n szamot ´ ´ıgy tekinthetjuk, ¨ mint a Zn gyur ˝ u ˝ elemét. Jol ´ ismert, hogy a Zn gyur ˝ uben ˝ egy [k]n elem egység, 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Í 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 ). Így fm,n (U(Zm )) ⊆ U(Zn ). Jelölje, f¯m,n a fm,n |U (Zm ) leképezést. 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én 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és miatt, f¯m,l e´ s f¯l,n szurjekt´ ¨ ıvek, f¯m,n is az. A f¯m,n leképezés 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övetkezik, e´ s ´ıgy u ∈ U(Zm ) e´ s u ∈ f¯m,n (U(Zm )). Ha p ∤ n, akkor a k´ınai maradéktétel következtében a következ˝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öbbszöröse, akkor elegend˝o az invarians ´ faktorok d szerinti maradékosztalyait ´ meghatarozni. ´ A δr (M) szam ´ egy többszörösét talalhatunk ´ példaul ´ ugy, ´ hogy keresunk ¨ néhany ´ nem-nulla M-beli (r×r)-s aldeterminanst, ´ e´ s kiszamoljuk ´ azok legnagyobb közös osztoj ´ at. ´ A következ˝okben azt targyaljuk, ´ hogyan lehet, ilyen aldeterminansokat ´ talalni. ´ Ha M ∈ Mm,n (Z), akkor jelölje [M]d azt a matrixot ´ melyet ugy ´ kapunk, hogy M minden elemét redukaljuk ´ d szerint. Az alabbi ´ sormuveleteket ˝ modulo´ d elemi sormuveleteknek ˝ h´ıvjuk: (i) két sor felcserélése; (ii) egy sor szorzasa ´ egy d-hez relat´ıv pr´ım egésszel; (iii) egy sor egész többszörösének hozzaad ´ asa ´ egy masik ´ sorhoz. A fenti sormuveleteket ˝ modulo´ d végezzuk, ¨ azaz, a sormuveletek ˝ elvégzése utan ´ a kiszam´ ´ ıtjuk matrixelemek ´ d szerinti redukaltj ´ at. ´ Két matrixot ´ sorekvivalensnek mondunk modulo´ d, ha a masodik ´ megkaphato´ az els˝ob˝ol modulo´ d elemi sormuveletek ˝ seg´ıtségével. 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érelemek osztjak ´ d-t. Tétel 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Í T AS ´ ıtas ´ igazolasa, ´ lényegében a 1.4.2 els˝o all´ ´ ıtas ´ anak ´ bizony´ıtas ´ aval ´ egyezik meg. Az egyetlen eltérés, hogy ha c a d-hez relat´ıv pr´ım, Jegyzet friss´ ıtve:

2006. december 12.


43

akkor c-nak létezik 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övetkezményekhez hasonloan ´ bizony´ıtjuk. Az egyetlen lényeges kul¨ ¨ onbség, hogy a vezérelemek d osztoi ´ kell, hogy legyenek. Tegyuk ¨ fel, hogy a az i-dik sor vezéreleme 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étezik egy w ∈ Z melyre wv ≡ 1 (mod d/u) tejlesul. ¨ Ekkor w egység a Zd/u gyur ˝ uben, ˝ ezért a 1.11.4 lemma miatt feltehetjuk, ¨ hogy w egység 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éreleme u lesz, ami a feltételek szerint osztoja ´ d-nek. 2 Legyen M ∈ Mm,n (Z) e´ s legyen d egy egész szam. ´ Jelölje A az M matrixszal ´ modulo´ d sor-ekvivalens HNF matrixot. ´ Az A matrixban ´ lév˝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étel), következik, hogy rang d M 6 rang M. Egy matrix ´ d-rangjat ´ meghatarozhatjuk ´ modularis ´ aritmetika seg´ıtségével, ´ıgy a szamol ´ as ´ soran ´ csak olyan egészekkel kell dolgoznunk melyek abszolut ´ e´ rtéke legfeljebb d. Ha d-t egy elég nagy pr´ımnek valasztjuk, ´ akkor nagy valosz´ ´ ınus´ ˝ eggel a d-rang megegyezik a ranggal. A következ˝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özo˝ 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övetkezménybeli B IZONYÍ T AS korlat. ´ Legyen C egy A-beli négyzetes almatrix ´ melyben a sorok szama ´ több mint r. Ekkor, minden i esetén, 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ésben mondottak miatt, rang A > r, ezért az A rangja pontosan r. 2 Az el˝oz˝o lemma seg´ıtségével könnyen meghatarozhatjuk ´ egy A egész 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övetkez˝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özo˝ 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éktétel szerint az B IZONYÍ T AS x ≡ d1 mod p1 .. . x ≡ ds mod ps kongruencia-rendszernek létezik x megoldasa, ´ e´ s x egyértelmu ˝ modulo´ p1 · · · ps . Ha K jelöli a Hadamard korlatot, ´ akkor 2| det A| 6 2K < p1 · · · p2 , e´ s ´ıgy −K e´ s K közé a kongruencia-rendszernek legfeljebb egy megoldasa ´ esik, ami megegyezik a det A mennyiséggel. 2 Az el˝obbi tételben szerepl˝o d determinanst ´ meghatarozhatjuk ´ a modulo´ pi maradékaibol ´ a következ˝o lemma alapjan. ´ A lemma bizony´ıtas ´ at ´ gyakorlatnak hagyjuk. Lemma 1.11.8 Legyenek p1 , . . . , ps egymast ´ ol ´ kul¨ ¨ onbözo˝ 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égyzetes M matrix ´ determinansa ´ modulo´ p könnyen meghatarozhat ´ o. ´ A matrixot ´ HNF alakra hozzuk, de a HNF alak szam´ ´ ıtasa ´ közben a következ˝okre ugyel ¨ unk. ¨ A HNF szam´ ´ ıtasa ´ elején 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.


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éktétel algoritmus Eközben 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ég pedig egyszeruen ˝ az A matrix ´ diagonalis ´ elemeinek a szorzata. Ezek utan ´ a 1.11.7 lemma alapjan ´ egy négyzetes matrix ´ determinansa ´ kiszam´ ´ ıthato. ´ A fentiek alapjan, ´ egy A matrix ´ invarians ´ faktoraira könnyen adhatunk fels˝o korlatot. ´ El˝oször 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önnyen modos´ ´ ıthato´ ugy, ´ hogy inputja egy M egész e´ rtéku ˝ 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ésben ismertetett modon. ´ A D szam ´ rendelkezik azzal a tulajdonsaggal, ´ hogy többszöröse az A invarians ´ faktorainak (1.8.2 következmény). 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özös osztoj ´ at. ´ Az invarians ´ faktorokat modulo´ D szerint hatarozzuk ´ meg, ahol D az el˝oz˝o bekezdésben definialt ´ szam. ´ Ehhez elemi sor- e´ s oszlopmuveleteket ˝ hajtunk végre modulo´ d. A modulo´ d elemi oszlopmuveletek ˝ a modulo´ d elemi sormuveletek ˝ analogjai. ´ Két egész 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égével. 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övetkez˝o tételt a 1.7.2 tétel e´ s a 1.8.2 következmény megfelel˝o all´ ´ ıta´ saihoz hasonloan ´ bizony´ıtjuk, illetve felhasznaljuk ´ a 1.11.5 tétel bizony´ıta´ san ´ al ´ targyalt ´ e´ szrevételeket.

Tétel 1.11.9 Minden egesz ´ matrix ´ modulo´ d ekvivalens pontosan egy modulo´ d SNF matrixszal. ´ Ha A egy egész matrix, ´ akkor az A-val ekvivalens modulo´ d SNF matrix ´ diagonalis ´ elemeit az A modulo´ d invarians ´ faktorainak h´ıvjuk.

Tétel 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öbbszöröse, 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Í T AS ´ Mivel, minden i estén, di | d, a modulo´ d SNF megegyezik az [A]d matrixszal. ´ Mivel d > dr , a [d]d = 0 az egyetlen lehetséges redukcio´ melyet az SNF matrixon ´ el kell végeznunk. ¨ 2 A fenti eljar ´ ast ´ alkalmazva immar ´ viszonylag nagy méretu ˝ egész matrixok ´ SNF alakjat ´ is meghatarozhatjuk. ´ Lassunk ´ egy példat. ´ Jegyzet friss´ ıtve:

2006. december 12.


47

Példa 1.11.11 Szam´ ´ ıtsuk ki a következ˝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ételben 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éku ˝ elem több 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övetkez˝o lépés, hogy, az 1.11.7 utan ´ ismertetett modszerrel, ´ keressunk ¨ a matrixban ´ egy (10 × 10)-es nem-nulla aldeterminanst. ´ Ilyet alkotnak példaul ´ az 1, 2, 3, 4, 6, 7, 8, 9, 10, 12 indexu ˝ sorok e´ s az ugyanezen indexu ˝ oszlopok metszetében lév˝o elemek; a kapott aldeterminans ´ 720.954. A 1.7.2 tételben ismertetett eljar ´ ast ´ elvégezzuk ¨ 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). Így az 1.11.10 tétel alapjan, ´ a fenti matrix ´ invarians ´ faktorai: 1, 1, 1, 1, 1, 1, 1, 1, 1, 720.954. A szam´ ´ ıtas ´ a GAP rendszerben néhany ´ tized masodperc ´ CPU id˝ot vesz igénybe.

1.12. Rácsok Legyen G a Zk csoport egy részcsoportja. Ebben a fejezetben szeretnénk rövid vektorokbol ´ all ´ o´ bazis ´ at ´ talalni ´ a G csoportnak. A problémat ´ tagabban ´ is Jegyzet friss´ ıtve:

2006. december 12.

48

Abel-csoportok

vizsgalhatjuk, ´ e´ s tekinthetjuk ¨ a Rn vektortér szabad Abel-részcsoportjait. Ebben a szakaszban az Rn halmaz egy R feletti n-dimenzios ´ vektortér. Ezen a vektortéren e´ rtelmezzuk ¨ a skalarszorz ´ ast ´ vagy mas ´ néven bels˝o szorzast: ´ P n v = (v1 , . . . , vn ), u = (u1 , . . . , un ) ∈ R esetén v · u = i vi ui. Egy v vektor |v| hossza √ a v · v mennyiség. Emlékezzunk, ¨ hogy az R egy X részhalmazat ´ 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örul ¨ egy kompakt B gömb melyre X ∩ B veges. ´ ´ . Ha X diszkrét akkor az origo´ nem torlod B IZONYÍ T AS ´ asi ´ pontja az X halmaznak, e´ s a k´ıvant ´ gömb létezik. Tegyuk ¨ fel most, hogy B az origo´ köruli ¨ ε sugaru ´ kompakt gömb. Legyen x egy torlod ´ asi ´ pontja az X csoportnak. Ekkor létezik y csoportelem melyre igaz, hogy az y középpontu, ´ ε sugaru ´ C gömb bels˝o pontként tartalmazza az x-et, ´ıgy az is igaz, hogy C végtelen sok csoportelemet tartalmaz. Ekkor azonban, B = C − y = {c − y | c ∈ C} e´ s ´ıgy B is végtelen sok csoportelemet tartalmaz. Mivel B valaszt ´ asa ´ tetsz˝oleges volt, az all´ ´ ıtas ´ következik. 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Í T AS ¨ fel el˝oször, hogy léteznek 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épezés. Mivel ϕ linearis, ´ ϕ egy homeomorfizmus. Legyen M = {|α1 x1 + · · · + αk xk | | α1 , . . . , αk ∈ R, α12 + · · · + αk2 = 1}. Jegyezzuk ¨ meg, hogy M az egységgömb ϕ altali ´ képe. Mivel az egységgömb kompakt, M is kompakt. Mivel x1 , . . . , xk linearisan ´ fuggetlenek, ¨ a nullvektor nem eleme M-nek. Ezért létezik a nullvektor körul ¨ egy µ sugaru ´ B gömb Jegyzet friss´ ıtve:

2006. december 12.


49

melyre B ∩ M = ∅, e´ s ´ıgy minden M-beli vektor hossza legalabb ´ µ. Tetsz˝oleges β1 x1 + · · · + βk xk 6= 0 esetén, 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én kapjuk, hogy |x| > µ. A 1.12.1 lemmab ´ ol ´ következik, hogy ebben az esetben L diszkrét. Tegyuk ¨ most fel, hogy L diszkrét e´ s legyen k a L altal ´ generalt ´ altér 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ét, F egy véges halmaz. Minden i = 1, . . . , k esetén 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étezik. 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ész egyutthat ¨ os ´ linearis ´ kombinaci ´ ojak´ ´ ent. Legyen v ∈ L e´ s ´ırjuk fel a v vektort v = β1 v1 + · · · + βk vk alakban. Jelölje [βi ] e´ s {βi } a βi egész- e´ s törtrészét, 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ért, minden i esetén, {βi } = 0 e´ s βi ∈ Z. 2

Az Rn csoport egy diszkrét részcsoportjat ´ 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ér dimenzioja, ´ ami megegyezik az L szabad Abel-csoportként tekintett rangjaval. ´ Egy racsot ´ teljesnek mondunk, ha a racs ´ rangja megn egyezik az alaptér R dimenzioj ´ aval. ´ Mivel, minden racs ´ teljes az altala ´ generalt ´ R feletti vektortérben, 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. Írasban ´ 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Í T AS ´ alkotnak, léteznek pi,j e´ s qi,j egész 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észetesen 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éren vett bels˝o szorzat szmmetrikus, a GramB IZONYÍ T AS matrix ´ defin´ıcioj ´ ab ´ ol ´ következik, hogy a G(L) szimmetrikus. Legyen v1 , . . . , vk e´ s w1 , . . . , wk az L két 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étezik 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értése nélkul, ¨ hogy L teljes racs, ´ akkor a fenti A t egy invertalhat ´ o´ négyzetes 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ég neve racsdetermin rövid racsvektorok ´ hosszanak ´ a becslésére. Jegyzet friss´ ıtve:

2006. december 12.


51

Tétel 1.12.5 (Minkowski konvex test tétele) 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ény 1.12.6 Egy L racsnak ´ van olyan racsvektora ´ melynek hossza √ √ n legfeljebb n det L √ n ´ . Legyen K az origo´ középpontu ´ ag ´ u ´ kocka. EkB IZONYÍ T AS ´ 2 det L e´ lhosszus n kor K térfogata 2 det L, tovabb ´ a´ K kielég´ıti az el˝obbi tétel követelményeit. √ √ Tehat ´ L ∩ K 6= ∅. Mivel K-ban minden vektor hossza legfeljebb n n det L, az all´ ´ ıtas ´ következik. 2 Az el˝obbi következményben még jobb korlatot ´ is lehetne adni, ha nem kockat ´ hanem gömböt hasznaln ´ ank. ´

´ e1.13. A legr¨ ovidebb rácsvektor a kétdimenzios setben Jelöljön L ebben a fejezetben egy R2 -beli racsot. ´ Megmutatjuk, hogy L egy legrövidebb vektora hatékonyan megkereshet˝o. Ez az eljar ´ as ´ adja majd az alapot a következ˝o szakaszban targyaland ´ o´ Lovasz ´ redukciohoz. ´ Tétel 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övidebb L-beli racsvektor, ´ a v2 pedig egy legrövidebb v1 -tol ˝ fuggetlen ¨ racsvektor. ´ ´ . El˝oször megjegyezzuk, B IZONYÍ T AS ¨ hogy az algoritmus végrehajtasa ´ 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éges sok lépés utan All´ ´ véget e´ r. Legyen B az origo´ sugaru ´ |v1 | sugaru ´ gömb. Mivel L diszkrét, L ∩ B véges halmaz. A ciklus minden végrehajtasa ´ utan ´ a v1 vektor hossza csökken e´ s az uj ´ v1 vektor is eleme B-nek, az algoritmus véges sok lépés utan ´ véget 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étel) Output: a hv1 , v2 i racs ´ egy rövid 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övidebb 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övidebb 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égrejtasa ´ a v1 Jegyzet friss´ ıtve:

2006. december 12.


53

p vektor hosszat ´ 3/4-szeresére vagy még kisebbre csökkenti. Így a v1 vektor hossza exponencialisan ´ gyorsan csökken e´ s az algoritmus hamar véget e´ r.

´ (LLL) 1.14. Lenstra-Lenstra-Lovász redukcio Ez el˝oz˝o szakaszban megmutattuk, hogy egy kétdimenzios ´ racsban ´ egy legrövidebb vektor hatékonyan megtalalhat ´ o. ´ Sajnos egy magasabb dimenzioj ´ u ´ racsban ´ ez nem ilyen egyszeru, ˝ de egy rövid vektort (azaz olyan vektort ami egy legrövidebbt˝ol csak valamilyen ismert faktorral hosszabb) itt is talalhatunk ´ az LLL (Lenstra-Lenstra-Lovasz) ´ racsredukci ´ os ´ algoritmus seg´ıtségével. n Az R tér 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ölje v a v vektor hv1 , . . . , vk i altérre történ˝o mer˝oleges vet´ıtését. Linearis ´ algebrab ´ ol ´ ismert, hogy v P az alabbi ´ képlettel meghatarozhat ´ o: ´ k X v · vi v, v = v · vi i i=1 i P

e´ s a vet´ıtés eredménye fuggetlen ¨ az ortogonalis ´ bazis ´ valaszt ´ as ´ at ´ ol. ´ Nyilvan ´ P v ∈ hv1 , . . . , vk i, tovabb ´ a´ könnyu ˝ szamol ´ as ´ mutatja, hogy, minden 1 6 i 6 k P P esetén, (v − v ) · vi = 0, azaz v − v mer˝oleges a hv1 , . . . , vk i altérre. A következ˝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érben. Definialjuk ´ a vi vektorokat a következ˝oképpen. Legyen v1∗ = v1 e´ s, i > 2 esetén legyen vi∗ = vi − viP ahol viP a vi vektor hv1 , . . . , vi−1 i térre történ˝o ∗ i térre mer˝oleges kommer˝oleges vet´ıtése. 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én 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ért ezekre kul¨ ¨ on jelölést vezetunk ¨ be. Legyen i ∈ {1, . . . , n} e´ s j ∈ {1, . . . , i − 1} esetén 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én, e´ s ∗ ∗ |vi∗ + µi,i−1vi−1 |2 > (3/4)|vi−1 |2

minden 1 < i 6 n esetén.

(1.7)

A fenti defin´ıcioban ´ szerepl˝o (1.7) feltétel neve Lovasz ´ feltetel ´ e´ s ekvivalens 2 2 ∗ 2 ´ etelb˝ol a következ˝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én.

(1.8)

Mivel v1∗ = v1 a fenti egyenletb˝ol kapjuk, hogy 2i−1 |vi∗ |2 > |v1 |2

minden i > 1 esetén.

Vegyuk ¨ e´ szre, hogy n = 2 esetén a Gauss-algoritmus outputja redukalt. ´ A redukalt ´ bazisokat ´ jellemzi a következ˝o tétel. Tétel 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ör is all´ B IZONYÍ T AS ´ ıtjuk, hogy 2

(det L) =

n Y i=1


vi∗ · vi∗ .

2006. december 12.

(1.9)


55

Az all´ ´ ıtas ´ igazolas ´ ahoz, ´ 1 6 j < i 6 n esetén legyen µi,j a Gram-Schmidt egyutt¨ hato, ´ 1 6 i 6 n esetén legyen µi,i = 1 e´ s i < j esetén 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éget fel´ırhatjuk matrixos ´ alakban a következ˝oképpen: B = MAM t . Mivel M fels˝oharomsz¨ ´ og matrix ´ melynek atl ´ oj ´ aban ´ egyesek szerepelnek, kapjuk, hogy ´ ent det M = 1 e´ s ezért 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ésben igazolt all´ ´ ıtast ´ e´ s az 1.8 egyenl˝otlenséget 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övetkezik. 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 . Így v · v = αj2 vj∗ · vj∗ + w · w > vj∗ · vj∗ > 21−j v1 · v1 > 21−n v1 · v1 ,

amib˝ol a (ii) all´ ´ ıtas ´ következik. A (iii) all´ ´ ıtas ´ igazolas ´ ahoz ´ mutassuk el˝oször meg, hogy vi · vi 6 2i−1 vi∗ · vi∗ . Mivel v1∗ = v1 , az all´ ´ ıtas ´ i = 1 esetén 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. Így 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övetkezik, ezzel a tétel bizony´ıtasa ´ teljes. 2 A fenti tételben szerepl˝o (ii) tulajdonsag ´ lényegében azt mondja, hogy egy redukalt ´ bazis ´ els˝o vektoranak ´ hossza jol ´ közel´ıti a legrövidebb vektorok hosszat. ´ A redukalt ´ bazis ´ jelent˝oségét, jo´ tulajdonsagai ´ mellett, az a tény adja, hogy hatékonyan kiszam´ ´ ıthato. ´ Ezzel a ténnyel most nem foglalkozunk b˝ovebben, csak egy egyszeru ˝ bazisredukci ´ os ´ algoritmust ismertetunk. ¨ Az algoritmus végrehajtas ´ ahoz ´ ismerni kell a µi,j Gram-Schmidt egyutthat ¨ okat. ´ Ezeket a Gram-Schmidt eljar ´ asban ´ ismertetett modon ´ meg lehet hatarozni. ´ Tétel 1.14.3 Az 5. algoritmus veges ´ sok lep ´ es ´ utan ´ veget ´ er, ´ outputja pedig az inputvektorok altal ´ generalt ´ racs ´ egy redukalt ´ bazisa. ´


2006. december 12.


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özelebbi egész. 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´


2006. december 12.

A kurzus során először az Abel-csoportokkal kapcsolatos algoritmikus kérdésekkel

Recommend Documents