Ugrás a tartalomhoz

Lineáris algebra

Freud Róbert (2014)

ELTE Eötvös Kiadó

9. Kombinatorikai alkalmazások

9. Kombinatorikai alkalmazások

9.1.

9.1.1 A minimális kérdésszám: a) 20; b) 2; c) 1.

9.1.2 Igazoljuk az állítást először teljes indukcióval pozitív egész súlyokra, ezután tetszőleges egészekre, majd racionálisokra. Az igazi nehézséget a valós számokra történő áttérés jelenti. Erre a megoldásoknál négy bizonyítást is közlünk, most ezekhez adunk útmutatást. — Első bizonyítás: Tekintsük a 13 valós szám által generált alteret a valós számoknak a racionálisok feletti szokásos vektorterében, és térjünk át (akármilyen bázis szerinti) koordinátákra. — Második bizonyítás: A feltételt felírhatjuk egy (0,±1 együtthatós) homogén lineáris egyenletrendszerként. Érdemes az egyik ismeretlent 0-nak rögzíteni, ekkor azt kell belátni, hogy az egyenletrendszernek csak triviális megoldása létezik. Mutassuk meg, hogy ha a racionális számok körében csak triviális megoldás létezik, akkor a valós számok körében is ugyanez a helyzet. — Harmadik bizonyítás: Az előző egyenletrendszert nézzük a modulo 2 test felett, majd innen térjünk át a valós számokra. — Negyedik bizonyítás: Lássuk be és használjuk fel, hogy a valós számok jól közelíthetők racionálisakkal: tetszőleges véges sok valós számhoz és előre megadott ε-hoz találhatók olyan azonos nevezőjű törtek, hogy mindegyik valós számnak a megfelelő törttől való eltérése legfeljebb a nevező reciprokának az ε-szorosa.

9.1.3 Nem marad igaz, ellenpélda: 12 darab 1-es és 1 darab 11-es (sok más ellenpélda is adható).

9.1.4 a) (i): log2m ahol x az x szám felső egész részét (azaz az x-nél nem kisebb egész számok minimumát) jelöli. (ii): m–1 (ha m≥2). — b) (i): logkm (ii): m-1/k-1 (ha mk). — c) Tekintsük csak az a)-beli probléma megfelelőjét (azaz amikor k=2), a b)-beli általános kérdés (azaz amikor k tetszőleges) hasonlóan tárgyalható. Az (i)-re adott válasz p<m esetén változik: ekkor log2m helyett log2p lesz a keresett minimum. A (ii)-nél is változás van, ha p nem túl nagy m-hez képest: mivel log2p unalmas vektor mindenképpen elegendő, ezért p≤2m–2 esetén m–1-nél kisebb lesz a keresett minimum. Ha viszont p elegendően nagy m-hez képest, akkor ugyanúgy m–1 a minimum, mint a valós (vagy bármilyen végtelen) test felett.

9.1.5 a) 5. b) 31.

9.2.

9.2.1 a) (21000–1)/3. b) 1+2999+1-2999/2 

9.2.2 a) 4443. b) 3. c) 3.

Útmutatás c)-hez: az

polinom (komplex) gyökei különböző 10-edik egységgyökök (éspedig éppen a primitív 10-edik egységgyökök, azaz f a 10-edik körosztási polinom), ezért a sorozat (bármilyen kezdőértékek mellett) mindenképpen periodikus 10 hosszúságú periódussal.

9.2.3 A Fibonacci-számoknál látott mindhárom bizonyítás megfelelő módosítása alkalmas az állítás igazolására, ehhez adunk némi útmutatást. — Első bizonyítás: Használjuk ki, hogy λi az f első si–1 deriváltjának is gyöke. — Második bizonyítás: A diagonális mátrix helyett a Jordan-alakot lehet felhasználni. — Harmadik bizonyítás: a parciális törtekre bontásnál a nevezőkben a megfelelő gyöktényezők magasabb hatványai is megjelennek, ezek sorbafejtése a mértani sor (első vagy magasabb) deriváltjainak segítségével történhet.

9.2.4 Használjuk fel az előző feladatot.

9.2.5 A βn sorozatot egy alkalmas konstanssal eltolva a zavart okozó 2-es tag eltűnik, és egy Fibonacci-típusú sorozatot kapunk.

Válasz: βnn+3–2 (ahol ϕn az n-edik Fibonacci-szám).

9.2.6 A ϕn képletében szereplő másik tag 0-hoz tart.

9.2.7

a) ϕn+1.

b) Nyilván csak n=2k esetén létezik ilyen kirakás, és a lehetőségek száma ekkor 3+32+3k+3-32-3k/6 — Útmutatás: Jelöljük T2k-val a 3×(2k)-as téglalapot és H2k–1-gyel azt a 3×(2k–1)-es téglalapot, amelynek hiányzik az egyik sarka. Legyen μ2k, illetve ϑ2k–1 a T2k, illetve H2k–1 alakzatok 2×1-es dominókkal való kirakásainak a száma. Ekkor μ2k=2ϑ2k–12k–2 és ϑ2k–12k–22k–3. A második összefüggés többszöri alkalmazásával ϑ2k–12k–22k–4+…+μ2+1 adódik. Ezt az elsőbe beírva, majd az így a μ2k-ra és μ2k–2-re kapott egyenlőségeket egymásból kivonva a μ2k=4μ2k–2–μ2k–4 rekurziót nyerjük.

c) A ψnn–1n–3 rekurziónak megfelelő f=x3x2–1 polinom (komplex) gyökei legyenek ρ1, ρ2, ρ3. A szokásos függvényvizsgálattal könnyen adódik, hogy f-nek egyetlen valós gyöke van és ez 1-nél nagyobb: ρ1>1. Ekkor 3=2¯ továbbá mivel a gyökök szorzata 1, ezért |ρ2|=|ρ3|<1. A ψn-re adódó n=γ11n+γ22n+γ33n képletben emiatt az utolsó két tag 0-hoz tart, ha n tart a végtelenhez. Az állítás ezután 1,46<ρ1<1,47-ből következik.

9.2.8 ϕn+2. Útmutatás: a rekurziót aszerint írjuk fel, hogy a legnagyobb elem hiányzik-e vagy szerepel-e a részhalmazban. (Vö. a 9.2.10h feladattal.)

9.2.9 Használjuk a mohó algoritmust, azaz összeadandónak minden lépésben rendre a rendelkezésre álló legnagyobb Fibonacci-számot vegyük. — A feladat állítása egyébként a Fibonacci-számok helyett bármely olyan, pozitív egészekből álló végtelen számsorozatra is igaz, amelynek az 1 eleme, és a sorozat minden eleme az előző elemnek legfeljebb a duplája.

