Freud Róbert (2014)
ELTE Eötvös Kiadó
• 4.2.12 e) Indirekt, tegyük fel, hogy ahol a Wi-k valódi alterei a V-nek. Feltehetjük, hogy k a minimális lehetséges darabszám. Ekkor hiszen különben W1-et elhagyva is teljesülne. Legyenek és olyan vektorok, amelyekre de ha i>1, továbbá Tekintsük a végtelen sok vektort. A feltétel szerint ezek valamennyien elemei a véges sok Wj közül valamelyiknek, tehát van olyan 1≤i≤k és olyan λ≠λ’, amelyre Itt i≠1, mert különben következne. A két Wi-beli vektort kivonva kapjuk, hogy ahonnan ami ellentmondás.
• f) Alkalmazzuk most is az e)-beli gondolatmenetet. A vektorok száma most |T|. Ha |T|>k-1, akkor ugyanúgy ellentmondásra jutunk, mint az előbb. Így valóban k≥|T|+1.
• g) Legyen és (ilyen és vektorok biztosan találhatók, ha a V vektortérnek van nemtriviális altere). Legyen W egy maximális (azaz tovább már nem bővíthető) olyan altér V-ben, amelynek a halmazzal való metszete csak a nullvektorból áll. (Ilyen W létezik, véges elemszámú vektortér esetén ez nyilvánvaló, végtelen elemszám esetén pedig a szokásos halmazelméleti módszerekkel — pl. a Zorn-lemmával — igazolható.) Azt állítjuk, hogy ekkor az alábbi k+1 darab valódi altér egyesítése kiadja a V vektorteret: továbbá minden -re Könnyen igazolható, hogy ezek valóban alterek. Megmutatjuk, hogy ezek egyike sem egyezik meg V-vel. Pl. Wγ-nak nem lehet eleme Ellenkező esetben ugyanis ahonnan átrendezéssel adódik. A W altérre szabott feltételünk szerint itt a jobb oldalon a nullvektor áll, ez viszont és miatt csak a ϑ=1-ϑγ=0 önmagának ellentmondó esetben valósulhatna meg. Hasonlóan igazolhatjuk, hogy Végül belátjuk, hogy tetszőleges vektor benne van a megadott k+1 valódi altér egyesítésében. Legyen Ekkor U altér, és W maximalitása miatt van olyan vektor, amely eleme U-nak: Itt a W-re adott feltétel szerint ϑ nem lehet 0, ezért kifejezhető alakban. Innen kapjuk, hogy λ=0 esetén egyébként pedig
• Megjegyzés: érdemes végiggondolni, hogy az itt elmondott bizonyítás az útmutatásban jelzett utat valósítja meg. Magát a bizonyítást is a fentinél jóval kényelmesebben lehet(ne) leírni a dimenzió, továbbá a faktortér vagy a direkt összeg felhasználásával, de ezekre nem akartunk támaszkodni.
• 4.4.11 A feladat egyes részei sokféleképpen vizsgálhatók, pl. a) igazsága nyilvánvaló a definícióból, c)-re könnyű ellenpéldát találni. Az egységes tárgyalásmód érdekében azonban érdemes azt a k×m-es mátrixot venni, amelynek az oszlopai az vektorok. A vektorok függetlensége azt jelenti, hogy ennek a mátrixnak a rangja m. A mátrixrangot most determinánsrangként célszerű tekinteni. Mivel egy egész elemű mátrix determinánsa mindig egész szám, ezért mindegy, hogy a rangot R vagy Q felett tekintjük-e, tehát a) és b) igaz. A modulo p esetben a determináns p-vel való oszthatóságát kell vizsgálni. Egy nullától különböző egész lehet páros, ezért c) hamis. Egy páratlan szám viszont biztosan nem nulla, tehát d) igaz. Végül egy nullától különböző egész csak véges sok prímmel lehet osztható, tehát e) is igaz. (Vö. a 3.4.8 és 4.6.16 feladatokkal.)
• 4.6.7 a) Legyen egy bázis V-ben. Ekkor pl. a végtelen sok vektor közül bármely 100 bázist alkot. Ehhez elég belátni, hogy bármely 100 ilyen vektor lineárisan független. Ez onnan adódik, hogy a megfelelő homogén lineáris egyenletrendszer determinánsa egy csupa különböző elemmel generált Vandermonde-determináns, tehát nem nulla.
• b) Az F2 test felett 101 ilyen vektor megadható: egy tetszőleges bázis és a báziselemek összege megfelelő. Megmutatjuk, hogy ennél több vektor már nem lehet. Vegyük bázisnak az első 100 vektort, -at. A -et írjuk fel ezek lineáris kombinációjaként: Ha itt valamelyik αi=0, akkor az ennek megfelelő kivételével a többi vektor nyilván összefüggő, ami ellentmondás. Így minden αi=1, vagyis a vektor egyértelműen meghatározott, tehát a rendszer tovább nem bővíthető.
Az F97 test felett is egy tetszőleges bázis és a báziselemek összege megfelelő 101 vektort alkot. Belátjuk, hogy itt sem lehet ennél több vektort megadni. Az F2-nél látott gondolatmenethez hasonlóan a vektor mindegyik αi együtthatója most is nullától különböző. Az első 100 vektor helyett esetleg azok alkalmas skalárszorosát véve elérhető, hogy minden αi=1 legyen, azaz Tegyük fel, hogy létezne még egy vektor. A skatulyaelv alapján van olyan i≠j, amelyre βi=βj, pl. β1=β2. Ekkor előállítható lineáris kombinációjaként, és így a vektorok lineárisan összefüggők, ami ellentmondás.
Az F101 test felett már 102 ilyen tulajdonságú vektor is létezik: legyen tetszőleges bázis, és Könnyen látható, hogy ezek a vektorok valóban a kívánt tulajdonságúak. Megmutatjuk, hogy 103 ilyen vektor már nem adható meg. Az F97-nél látott gondolatmenethez hasonlóan feltehető, hogy és ahol a βi-k egymástól és nullától különbözők. Ennélfogva a βi-k az 1,2,...,100 számok egy permutációját alkotják. Tegyük fel, hogy létezne még egy vektor. Ekkor szükségképpen a γi-k is az 1,2,...,100 számok egy permutációját alkotják. Emellett a γi=δiβi előállításnál a δi-k egymástól (és nullától) különbözők kell hogy legyenek, ugyanis ha pl. δ1=δ2, akkor előállítható lineáris kombinációjaként, és így a vektorok lineárisan összefüggők, ami ellentmondás. Szorozzuk össze a(z F101-beli) γi=δiβi,i=1,2,…,100 egyenlőségeket. Modulo 101 kongruenciákkal számolva a Wilson-tétel alapján kapjuk, hogy
ami ellentmondás.
• 4.6.16 c) Jelölje egy 0-1 mátrixnak az F2 feletti rangját s, a Q feletti rangját pedig t. Vegyünk s darab (F2 felett) lineárisan független oszlopot, ezeknek 2s-1 számú nemtriviális lineáris kombinációja képezhető. Így a mátrixnak bármely 2s-1-nél több oszlopa között vagy szerepel egy csupa nulla oszlop, vagy pedig előfordul két azonos oszlop, ezért 2s-1-nél több oszlop Q felett sem lehet független. Ebből következik, hogy t≤2s-1. Megfordítva, megmutatjuk, hogy tetszőleges (s≤)t≤ 2s-1 esetén létezik olyan t×t-es 0-1 mátrix, amelynek az F2 feletti rangja s, a Q feletti rangja pedig t. Innen kapjuk, hogy az 1000-es különbséget biztosító legkisebb s érték az s=10, és ekkor a mátrix mérete t=s+1000=1010.
A megfordítást elegendő a t=2s-1 esetre igazolni. Ha ugyanis s≤t’<
<2s-1, akkor hagyjunk el a megfelelő (2s-1)×(2s-1) méretű A mátrixból 2s-1-t’ számú oszlopot úgy, hogy a megmaradók között szerepeljen s olyan oszlop, amelyek F2 felett függetlenek. Ekkor a megmaradó t’ számú oszlop Q felett továbbra is független, tehát ennek a ( 2s-1)×t’ méretű B mátrixnak a Q feletti rangja t’, az F2 feletti rangja pedig s. Tartsunk most meg B-ből s olyan sort, amelyek F2 felett függetlenek. Ekkor ezek Q felett is függetlenek, tehát hozzávehetünk még t’-s további sort B-ből, hogy a kapott t’ sor Q felett független legyen. Az így adódó t’×t› méretű C mátrix megfelel; a Q feletti rangja t’, az F2 feletti rangja pedig s.
Legyen tehát t=2s-1, és készítsünk egy olyan t×t-es 0-1 mátrixot, amelynek az F2 feletti rangja s, a Q feletti rangja pedig t. A mátrix első s oszlopába soronként rendre az 1,2,…,2s-1 számoknak a kettes számrendszerbeli számjegyei kerülnek, tehát az első sor első s eleme(0,0,…,0,0,1), a második soré (0,0,…,0,1,0), a harmadik soré (0,0,…,0,1,1) stb. A többi oszlop legyen ezután az első s oszlopnak az F2 test felett képzett összes (további) nemtriviális lineáris kombinációja (azaz ahol legalább két együttható nem nulla). Így egy (2s-1)×(2s-1) méretű 0-1 mátrixot kapunk. Megmutatjuk, hogy ennek az oszlopai a Q felett függetlenek, vagyis a Q feletti rang 2s-1. Ebből a konstrukció és az elején látottak alapján az is következik, hogy az F2 feletti rang s.
Az áttekinthetőség kedvéért egészítsük ki a mátrixunkat a tetején egy csupa nulla sorral (ez az oszlopok függetlenségi viszonyain nyilván nem változtat). Az s szerinti teljes indukcióval megmutatjuk, hogy az így kapott 2s×(2s-1) méretű As mátrix bármely oszlopában a 2s darab elem fele 1, másik fele pedig 0. Ez s=1-re nyilvánvaló. Legyen s-1-re az első s-1 oszlopvektor (minden vektornak 2s-1 komponense van). Ekkor s-re a konstrukció szerint a következőképpen kapjuk meg az első s oszlopot (ezek mindegyike 2s komponensből áll):
Mivel az indukciós feltevés szerint az vektorok komponenseinek pontosan a fele volt 1-es, ezért ez a tulajdonság öröklődik a vektorokra is. Ezzel beláttuk, hogy s-re az első s oszlop rendelkezik a jelzett tulajdonsággal. A további oszlopokat az első s oszlop F2 felett vett nemtriviális lineáris kombinációjaként, azaz néhány összegeként kapjuk. Ha az összeadandók között nem szerepel a akkor az összegvektor „alsó és felső fele” ugyanúgy azonos, mint az összeadandóknál, tehát ugyanazt az indukciós következtetést alkalmazhatjuk, mint az első oszlopok esetében. Ha még a -et is hozzáadjuk egy ilyen vektorhoz, akkor az „alsó felében” az 1-esek és a 0-k helyet cserélnek, de mivel a számuk az indukciós feltevés szerint ugyanannyi volt, ezért most is készen vagyunk.
Szükségünk lesz még arra, hogy (s>1 esetén) az As mátrix bármely két oszlopában az azonos helyeken szereplő 1-esek száma 2s-2. Legyen és két tetszőleges oszlop, és legyen x azoknak a helyeknek a száma, ahol mindkettőben 1-es szerepel. Ekkor -nak és -nek is további 2s-1-x olyan komponense van, ahol az illető vektorban 1-es áll. Az F2 felett képzett vektor a konstrukció alapján előfordul As oszlopai között és -ben azokra a helyekre kerül 1-es, ahol -ban és -ben különböző értékek szerepeltek. Így -ben az 1-esek száma 2(2s-1-x)=2s-1. Innen x= 2s-2, ahogy állítottuk.
Az As mátrix oszlopainak a Q feletti lineáris függetlenségét a skalárszorzat (részletesen lásd a 7.1, 8.1, illetve 9.4 pontokban) segítségével igazoljuk. (Az s=1 esetben az állítás nyilvánvaló, tehát feltehetjük, hogy s≥2, bár az alábbi bizonyítás formálisan az s=1esetre is helyes.) Legyen Képezzük mindkét oldalnak egy tetszőleges vektorral a skalárszorzatát. Két 0-1 vektor skalárszorzata a közös helyeken előforduló 1-esek száma. Az előző két bekezdésben igazoltak alapján így az azaz egyenlőséghez jutunk. Mivel ez minden j-re teljesül, ezért nyilván minden αi szükségképpen 0, amint állítottuk.
Megjegyezzük, hogy az As mátrix sor-, illetve oszlopcseréktől eltekintve a következőképpen is megadható: a sorokat indexezzük az X={1,2,…,s} halmaz részhalmazai, az oszlopokat pedig az X nemüres részhalmazai szerint, és legyen αY,Z=|Y∩Z| mod 2 (ahol ).