Ugrás a tartalomhoz

Lineáris algebra

Freud Róbert (2014)

ELTE Eötvös Kiadó

1. fejezet - 1. DETERMINÁNSOK

1. fejezet - 1. DETERMINÁNSOK

A determinánsfogalom kialakulása történetileg a lineáris egyenletrendszerek megoldásához kapcsolódik, de a determinánsok azóta a matematika szinte minden területén alapvető fontosságúvá váltak. Ez a bonyolultnak és mesterkéltnek látszó fogalom (amely tulajdonképpen csak egy célszerű jelölésrendszer) nagyon szerencsésnek bizonyult a legkülönbözőbb problémák kényelmes, elegáns és természetes kezeléséhez. Erre számos példát tartalmaznak majd a későbbi fejezetek is.

1.1. Permutációk inverziószáma

A permutációk inverziószámára csak a determináns definíciójához és ennek kapcsán néhány tulajdonságának a bizonyításához lesz szükségünk. Emiatt megelégszünk a permutáció legegyszerűbb, „hétköznapi” definíciójával: n különböző elemnek valamilyen sorrendje. Jól ismert, hogy adott n elem esetén n!=n·(n-1)·…·2·1 ilyen sorrend lehetséges.

A továbbiakban feltesszük, hogy a kérdéses elemek számok, és ezen belül is általában az 1,2,…,n számok permutációiról lesz szó. Megállapításaink ugyanúgy érvényben maradnak, ha az elemek között egy „természetes sorrendet” rögzítünk, és a permutációknak az „ehhez a természetes sorrendhez viszonyított eltéréseit” vizsgáljuk.

Tekintsük tehát az 1,2,…,n számoknak egy sorrendjét. Az első helyen álló számot jelöljük σ(1)-gyel, a második helyen állót σ(2)-vel stb. Ha pl. n=5, akkor a 31452 permutáció esetén σ(1)=3, σ(2)=1, σ(3)=4, σ(4)=5 és σ(5)=2. Ez tulajdonképpen azt is jelenti, hogy a permutációt felfoghatjuk mint egy függvényt: ez a σ függvény az {1,2,…,n} halmaznak önmagára történő kölcsönösen egyértelmű (bijektív) leképezése (az i-edik helyhez az ott álló σ(i) számot rendeljük).

Megjegyezzük, hogy a permutációt legtöbbször ilyen bijekcióként célszerű tekinteni. A mi szempontjainknak azonban tökéletesen megfelel, ha a permutációra, mint az 1,2,…,n számok egy sorrendjére gondolunk.

Most rátérünk az inverzió definíciójára. Az inverzió(=„fordítottság”) azt jelenti, hogy egy permutációban két elem egymáshoz képest a természetestől eltérő, „fordított módon” helyezkedik el:

1.1.1 Definíció

Az 1,2,…,n elemek egy permutációjában két elem inverzióban áll, ha közülük a nagyobbik megelőzi a kisebbiket. Egy permutáció inverziószámán az inverzióban álló elempárok számát értjük.❶

A σ permutáció inverziószámát I(σ)-val jelöljük. A fenti 31452 példában a 3 és az 1, a 3 és a 2, a 4 és a 2, valamint az 5 és a 2 állnak inverzióban, az inverziószám tehát 4.

A σ jelöléssel az inverzió úgy fogalmazható meg, hogy valamely i<j-re σ(i)>σ(j) (azaz az előrébb, az i-edik helyen álló σ(i) elem nagyobb a hátrébb, a j-edik helyen következő σ(j) elemnél).

A továbbiakban csak az játszik majd szerepet, hogy egy adott permutációban az inverziószám páros-e vagy páratlan:

1.1.2 Definíció

Egy permutáció aszerint páros, illetve páratlan, hogy az inverziószáma páros, illetve páratlan.❶

A fenti 31452 permutáció tehát páros. A legegyszerűbb páros permutáció az 12…n természetes sorrend, amely a σ(x)=x identikus függvénynek felel meg; ennek 0 az inverziószáma.

1.1.3 Tétel

I. Ha egy permutációban két szomszédos elemet felcserélünk, akkor az inverziószám 1-gyel változik (nő vagy csökken).

II. Ha egy permutációban két tetszőleges elemet felcserélünk, akkor az inverziószám páratlannal változik.❶

Bizonyítás: I. A két felcserélt elem viszonya megváltozott, azaz ha eredetileg inverzióban álltak, akkor a csere után már nem állnak inverzióban, és fordítva. Mivel szomszédosak voltak, ezért a többi elemhez képest az elhelyezkedésük nem változott, és természetesen a többi elem egymáshoz viszonyított helyzete sem módosult.