9.2.10 a) Teljes indukció n szerint. — b) Az előző azonosságból következik alkalmas helyettesítéssel. — c) Teljes indukció vagy a ϕk+1–ϕkk–1 egyenlőségek összegzése k=1,2,…,n+1-re. — d) Teljes indukció vagy a (k–2)ϕk+1–(k–2)ϕk=(k–2)ϕk–1 egyenlőségek összegzése k=3,4,…,n+1-re és némi átrendezés. — e) Teljes indukció vagy a φk2=φkφk+1-φkφk-1 egyenlőségek összegzése k=1,2,…,n-re. — f) Az a)-ból nyerhető ϕ2n–1n–2ϕnn–1ϕn+1 egyenlőséget b)-vel összevetve átrendezés után φn2-φn-1φn+1=-φn-12-φn-2φn adódik. Ezután ugyanezt az összefüggést alkalmazzuk n helyett rendre az n–1,n–2,… számokkal. — g) Az a) azonosságot alkalmazzuk a ϕn+2n, ϕn+n és ϕ(n+1)+n számok felbontásához, így ϕ3n-et kifejezhetjük ϕn és ϕn–1 segítségével. Használjuk fel még az f)-beli azonosságot is. — h) Teljes indukció vagy használjuk fel a 9.2.8 feladatot. — i) A ϕtt–1t–2 azonosság ismételt alkalmazásával bármely k-ra a φ2n=j=0kkjφ2n-2k+j összefüggést nyerjük. Ennek k=n speciális esete a bizonyítandó állítás.

9.2.11 A másodszomszédok is relatív prímek. A harmadszomszédok közül a 3-mal osztható indexűek legnagyobb közös osztója 2, a többiek relatív prímek. (Vö. a 9.2.13 feladattal.)

9.2.12 Jelöljük ϕk-nak m-mel való osztási maradékát rk-val. Az (rk, rk+1) párok csak m2 különböző értéket vehetnek fel, ezért lesz olyan t>s, amelyre (rt, rt+1)=(rs, rs+1). Lássuk be, hogy ekkor bármely k-ra (rk, rk+1)=(rk+t–s, rk+t–s+1), azaz az rn maradékok periodikusan ismétlődnek (ts periódus szerint). Mivel r0=0, ezért bármely j-re rj(t–s)=0, azaz mj(t–s).

9.2.13 Útmutatás: Használjuk fel a 9.2.10a feladatot. A knφkφn állítást az n/k szerinti teljes indukcióval igazolhatjuk. A megfordításhoz és a legnagyobb közös osztóra vonatkozó állításhoz lássuk be, hogy ha a=bq+r, akkor (ϕa, ϕb)=(ϕb, ϕr). — Egy másik lehetőség: Mutassuk meg, hogy bármely m-re az m-mel osztható Fibonacci-számok indexei éppen a legkisebb ilyen tulajdonságú nemnulla Fibonacci-szám indexének a többszörösei.

9.2.14 a) ϕn+1. — b) 1+2n-1-2n/22 ami az αi+1=2αii–1, α0=0, α1=1 rekurzió megoldása (ezeket a számokat szokás Lucas-sorozatnak nevezni).

9.2.15 Legyen =1+5/2  ekkor φn=n--1/n/5  A szóban forgó sor első m tagjának az összegét „teleszkopikus” összeggé alakíthatjuk át:

Mivel a második tag 0-hoz tart, így a keresett sorösszeg 5/2-1=5-5/2

9.2.16 Eredmény: 2n-2n-1/n  A megoldásoknál ezt három különböző módon vezetjük le, most ezekhez adunk útmutatást. — Első megoldás: n–1 darab (kéttényezős) szorzást kell végrehajtani. Minden egyes szorzásnál jelöljük meg a nyitó zárójelet +1-gyel és a szorzat első tényezőjét –1-gyel; ha ez az első tényező maga is egy többtényezős szorzat, akkor annak utolsó tényezőjét jelöljük meg a –1-gyel. Könnyen láthatóan ekkor az a1, a2,…, an–1 tényezők mindegyike pontosan egyszer van –1-gyel megjelölve, továbbá bármely kn–1-re ak előtt legalább k nyitó zárójelnek (azaz +1-nek) kell szerepelnie. Ennek a megfordítása is igaz, minden ilyen ±1-ekből álló sorozat egy szorzási útnak felel meg. Így n–1 darab +1-ből és n–1 darab –1-ből álló sorozatokat képezünk, amelyekben az elejétől számítva akárhány tag összege nemnegatív. Minden sorozat elejére még egy +1-et odaírva, olyan, most már n darab +1-ből és n–1 darab –1-ből álló sorozatokra fogalmaztuk át a problémát, amelyekben az elejétől számítva akárhány tag összege pozitív. Lássuk be, hogy a „rossz” sorozatok száma a –1-gyel kezdődő sorozatok számának a duplája. — Második megoldás: Az utoljára elvégzett szorzás az első k és a maradék nk tényezőből (valahogyan) elkészített szorzatokat szorozza össze, k=1,2,…,n–1, így a feladatnak az αn=k=1n-1αkαn-k , α1=1  rekurzió felel meg. Ebből az Az=n=1αnzn  hatványsorra az A2(z)=A(z)–z egyenletet kapjuk. – Harmadik megoldás: Egyszerűbb rekurziót kapunk, ha az elemek egymás közötti cseréjét is figyelembe vesszük. A rekurziót megoldva, az így meghatározott βn értékből nyilván αnn/n!.

9.2.17 Az egyik oldalt rögzítsük, és aszerint csoportosítsuk az eseteket, hogy az ezen oldalt tartalmazó háromszög harmadik csúcsa hová esik. Az így kapott rekurzió lényegében azonos az előző feladat második megoldásában tárgyalt rekurzióval. – Eredmény: 2n-4n-2/n-1 

9.3.

9.3.1 a) Pl. megfelelnek a pi-k első és negyedik hatványai. — b) A skatulyaelv szerint biztosan lesz három olyan cj, amelyekben mindegyik pi kitevőjének modulo 3 vett maradéka ugyanannyi. Ennek a három cj-nek a szorzata köbszám. — c) Az állítás a 9.3.1 Tételre adott bármelyik bizonyítás értelemszerű módosításával igazolható.

9.3.2 Okoskodjunk indirekt, ekkor a kis-Fermat-tétel felhasználásával kapjuk, hogy a

