Ugrás a tartalomhoz

Új matematikai mozaik

Ambrus Gergely, Bárszi Gergely, Csikós Balázs, Frenkel Péter, Gács András, Gyárfás András, Hraskó András, Kiss Emil, Laczkovich Miklós, Lovász László, Montágh Balázs, Moussong Gábor, Pach János, Pelikán József, Recski András, Reiman István

Typotex

2. Előismeretek

2. Előismeretek

Lényegében mindaz, amit most röviden összefoglalunk, megtalálható Fried Ervin tankönyvében [4]. Ugyanebben a könyvben kódokról (például a Hamming-kódokról) is olvashatunk. A számelméleti részekhez Sárközy András [10] példatárát ajánljuk.

Szükségünk lesz a modulo p maradékosztálytest fogalmára, illetve a modulo p számolásra. (modulo p helyett röviden mod p -t írunk.) Erről részletesen Wettl Ferenc fejezetében olvashatunk, de röviden mi is áttekintjük. Például a mod 2 számolásnál Q = { 0 , 1 } a maradékosztályok halmaza, 0 + 0 = 1 + 1 = 0 , 0 + 1 = 1 + 0 = 1 , 0 · 0 = 0 · 1 = 1 · 0 = 0 , 1 · 1 = 1 . Ha p prímszám, akkor Q = { 0 , 1 , , p - 1 } a lehetséges maradékok halmaza, és Q elemeit úgy adjuk vagy szorozzuk össze, hogy egész számoknak tekintve őket elvégezzük a műveletet, majd az eredményt maradékosan elosztjuk p -vel, és a maradékot tekintjük a „modulo p ” művelet eredményének. Ha modulo 7 számolunk, akkor 5 · 5 = 4 , mert 5 · 5 = 25 , amit 7-tel elosztva 4-et kapunk maradékul. Ezen a módon az összeadás és szorzás megszokott tulajdonságai érvényben maradnak (sőt osztani is tudunk), a Q halmazt ezen összeadás és szorzás művelettel mod p maradékosztálytestnek nevezzük. Testekről, illetve véges testekről Montágh Balázs írásában olvashatunk.

Alapvetően fontos lesz számunkra lineáris egyenletrendszerek megoldása. Erről is olvashatunk a Wettl-féle fejezetben, kongruencia-rendszerek néven, hiszen ilyenkor az egyenletek modulo p kongruenciák. Az egyenletrendszerek megoldására ugyanazokat a trükköket alkalmazhatjuk, mint amit valós együtthatók esetére megtanultunk. Például az

x 1 + 2 x 2 - x 3 = 0 2 x 1 - x 2 + x 3 = 1

megoldása történhet úgy, hogy az első egyenletből kifejezzük x 1 -et: x 1 = x 3 - 2 x 2 , majd ezt behelyettesítjük a másodikba, amiből - 5 x 2 + 3 x 3 = 1 adódik. Eddig a pillanatig mindegy volt, hogy mi a modulus, mostantól oldjuk ezt meg, mondjuk modulo 5. Eszerint a második egyenletből x 3 = ( 1 + 5 x 2 ) / 3 , azaz x 3 ? 2 ( mod 5 ) adódik. Eszerint x 3 értéke fix, x 2 tetszőleges, x 1 pedig a fenti képlettel kapható x 2 , x 3 -ból, vagyis összesen 5 megoldás van, hiszen x 2 ennyiféleképpen választható. Ugyanígy megtehettük volna, hogy a két egyenletet összeadjuk, amiből 3 x 1 + x 2 = 1 , vagyis x 2 = 1 - 3 x 1 , x 3 = x 1 + 2 x 2 = 2 - 5 x 1 a megoldás.

Igen gyakran nem magát a lineáris egyenletrendszert, hanem csak annak együtthatóit írjuk le, téglalap alakú elrendezésben, amely emlékeztet az együtthatók egyenletrendszerben elfoglalt helyére. A fenti egyenlet számtáblázata például

1 2 - 1 2 - 1 1 .

Az ilyen számtáblázatokat mátrixoknak nevezzük. A mátrixba azért nem foglaljuk bele az egyenletrendszer jobb oldalán található tagokat, mert azok szinte mindig 0-k lesznek (homogén egyenletrendszer). A k × n -es H = ( h i j ) , i = 1 , , k ; j = 1 , , n mátrixnak k sora és n oszlopa van, elemeire h i j ? Q minden i , j -re. A H mátrix i -edik sora az n hosszú ( h i 1 , h i 2 , , h i n ) ? Q n vektor, azaz n hosszú számsorozat. Hasonlóan a H mátrix j -edik oszlopa a k hosszú ( h 1 j , , h k j ) vektor. Itt „szám” jelenthet egész, racionális, valós, komplex számot vagy mod p maradékosztályt vagy egy véges test egy elemét, a lényeges csupán az, hogy „szám”-okat tudjunk összeadni és szorozni. Kiegészítő megjegyzésként néha utalunk az összefüggések mátrixműveletekkel való tömör leírására, de ez sosem lesz elengedhetetlen a megértéshez. Ezalól kivételt csupán a vektorok skaláris szorzata jelent. Az a = ( a 1 , , a n ) és b = ( b 1 , , b n ) vektorok skaláris szorzatát az analitikus geometriából n = 2 , 3 esetre megismert képlet kiterjesztésével az a b = ? i = 1 n a i b i kifejezéssel definiáljuk és a vektorok egymás mellé írásával jelöljük. Tehát két vektor skaláris szorzata nem vektor, hanem szám.