II. Ha a két elem, b és c között k darab másik áll, akkor először a hátrébb álló c-t sorra megcseréljük a mindig éppen előtte állóval, amíg közvetlenül b mögé nem kerül, ez szomszédos elemek közötti k cserét jelent. Ezután megcseréljük (a most egymás mellett levő) b-t és c-t. Végül újabb k cserével b-t rendre megcseréljük a mögötte álló elemekkel, amíg végül a b elem a c eredeti helyére nem kerül. Ez összesen 2k+1, szomszédos elemek közötti csere volt, amelyek mindegyikénél 1-gyel változott (nőtt vagy csökkent) az inverziószám. Összességében az inverziószám tehát (egy 2k+1-nél nem nagyobb) páratlan számmal változott.❷

Az előző tétel segítségével könnyen nyerhetünk információt a páros, illetve páratlan permutációk számára:

1.1.4 Tétel

Ha n>1, akkor n elemnek ugyanannyi páros és páratlan permutációja van.❶

Bizonyítás: Tekintsük az 1,2,…,n számok összes páratlan permutációját, és mindegyikben cseréljük fel az első és a második helyen álló elemet. Ekkor csupa páros permutációhoz jutunk, amelyek mind különbözők. Ebből azt kaptuk, hogy legalább annyi páros permutáció van, mint páratlan. Ha ugyanezt az eljárást a páros permutációkból kiindulva hajtjuk végre, akkor az adódik, hogy legalább annyi páratlan permutáció van, mint páros. Így a páros és páratlan permutációk száma valóban megegyezik (=n!/2).❷

Feladatok

Valamennyi feladatban az 1,2,…,n számok σ permutációiról lesz szó.

1.1.1

a) Bizonyítsuk be, hogy 0In2

b) Legyen 0kn2 tetszőleges egész. Bizonyítsuk be, hogy van olyan σ, amelyre I(σ)=k.

1.1.2 Mennyi az alábbi permutációk inverziószáma (n=101)?

a) 1,3,5,…,99,101,100,98,…,4,2;

b) 51,52,50,53,49,…,101,1;

c) 62,63,64,…,101,61,60,59,…,1;

d) 100,101,98,99,96,97,…,2,3,1.

1.1.3 Vegyünk egy tetszőleges permutációt, majd írjuk fel az elemeit pontosan fordított sorrendben, ezzel egy másik permutációt kaptunk. (Pl. a 25413-ból kiindulva a 31452 permutációt nyerjük.) Mi a szükséges és elégséges feltétele annak, hogy a két permutáció azonos paritású (azaz vagy mindkettő páros, vagy mindkettő páratlan) legyen?

1.1.4 Egy permutációban az első helyen álló elemet az utolsó, n-edik helyre visszük (a többi elem pedig egy hellyel előbbre csúszik). Mi volt az elmozgatott elem, ha az új permutációban ugyanannyi inverzió van, mint az eredetiben?

1.1.5

a) Mi a lehető legnagyobb inverziószám-változás, amelyet két elem cseréjével megvalósíthatunk? Milyen esetben lép ez fel?

M*b) P és C az alábbi játékot játsszák. P választ egy tetszőleges permutációt. Ezután C ebben a permutációban felcserél két tetszőleges elemet, majd megnézik, hogy a cserénél mennyit változott az inverziószám. P-nek az a célja, hogy a lehető legkisebb inverziószám-változás következzen be, C-nek pedig az, hogy a lehető legnagyobb. Mekkora lesz az inverziószám-változás, ha mindketten optimálisan játszanak?

1.1.6 P és C játékszenvedélyüket újabb játék(ok)ban élik ki. P választ egy tetszőleges permutációt. C feladata ezután a természetes sorrend visszaállítása bizonyos megengedett lépések egymás utáni alkalmazásával. P-nek az a célja, hogy C a természetes sorrendet a lehető legtöbb lépésben érje el, C-nek pedig az, hogy a lehető legkevesebben. Mekkora lesz a lépésszám, ha mindketten optimálisan játszanak és egy lépés

a) két szomszédos nagyságú elem cseréjét jelenti (pl. a 6-ét és a 7-ét, akárhol is állnak);

*b) két tetszőleges elem cseréjét jelenti;

*c) az 1-esnek valamelyik másik elemmel történő cseréjét jelenti?

M1.1.7 Mely n-ekre létezik az 1,2,…,n számoknak olyan permutációja, amelyben minden elem pontosan a) 1; b) 2; **c) k másik elemmel áll inverzióban?

*1.1.8 Jelöljük f(n,k)-val az 1,2,…,n elemek azon permutációinak a számát, amelyekben pontosan k inverzió van.

a) Bizonyítsuk be, hogy fn,k=i=k-n+1kfn-1,i

b) Bizonyítsuk be, hogy fn,k=fn-1,k+fn,k-1-fn-1,k-n

c) Adjuk meg egyszerűbb alakban a kfn,k összeget.

d) Adjuk meg egyszerűbb alakban a kkfn,k összeget.

e) Bizonyítsuk be, hogy n>2-re maxk fn,k2n-2

f) Mely k-ra lesz f(n,k) maximális (rögzített n mellett)?