kongruencia azonosság (azaz minden x1,…,xt esetén teljesül). Mutassuk meg, hogy a fokszámok összegére tett feltétel miatt ez nem lehetséges. — Ha speciálisan mindegyik polinom elsőfokú, akkor (az Fp test felett) egy homogén lineáris egyenletrendszert kapunk, amelyben az ismeretlenek száma nagyobb az egyenletek számánál, tehát van nemtriviális megoldás. A Chevalley-tétel tehát ennek a jól ismert eredménynek az általánosításaként is tekinthető.

9.3.3 A cj számban a pi prím kitevője legyen γij(1≤ik,1≤jt). Az fix1 , . . . ,xt=j=1tγijxj2 polinomokra és p=3-ra alkalmazzuk a Chevalley-tételt.

9.3.4 Itt t≥(q–1)k+1 a megfelelő feltétel.

9.3.5

a) Tekintsük a c1, c1+c2,…, c1+c2+…+cn számok n-nel való osztási maradékait.

b) Először azt igazoljuk, hogy ha az állítás igaz n=r-re és n=s-re, akkor teljesül n=rs-re is. A 2rs–1 számból vegyünk tetszőleges 2r–1-et, ekkor az r-re vonatkozó állítás szerint kiválaszthatunk r olyat, amelyek összege osztható r-rel. A maradék 2rs–1–r számból ismét vegyünk tetszőleges 2r–1-et, ezek között is van r darab olyan, amelyek összege osztható r-rel. Lássuk be, hogy ily módon 2s–1 darab olyan r-es csoport keletkezik, ahol minden csoport elemeinek az összege osztható r-rel. Alkalmazzuk ezután az s-re vonatkozó állítást ezen összegek r-edrészére.

Ennek alapján elég az n=p=prím esettel foglalkozni. Legyen f1=j=12p-1cjxjp-1 ,  f2=j=12p-1xjp-1  és alkalmazzuk a Chevalley-tételt.

9.3.6

a) A kínai maradéktétel szerint elegendő a problémát egy pm prímhatvány modulusra megoldani. Ha m>1, akkor az x1=x2=x3=pm/2 választás megfelelő. Ha m=1, akkor (pl. a Chevalley-tétel alapján) az x12+x22+x320 mod p kongruenciának van nemtriviális megoldása. Itt feltehető |xi|≤p/2, ezért 0<x12+x22+x32<p2  tehát az x12+x22+x32 összeg (amely a feltétel szerint p-vel osztható) p2-tel már nem lehet osztható.

b) Az a)-beli eljárást kell egyetlen esetben finomítani: ha m>1 és páratlan, akkor legyen xi=p(m–1)/2yi, és az yi-kre alkalmazzuk az előbb m=1-re látott gondolatmenetet.

9.3.7 Képezzük a kérdéses N számnak minden lehetséges k-ra a (közelítő, valós) k-adik gyökét, és az ehhez legközelebbi nk egész számra ellenőrizzük le, nem teljesül-e nkk=N  Mivel a szóba jöhető legkisebb hatványalap a 2, ezért k≤log2N, tehát ez valóban gyors algoritmus.

9.3.8

a) Az egyes prímek egymástól függetlenül durván a számok felét selejtezik ki, tehát a garantáltan rossz számok aránya s darab prím esetén körülbelül (2s–1)/2s (azaz nagyjából minden 2s-edik számot kell csak x-ként kipróbálni).

b) Az a jó, ha d és e közel egyforma.

c) 86519=241·359, 584189=613·953. Az N=86519=x2y2 keresésénél x86519 azaz x legkisebb szóba jöhető értéke 295. Az y2=x2N egyenlőséget modulo 8 vizsgálva a bal oldal lehetséges értéke 0,1 vagy 4, a jobb oldalé 0–7,1–7 vagy 4–7, ezek egyetlen közös értéke 1=0–7, azaz 8|x2. Innen kapjuk, hogy az x szükségképpen osztható 4-gyel. Modulo 3 vizsgálva hasonlóan adódik, hogy 3|x. Így a legkisebb kipróbálandó érték az x=300, ami rögtön meg is felel, hiszen 3002-86519=59 egész szám. Az N=584189 esetében azt kapjuk, hogy x páratlan és 3-mal osztható, így a kipróbálandó számok az x=765,771,…, itt x=783-ra járunk szerencsével.

Megjegyzés: Mielőtt egy nagy szám felbontását megkíséreljük, mindenképpen célszerű egy gyors prímteszttel meggyőződni arról, hogy a szám valóban összetett. Azt se felejtsük el, hogy igazán gyors faktorizációs algoritmus nem ismeretes, nagy (pl. háromszázjegyű) számokra a feladatban jelzett faktorizációs módszer is reménytelenül lassú.

9.4.

9.4.1

a) 2k–1. — Útmutatás: az első k–1 elem mindegyikénél szabadon dönthetünk, hogy bevesszük-e az adott elemet a részhalmazba vagy sem, és ekkor az utolsó elemnél egyértelműen adódik, hogy be kell-e vennünk vagy sem. Egy másik lehetőség: a keresett szám ik/2k2i=1+1k+1-1k/2 

b) (2k+2cos(kπ/3))/3. Ezt átírhatjuk más alakba is aszerint, hogy k milyen maradékot ad 6-tal osztva: (2k+2)/3, ha k≡0(mod 6); (2k+1)/3, ha k≡±1(mod 6); (2k–2)/3, ha k≡3(mod 6); és végül (2k–1)/3, ha k≡±2(mod 6). — Útmutatás: Jelölje αk, βk, illetve γk egy k elemű halmaz azon részhalmazainak a számát, amelyek elemszáma 0, 1, illetve 2 maradékot ad 3-mal osztva. Célunk az αk meghatározása. Nyilván αiii=2i. Ennek felhasználásával αk=2k–1–βk–1, βk–1=2k–2–γk–2, valamint γk–2=2k–3–αk–3, ahonnan az αkk–3=3·2k–3, majd az αkk–6+21·2k–6 rekurzió adódik. Ezt tovább bontva az αk=21·2k–6+21·2k–12+… képletet nyerjük, amely az utolsó tagjától eltekintve egy 26 hányadosú mértani sor összege. — Másik lehetőségként az

összefüggéssel dolgozhatunk, ahol ω egy harmadik primitív komplex egységgyök.

9.4.2 a) H és H’ egymás komplementerei.

b) H és H’ szimmetrikus differenciáját kell képezni.

9.4.3 Indirekt okoskodva tegyük fel, hogy létezik egy δ1h_1+. . .+δnh_n=0_ racionális együtthatós nemtriviális lineáris kombináció. Az együtthatók nevezőinek legkisebb közös többszörösével beszorozva, majd a kapott egész együtthatók legnagyobb közös osztójával végigosztva elérhetjük, hogy a δj-k relatív prím egész számok legyenek. Mindkét oldalt skalárisan megszorozva h_j-vel, most is δ1h_1h_j+. . .+δjh_jh_j+. . .+δnh_nh_j=0  adódik. Mivel |Hj| páratlan, de minden tj-re |HtHj| páros, ezért itt minden h_th_j skalárszorzat páros, kivéve h_jh_j-t, ami páratlan. Innen azonnal kapjuk, hogy δj szükségképpen páros. Mivel ez tetszőleges j-re teljesül, ezért valamennyi δj páros, ami ellentmond annak, hogy a δj számok relatív prímek voltak.

9.4.4 a) βij=|HiHj| modulo 2 maradéka. — b) Ekkor a B=ATA szorzat az n×n-es egységmátrix, tehát n=r(B)≤r(A)≤k.

9.4.5 a) Az egyelemű részhalmazok mindig jók. Emellett k=4-re (vagy bármely páros k-ra) megfelelnek az egyelemű részhalmazok komplementerei is. A többi k-ra a kétféle eljárás kombinációjával kapjuk a kívánt eredményt. — b) Az a) részben jelzett kombináció ezt is biztosítja. — c) A felső becslés nagyjából k tetszőleges részhalmaz összes lehetséges kiválasztásának a száma. Az alsó becsléshez a legkönnyebben úgy jutunk el, ha a 9.4.4 feladatban látott módszert alkalmazzuk. Az egyszerűség kedvéért legyen k páros, k=2t. Ha C egy tetszőleges t×t-es szimmetrikus 0-1 mátrix, Et pedig a t×t-es egységmátrix, akkor a k×k-as A=C+EtCCC+Et mátrixra B=ATA a k×k-as egységmátrix, tehát A egy alkalmas Hj halmazrendszer illeszkedési mátrixa. Az ilyen A-k (azaz C-k) száma 2k(k+2)/8. A k!-sal az oszlopcserékkel egymásbavihető halmazrendszerek azonossága miatt kell leosztani. (Ha az izomorf halmazrendszerektől is el akarunk tekinteni, tehát azoktól, amelyek egymásból a városlakók valamilyen permutációjával nyerhetők, akkor ez a sorcseréknek felel meg, és ekkor még egyszer le kell osztani k!-sal. Azonban még így is igen nagy számot kapunk, pl. elég nagy k-ra alulról becsülhetjük 2k2/9-cel.) Mindez azt mutatja, hogy Páratlanvárosban nagyon sok különböző módon alapíthatunk k megfelelő egyesületet.

9.4.6 Eredmény: k, ha k páratlan és k–1, ha k páros. — Útmutatás: páratlan k-ra a k–1 elemű részhalmazok, páros k-ra pedig például az x1-et tartalmazó kételemű részhalmazok megfelelnek. Annak igazolására, hogy ennél több részhalmaz már nem létezik, a Páratlanváros-tétel eredeti vagy a 9.4.4 feladatban jelzett bizonyítása adaptálható. Páros k esetén azt lehet kihasználni, hogy az illeszkedési mátrix (F2 feletti) rangja legfeljebb k–1, hiszen a sorok összege 0.

9.4.7 a) A Páratlanváros-tétel bármelyik bizonyítása átvihető (értelemszerűen az F2 test helyett F3-mal kell dolgozni). Válasz: k. — b) A válasz most is k, azonban csak a 9.4.3 feladatban ajánlott bizonyítás működik. — c) Mivel |HtHj| osztható 6-tal, ezért |HtHj| osztható 2-vel és 3-mal is, ugyanakkor |Hj| nem osztható 6-tal, tehát |Hj| a 2 és a 3 közül legalább az egyikkel nem osztható. Így 2k+1 darab Hatfalus egyesület között vagy lenne k+1 darab Páratlanvárosos, vagy pedig lenne k+1 darab Hármashatáros, és mindkettő lehetetlen.

Megjegyzés: Általánosan a következő problémáról van szó. Legyen s rögzített pozitív egész. Maximálisan hány olyan Hj részhalmaza lehet egy k elemű X halmaznak, amelyekre s Hj  de tj esetén s||HtHj|?

Mindig meg lehet adni k ilyen részhalmazt; az egyeleműeket. A Páratlanváros-tételben láttuk, hogy s=2 esetén ez a maximum. Ugyanígy elintézhető minden olyan eset, amikor s prímszám. Az állítás akkor is igaz marad, ha s egy prímszám hatványa (a bizonyítást ekkor a 9.4.3 feladat ajánlása szerint lehet elvégezni). A többi s-re a probléma megoldatlan; csak annyi adódik, hogy a maximum legfeljebb ω(sk, ahol ω(s) az s különböző prímosztóinak a száma. Ezt a felső becslést eddig csak igen minimális mértékben sikerült javítani, pl. s=6-ra n≤2k helyett csak a hajszálnyival jobb n≤2k–2log2k az ismert legjobb eredmény. Ugyanakkor egyetlen s-re sem találtak k-nál több megfelelő részhalmazt.

9.4.8 a) k. b) k–1.

9.4.9 Válasz: k. — A Páratlanváros-tétel eredeti bizonyítását kövessük. A Kj halmazoknak megfelelő k_j vektorok függetlenségét úgy láthatjuk be, ha a δ1k_1+. . .+δnk_n=0_ lineáris kombináció mindkét oldalát skalárisan megszorozzuk rendre a Pt halmazoknak megfelelő p_1 , . . . ,p_n vektorokkal.

9.4.10 Válasz: k. — Útmutatás a felső becsléshez: lássuk be, hogy a megfelelő vektorok a valós test felett lineárisan függetlenek.

9.4.11 Válasz: 1 (és ennek minden városlakó tagja). — Az előző feladatnál használt lineáris algebrai gondolatmenethez hasonlóan okoskodhatunk.

9.4.12 i=0mki 

9.4.13 b) Válasz: p2, azaz az altér maximálisan 2-dimenziós lehet.

Először példát mutatunk ilyen altérre. Legyen 0<r<p egy kvadratikus nemmaradék modulo p, ekkor megfelel Tp–r+1-ben az U=100 , 011  altér. (Megjegyezzük, hogy már T3-ban is mindig található a kívánt tulajdonságú altér, sőt ha p≡3(mod 4), akkor maga a T2 vektortér is megfelel.)

Most megmutatjuk, hogy egy (legalább) háromdimenziós altérben mindig található önmagára merőleges nemnulla vektor. Az ortogonalizációs eljárással előállíthatunk b_1,b_2,b_3 páronként merőleges vektorokat, legyen b_ib_i=βi ,   i=1, 2, 3  Egy v_=i=13γib_i vektor akkor és csak akkor merőleges önmagára, ha

teljesül. A γi-ket ismeretleneknek tekintve ennek az egyenletnek pl. a Chevalley-tétel (9.3.2 feladat) szerint van nemtriviális megoldása.

9.4.14 a) Ha p≡3 (mod 4), akkor k≥3 esetén, egyébként k≥2-re. Ugyanis a z12+z220 mod p (mod p) kongruenciának pontosan p3 mod p (mod 4) mellett van nemtriviális megoldása, a z12+z22+z320 mod p (mod p) kongruencia pedig már minden p-re nemtriviálisan megoldható. — b) Ha csak a nullvektor merőleges önmagára, azaz ha k=1 és p tetszőleges vagy k=2 és p≡3 (mod 4), akkor ez triviálisan altér (dimenziója 0). Ettől eltekintve csak p=2-re kapunk alteret, de k tetszőleges lehet. Ennek a dimenziója k–1. (Azokból a vektorokból áll, amelyeknek páros sok koordinátája 1-es.)

9.4.15 a) Pl. legyen p=k=2 és U=11  — b) Egy x_V vektor pontosan akkor merőleges U-ra, ha U egy bázisának minden elemére merőleges. Ez a feltétel egy dimU egyenletből álló, dimV ismeretlenes homogén lineáris egyenletrendszert jelent, amelynek a rangja dimU (ugyanis a sorok, amelyek az U báziselemeiből származnak, lineárisan függetlenek). A megoldásoknál így a szabad paraméterek száma dim U=dimV-dimU — c) A b) részből és a 4.6.6 feladatból következik.

9.4.16 Létezik: a), c), e). — Útmutatás: A dim U+dim U=dim V összefüggés alapján k szükségképpen páros. Használjuk fel a 9.4.14a feladatot is.

9.4.17 a) Nem igaz, vegyünk pl. egy nagy páratlan elemszámú részhalmazt és a tőle diszjunkt egyelemű részhalmazokat. — b) Igaz. A Párosváros-tétel bizonyítását követve tekintsük a Hj halmazoknak megfelelő h_j vektorok által generált U alteret. Ha ennek az U-nak nem minden eleme szerepel a h_j-k között, akkor egy ilyen hiányzó vektorral bővíthetjük a rendszert. Ha U minden eleme szerepel, de az elemszám nem maximális, akkor dim U<dim V/2 és így dim UdimU+2 Egészítsük ki U bázisát  U bázisává a w_1 ,w_2 ,   .  .  .  vektorokkal. Ekkor w_1 ,w_2 és w_1+w_2 mindegyike merőleges U-ra és közülük legalább az egyik önmagára is merőleges, és ekkor ezzel a vektorral bővíthetjük a rendszert.

9.4.18 Útmutatás: Válasszuk külön a páros és páratlan tagszámú egyesületeket, és mutassuk meg, hogy a nekik megfelelő vektorok által generált alterek diszjunktak. Ha ezek dimenziója s, illetve t, akkor 2s+tk, és így nt+2k-t/2 

9.4.19 Válasz: 8. — Útmutatás: Lássuk be először, hogy 6 elemű halmaz esetén 4 a maximum. Rátérve a 9 elemű halmaz esetére, igazoljuk, hogy ha a Hi részhalmazok megfelelnek, akkor a komplementereik is a kívánt tulajdonságúak. Ennek alapján feltehető, hogy |H1|=3. Ekkor valamennyi Hi-re HiH1= vagy HiH1  A Hi-knek a H1-be eső része tehát kétféle lehet, a H1-en kívül eső részekre pedig a 6 elemű halmaznál látottak szerint négy lehetőség adódik.

9.5.

9.5.1 b) A 3 egyszeres, az 1 ötszörös és a –2 négyszeres sajátérték. Ezt a legegyszerűbben a 9.5.1 Tétel bizonyításából olvashatjuk le a d=3 speciális esetben.

9.5.2 Az állítás a szomszédsági mátrix és a sajátvektor definíciójából következik.

9.5.3 A sajátértékeket a szomszédsági mátrix karakterisztikus polinomjának a gyökeiként kaphatjuk meg, azonban gyakran kevesebb számolással is célhoz érhetünk, ha az előző feladatra támaszkodunk. — Eredmények: a) Az n–1 egyszeres, a–1 pedig n–1-szeres sajátérték. b) Az 1 és a–1 mindketten k-szoros sajátértékek. c) A k és a –k egyszeres, a 0 pedig n–2-szeres sajátérték. d) A n-1 és a -n-1 egyszeres, a 0 pedig n–2-szeres sajátérték. e) A sajátértékek 2cos(2jπ/n), 0≤jn–1.

9.5.4 Legyen G, illetve G¯ szomszédsági mátrixa A, illetve A’. Ekkor a csupa 1 komponensű j_ vektor a regularitás miatt mind G-nek, mind pedig G¯-nek sajátvektora, a megfelelő sajátérték d, illetve n–1–d. Legyen j_ , v_2 ,. . . ,v_n az A-nak egy ortonormált sajátbázisa (az Rn euklideszi térben), a megfelelő sajátértékek legyenek d, λ2,…, λn. Mivel a J-nek a j_-től független sajátvektorai éppen j_ nemnulla elemei, és ezekhez a 0 sajátérték tartozik, ezért a v_i-k a J-nek is sajátvektorai 0 sajátértékkel. Ekkor az A’=JEA összefüggés alapján a v_i-k az A’-nek is sajátvektorai, a megfelelő sajátértékek pedig –1–λi. Az A’ sajátértékei tehát n–1–d, –1–λ2,…, –1–λn.

9.5.5 Mutassuk meg, hogy mindkét feltétel ekvivalens azzal, hogy A minden sajátvektora J-nek is sajátvektora.

9.5.6 A Petersen-gráf illeszkedési mátrixa 10×15-ös, ez 6 darab 5×5-ös Cij blokkból áll (i=1,2, j=1,2,3), ahol C12=C21=0, C13=C23=E,

C 11 = 1 1 0 0 0 0 1 1 0 0 0 0 1 1 0 0 0 0 1 1 1 0 0 0 1 és C22=1010001010001011001001001 

A továbbiakban a 9.5.3 feladat számozását használjuk.

a) Egy n×n(n–1)/2-es mátrix, amelynek oszlopaiban minden lehetséges módon előfordul két darab 1-es.

b) Két k×k-as egységmátrix egymás alatt.

c) Egy 2k×k2-es mátrix, amelynek oszlopaiban minden lehetséges módon előfordul két darab 1-es úgy, hogy az egyik a felső k sorból, a másik pedig az alsó k sorból van.

d) Egy (n–1)×(n–1)-es egységmátrix fölött egy csupa 1 sor.

e) Egy n×n-es mátrix, ahol a főátlóban, közvetlenül a főátló alatt és a jobb felső sarokban áll 1-es, máshol pedig 0.

9.5.7 M=CTC olyan m×m-es mátrix, ahol a főátló minden eleme 2 és ij-re μij aszerint 1, illetve 0, hogy az i-edik és j-edik élnek van-e közös csúcsa vagy sem. — N=CCT olyan n×n-es mátrix, ahol a főátlóban νii az i-edik csúcs foka és ij-re νij aszerint 1, illetve 0, hogy az i-edik és j-edik csúcs össze van-e kötve éllel vagy sem.

9.5.8 Diszjunkt háromszögek egyesítése.

9.5.9 A szokásos jelölésekkel az Aj_ vektor i-edik koordinátája éppen di, az i-edik csúcs foka. Legyen b_1 ,. . . ,b_n ortonormált sajátbázis, λ1,…, λn a megfelelő sajátértékek és j_=i=1nib_i  Ekkor

azaz valóban δ≤Λ. A Λ≤Δ egyenlőtlenség bizonyításához legyen v_ a  -hoz tartozó olyan sajátvektor, amelynek a(z egyik) legnagyobb koordinátája 1, legyen ez pl. az első koordináta. Az x_z_ jelentse azt, hogy minden koordinátára xizi. Ekkor v_=Av_ Aj_j_  és az első koordináták összehasonlításával kapjuk, hogy Λ≤Δ.

9.5.10 Először igazoljuk az alábbi segédállításokat. Legyenek A és A’ nemnegatív elemű szimmetrikus mátrixok, a maximális sajátértékek Λ, illetve Λ’. (i) Ha egy nemnulla x_ vektor koordinátái nemnegatívak (azaz x_0_) és Ax_Tx_  akkor Λ≥τ. (ii) Ha az A és A’ minden elemére αij≥αij’, akkor Λ≥Λ’. Ezután a feladat állítását bizonyítsuk a csúcsok száma szerinti teljes indukcióval; a gráfból hagyjuk el a legkisebb fokszámú csúcsot a hozzá tartozó élekkel és használjuk fel (ii)-t. — Megjegyzés: belátható, hogy a legnagyobb sajátértékhez mindig tartozik nemnegatív sajátvektor, sőt ez bármely nemnegatív elemű (nem feltétlenül szimmetrikus) mátrixra is igaz (Frobenius-Perron-tétel).

9.6.

9.6.1 A mohó algoritmussal mindig a legelső olyan elemet választjuk, amelyik nem rontja el a Sidon-tulajdonságot. Tegyük fel, hogy a1<a2<…<as<n már megvan. Egy d elem akkor rossz, ha valamilyen i,j,ks-re d+ai=aj+ak, azaz d=aj+akai. Ezzel legfeljebb s3 (sőt tulajdonképpen kevesebb mint s3/2) elemet zártunk ki, azaz s<n1/3 esetén még találunk n-nél kisebb további jó elemet.

9.6.2 A Sidon-tulajdonság igazolásához tegyük fel, hogy ai+aj=ak+al, azaz

Itt a második tag osztható 2p-vel, de abszolút értéke 2p-nél kisebb, tehát csak 0 lehet. Emiatt az első tag is 0. Vagyis ik=lj és i2k2l2j2 (mod p). Innen egyszerű számolással adódik, hogy vagy i=k és j=l vagy pedig i=l és j=k.

9.6.3 A p2 elemű testtel és a benne levő p elemű résztesttel hasonlóan (csak egyszerűbben) kell okoskodni, mint a 9.6.2 Tétel bizonyításában tettük.

9.6.4 Vegyünk egy g primitív gyököt modulo p, és legyen ai az xi (mod p–1), xgi (mod p) szimultán kongruenciarendszer megoldása modulo p(p–1), i=1,2,…,p–1.

9.6.5 A 9.6.1 Tétel szerint vegyünk 1 és n1 között egy kb. n1 elemszámú S1 Sidon-sorozatot. Legyen n2 sokkal nagyobb n1-nél. Az [n1, n1+n2] intervallumban ne vegyünk elemeket, viszont n1+n2 és n1+2n2 között helyezzünk el egy kb. n2 elemszámú Sidon-halmazt, és abból hagyjuk el azokat az elempárokat, amelyeknek a különbsége <n1, a maradékot jelölje S2. (Megfelelne céljainknak az is, ha minden elempárból csak az egyik elemet hagynánk el.) A Sidon-tulajdonság miatt az elhagyott elemek száma <2n1. Így n1+2n2-ig összesen körülbelül

n 2 + n 1 - 2 n 1 n 2 elemünk van. Lássuk be, hogy S1S2 Sidon-tulajdonságú. Ezután válasszunk egy, az n1+2n2-nél jóval nagyobb n3-at, n1+2n2+n3 és n1+2n2+2n3 között helyezzünk el egy kb. n3 elemszámú Sidon-halmazt, abból töröljük azokat az elemeket, amelyeknek a különbsége <n1+2n2 stb. Az eljárást folytatva a feladat feltételeit teljesítő végtelen Sidon-sorozatot kapunk.

9.6.6 a) Általánosítsuk a 9.6.3 feladat módszerét a ph elemű testre.

b) Az elemekből képezhető h-tagú összegek egyrészt mind különbözők, másrészt valamennyien 1 és nh közé esnek.

9.6.7 a) A kettőhatványok ilyenek. — b) Vizsgáljuk meg, hány összeg keletkezik és ezek milyen határok közé esnek. — c) A keletkező összegeket egy (klasszikus) valószínűségi változónak tekintve alkalmazzuk a Csebisev-egyenlőtlenséget.

9.6.8 Legyen C az 1 és n2/3 közötti egész számok halmaza, továbbá D a C-nek az n-ig terjedő prímszámokkal való egyesítése. Először lássuk be, hogy n-ig minden szám felírható n=cd alakban, ahol cC , dD (a felírás általában nem egyértelmű). Ezután az ai számoknak rögzítsük egy ilyen ai=cidi alakú előállítását, majd készítsünk el egy |C|+|D|≤π(n)+2n2/3 csúcsú páros gráfot, amelynél a csúcsok egyik csoportja a C halmaz, a másik pedig a D, és az ai számnak a ci és di csúcsot összekötő él felel meg. Ha az élek száma legalább annyi, mint a csúcsok száma, akkor a gráfban van kör. A párosság miatt ennek a körnek páros sok éle van, és a konstrukció alapján a minden második élnek megfelelő ai-k szorzata megegyezik a kör többi élének megfelelő aj-k szorzatával (hiszen mindkét szorzat a kör összes csúcsaiban szereplő számok szorzata).

9.6.9 Írjuk fel a számokat d alapú számrendszerben, ahol d értékét később alkalmasan megválasztjuk. Tekintsük most azokat a számokat n-ig, amelyek felírásában minden számjegy <d/2 és a számjegyek négyzetösszege egy adott q érték. Mutassuk meg, hogy egy ilyen számhalmazban nem fordul elő háromtagú számtani sorozat, továbbá q és d alkalmas megválasztásával elérhető, hogy a halmaz elemszáma a feladat állításának megfelelően nagy legyen.

9.6.10 Első megoldás: A „rossz” színezések számát ügyesen felülről becsülve mutassuk meg, hogy ez kisebb, mint az összes színezések száma. — Második megoldás: Tekintsük a p prímmel a 2p elemű T véges testet, legyen Δ a multiplikatív csoport generátoreleme és W egy p–1-dimenziós altér T-ben (mint F2 feletti vektortérben). A színezés: k akkor piros, ha k W Az 1,2,…,p(2p–1) számokat ily módon kiszínezve nem fordul elő p+1-tagú egyszínű számtani sorozat. — Harmadik megoldás: Legyenek pirosak azok a számok, amelyek a 7 és a 17 közül pontosan az egyikkel oszthatók. — Negyedik megoldás: Legyenek pirosak azok a számok, amelyek a 2, a 3, az 5 és a 7 közül páratlan sokkal oszthatók. — Ötödik megoldás: Nevezzünk A-nak, illetve B-nek egy olyan, 17 egymás után következő számból álló blokkot, amelynek az első 16 eleme piros, az utolsó eleme pedig kék, illetve fordítva, és tekintsük az alábbi színezést: 15 darab A után vegyünk 15 darab B-t és ezt ismételjük (összesen 16-szor lehet).

9.7.

9.7.1 Az alábbi lépésekben igazolhatjuk a tételt:

(i) Két egyenlő alapú és magasságú paralelogramma egymásba darabolható. Legyen a közös alap AB, a vele párhuzamos oldalegyenesen a csúcsok legyenek CD, illetve C’D’. Ha pl. D a D’C’ szakaszon van, akkor az ABCD paralelogrammából vágjuk le a BCC’ háromszöget, és ezt a vele egybevágó ADD’ háromszög helyére illesztve megkapjuk az ABC’D’ paralelogrammát. Ha a CD és C’D’ szakaszoknak nincs közös pontja, akkor mindkét paralelogrammát vágjuk szét az alapjukkal párhuzamosan olyan „alacsonyabb” paralelogrammákra, amelyekre már alkalmazhatjuk az előző gondolatmenetet.

(ii) Egy téglalap átdarabolható olyan téglalappá, amelynek egyik oldala adott. A téglalapot szükség esetén vékonyabb csíkokra vágva és a csíkokat a rövidebb élek mentén összeragasztva olyan ABCD téglalapot kapunk, amelynek (mondjuk) a BC oldala kisebb, az AB oldala pedig nagyobb az adott x szakasznál. A B középpontú x sugarú kör messe a CD oldalt a C’ pontban, és legyen D’ a B pont tükörképe az AC’ szakasz felezőpontjára, ezzel egy ABC’D’ paralelogrammát kapunk. A C’ és B pontok merőleges vetülete a D’A egyenesen legyen X, illetve Y, így egy BC’XY téglalaphoz jutunk, amelynek BC’ oldala éppen az előírt x hosszúságú. Ekkor az ABCD téglalap és a BC’XY téglalap is azonos alapú és magasságú, mint az ABC’D’ paralelogramma, ezért az (i) rész alapján a két téglalap — az ABC’D’ paralelogramma „közvetítésével” — egymásba darabolható.

(iii) Végül egy tetszőleges sokszöget háromszögekre bonthatunk, mindegyik háromszöget téglalappá alakíthatjuk, a kapott téglalapokból pl. egységnyi alapú téglalapokat gyárthatunk, és ezeket egymás mellé téve egyetlen, egységnyi alapú téglalappá daraboltuk át a sokszöget. Ezt két azonos területű sokszögre elvégezve két egybevágó téglalaphoz jutunk, tehát a két sokszög egymásba is átdarabolható.

9.7.2 a) Valamely δ pontosan akkor lesz a π-nek racionális számszorosa, ha van olyan n pozitív egész, amelyre nδ a 2π-nek egész számú többszöröse, azaz cos(nδ)=1. A

összefüggés alapján igazoljuk teljes indukcióval, hogy cos(nα) egy 3n nevezőjű (tovább már nem egyszerűsíthető) tört, és így nem lehet az értéke 1. — b) Az előzőkhöz hasonlóan igazoljuk teljes indukcióval, hogy 2cos(nγ) a 2cosγ-nak egy egész együtthatós, normált polinomja. Így ha cos(nγ)=1, akkor 2cosγ gyöke egy egész együtthatós, normált polinomnak. Egy ilyen polinom racionális gyökei csak egészek lehetnek, tehát 2cosγ egész szám. Ezt a |cosγ|≤1 feltétellel összevetve kapjuk az állítást.

9.7.3 a) Nyilván c=f(1). Az állítást lássuk be először a pozitív egészekre, majd a pozitív racionálisokra, a 0-ra és végül a negatív racionálisokra. — b) Mutassuk meg, hogy f ekkor mindenütt folytonos, majd támaszkodjunk az a)-beli eredményre. — c) Ekkor a 0 körül is van olyan intervallum, amelyben f korlátos, és innen az is következik, hogy f a 0-ban folytonos. — d) Ha a valós számokat mint a racionális test feletti V vektorteret tekintjük, akkor a feltétel azt jelenti, hogy f lineáris transzformáció V-n. A bázis fogalmának (és létezésének) végtelen dimenziós térre történő kiterjesztésével (Hamel-bázis) a lineáris transzformációk továbbra is a báziselemek képeivel jellemezhetők, azaz egy Hamel-bázison f-et tetszőlegesen előírhatjuk, ez mindig egyértelműen meghatároz egy minden valós számon értelmezett megfelelő f függvényt. (Ezeket az f-eket természetesen „nem látjuk”.)

9.7.4 a) Átdarabolhatók, ennek igazolása a Bolyai–Gerwien-tétel bizonyításának a mintájára (szinte arra támaszkodva) végezhető el (9.7.1 feladat). — b) Nem darabolhatók egymásba: az ABCC’ tetraéder átdarabolható egy hasábba és így egy vele azonos térfogatú kockába is, az ABCB’ tetraéder viszont nem. Ez utóbbi egyik lapszöge π/2, a másikat ϑ-val jelölve cosϑ=1/3  Mutassuk meg, hogy ϑ/π irracionális, és ezután kövessük a 9.7.1 Tétel bizonyításának a gondolatmenetét.

9.7.5 A megfelelő invariáns legyen a sokszögnek egy adott irányba eső élhosszainak (valamely körüljárás szerinti) előjeles összege.

9.7.6

a) Ha n=2k>2, akkor egy k oldalhosszúságú négyzetben vegyünk egy k–1 oldalú négyzetet és a megmaradt sávokban a 2k–1 darab egységnégyzetet. Ha n=2k+3>5, akkor vegyük az előző konstrukciót, majd valamelyik négyzetet vágjuk fel 4 egybevágó részre. A megfordításhoz használjuk ki, hogy az eredeti négyzet minden sarkára kell illeszkednie egy kis négyzetnek, tehát n eleve nem lehet 2 vagy 3, az n=5 esetben pedig a nagy négyzet egyik oldalára 3, a többi oldalra 2 kis négyzet illeszkedne, ami egyszerű esetszétválasztás után szintén ellentmondásra vezet.

b) Mivel egy kockából könnyen csinálhatunk 8, illetve 27 kis kockát, ezek egymás utáni alkalmazásával egy kocka 1+7x+26y részre is bontható, ahol x és y tetszőleges nemnegatív egészek. Felhasználva, hogy a 7 és a 26 relatív prímek, lássuk be, hogy minden elég nagy n előállítható ilyen alakban.

c) Mivel egy kockát 8 részre vágva, a kis kockák számát mindig tudjuk 7-tel növelni, ezért elég az állítást a 48 és 54 közötti n-ekre igazolni. 48:48=27+3·7, azaz a kockát vágjuk 27 részre, majd 3 kis kockát 8-8 részre. 49: egy 6 oldalú kocka alsó felét bontsuk 4 darab 3 oldalú kockára, a felső sorát 36 darab egységkockára, a fennmaradó két sort pedig 9 darab 2 oldalú kockára. 50:50=7·7+1. 51: egy 6 oldalú kocka alsó felét és még egy nyolcadát bontsuk 5 darab 3 oldalú kockára, a megmaradt részből kiválaszthatunk 5 darab 2 oldalú kockát és marad még 41 darab egységkocka. 52: egy 4 oldalú kockából vegyünk ki egy 3 oldalú részt, ekkor marad 37 egységkocka, ezekből kettőt 8-8 részre osztva összesen 52 kockára bontottuk az eredeti kockát. 53:53=1+2·19+2·7 alapján elég olyan eljárást mutatni, amely 19-cel növeli a kockák darabszámát; egy 3 oldalú kockát bontsunk egy 2 oldalúra és a megmaradó 19 egységkockára. 54: egy 8 oldalú kocka háromnegyedét bontsuk 6 darab 4 oldalú kockára, a maradékból leválasztható 2 darab 3 oldalú és 4 darab 2 oldalú kocka, valamint marad 42 darab egységkocka.

9.7.7

a) Ha n≠2, 3 vagy 5, akkor a 9.7.6a feladathoz hasonló konstrukciót alkalmazhatunk. A megfordítás n=2-re most is egyszerű, azonban n=3-ra és 5-re a négyzethez képest bonyolítja a helyzetet, hogy a kis háromszögek az eredeti háromszög szögeit is elvághatják. Itt jó szolgálatot tesz az alábbi, önmagában is érdekes észrevétel: Ha egy H háromszög szögei a racionális test felett lineárisan függetlenek, akkor H csak úgy bontható fel hasonló háromszögekre, ha azok H-hoz is hasonlók, továbbá ekkor H felbontásánál a kis háromszögek H szögeit nem vághatják el.

b) Ha n=k2, akkor egy háromszög minden oldalát k egyenlő részre osztva a háromszöget nyilván n egybevágó kis háromszögre bontottuk. A megfordításhoz vegyünk egy olyan háromszöget, amelyben nemcsak a szögek, hanem az oldalak is lineárisan függetlenek. Mutassuk meg, hogy valóban létezik ilyen háromszög, továbbá egy ilyen háromszöget nem lehet n egybevágó háromszögre felbontani, ha n irracionális.

c) Ha n=k2+m2, akkor vegyünk egy olyan derékszögű háromszöget, amelynek a befogói k és m. Ha n=3k2, akkor egy szabályos háromszög „fele” lesz megfelelő.

9.8.

9.8.1 Ha pl. a_n=j=1n-1λja_j akkor (i) miatt γ11γ12γ13γ14γ21γ22γ23γ24γ31γ32γ33γ341     1     1      1 és itt (iv) szerint mindegyik tag 0.

9.8.2 A 9.8.1 Tétel bizonyításának mintájára következik, hogy Da_1 ,a_2 . . . ,a_n=j=1n-1λjDa_1 ,a_2 . . . ,a_j már teljesen meghatározza Fi-t.

9.8.3 Használjuk fel az előző feladatot és az Fie_1 , . . . ,e_n egyenlőséget.

9.8.4 Támaszkodjunk az előző feladatra.

9.8.5

a) A determináns értéke nem változik, ha az első két oszlopból kivonjuk a harmadik oszlopot és a harmadik sora szerint kifejtjük. Az ennek megfelelő Fe_1 , . . . ,e_n=Ge_1 , . . . ,e_n determináns a P3-ból P1-be, illetve P2-be mutató vektorok által kifeszített paralelogramma előjeles területe. Ez a paralelogramma pontosan akkor fajul el, ha a pontok egy egyenesbe esnek.

b) A négy pont akkor és csak akkor van egy síkban, ha a koordinátáikból képezett γ11-γ13γ12-γ13γ21-γ23γ22-γ23 determináns nulla.

c) Az eredmények tetszőleges koordinátarendszerben érvényesek, ugyanis a 9.8.1 Tétel szerint tetszőleges bázist választhatunk.