• 4.2.12 e) Indirekt, tegyük fel, hogy $V={}_{i=1}^k{W}_i$ ahol a W_i-k valódi alterei a V-nek. Feltehetjük, hogy k a minimális lehetséges darabszám. Ekkor $W_1{ }_{i=2}^k{W}_i$ hiszen különben W₁-et elhagyva $V={ }_{i=2}^k{W}_i$ is teljesülne. Legyenek $\underset{\_}{u}$ és $\underset{\_}{v}$ olyan vektorok, amelyekre $\underset{\_}{u}{W}_1$ de $\underset{\_}{u}{W}_i$ ha i>1, továbbá $\underset{\_}{v}{W}_1$ Tekintsük a $\underset{\_}{v}+\lambda \underset{\_}{u} \left(\lambda T\right)$ végtelen sok vektort. A feltétel szerint ezek valamennyien elemei a véges sok W_j közül valamelyiknek, tehát van olyan 1≤i≤k és olyan λ≠λ’, amelyre $\underset{\_}{v}+\lambda \underset{\_}{u}{W}_i , \underset{\_}{v}+{\lambda }^{\text{'}}\underset{\_}{u}{W}_i$ Itt i≠1, mert különben $\underset{\_}{v}{W}_1$ következne. A két W_i-beli vektort kivonva kapjuk, hogy $\left(\underset{\_}{v}+\lambda \underset{\_}{u}\right)-\left(\underset{\_}{v}+{\lambda }^{\text{'}}\underset{\_}{u}\right)=\left(\lambda -{\lambda }^{\text{'}}\right)\underset{\_}{u}{W}_i$ ahonnan $\underset{\_}{u}{W}_i$ ami ellentmondás.

• f) Alkalmazzuk most is az e)-beli gondolatmenetet. A $\underset{\_}{v}+\lambda \underset{\_}{u}$ 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 $\underset{\_}{b}\ne \underset{\_}{0}$ és $\underset{\_}{c}\ne \alpha \underset{\_}{b}$ (ilyen $\underset{\_}{b}$ és $\underset{\_}{c}$ 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 $\left\{\left.\lambda \underset{\_}{b}+\mu \underset{\_}{c} \right| \lambda , \mu T\right\}$ 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: $W^{\text{'}}=\left\{\left.\vartheta \underset{\_}{c}+\underset{\_}{w} \right| \vartheta T ,wW \right\}$ továbbá minden $\gamma T$-re $W_{\gamma }=\left\{\left.\vartheta \left(\underset{\_}{b}+\gamma \underset{\_}{c}\right)+\underset{\_}{\omega } \right| \vartheta T ,\underset{\_}{w}W \right\}$ Könnyen igazolható, hogy ezek valóban alterek. Megmutatjuk, hogy ezek egyike sem egyezik meg V-vel. Pl. W_γ-nak nem lehet eleme $\underset{\_}{c}$ Ellenkező esetben ugyanis $\underset{\_}{c}=\vartheta \left(\underset{\_}{b}+\gamma \underset{\_}{c}\right)+\underset{\_}{w}$ ahonnan átrendezéssel $\underset{\_}{w}=-\vartheta \underset{\_}{b}+\left(1-\vartheta \gamma \right)\underset{\_}{c}$ adódik. A W altérre szabott feltételünk szerint itt a jobb oldalon a nullvektor áll, ez viszont $\underset{\_}{b}\ne \underset{\_}{0}$ és $\underset{\_}{c}\ne \alpha \underset{\_}{b}$ miatt csak a ϑ=1-ϑγ=0 önmagának ellentmondó esetben valósulhatna meg. Hasonlóan igazolhatjuk, hogy $\underset{\_}{b}{W}^{\text{'}}$ Végül belátjuk, hogy tetszőleges $\underset{\_}{u}V$ vektor benne van a megadott k+1 valódi altér egyesítésében. Legyen $U=\left\{\left.\vartheta \underset{\_}{u}+\underset{\_}{w}\right|\vartheta T ,\underset{\_}{w}W \right\}$ Ekkor U altér, és W maximalitása miatt van olyan $\lambda \underset{\_}{b}+\mu \underset{\_}{c}\ne \underset{\_}{0}$ vektor, amely eleme U-nak: $\vartheta \underset{\_}{u}+\underset{\_}{w}=\lambda \underset{\_}{b}+\mu \underset{\_}{c}$ Itt a W-re adott feltétel szerint ϑ nem lehet 0, ezért $\underset{\_}{u}$ kifejezhető $\underset{\_}{u}=\left(\lambda /\vartheta \right)\underset{\_}{b}+\left(\mu /\vartheta \right)\underset{\_}{c}-\left(1/\vartheta \right)\underset{\_}{w}$ alakban. Innen kapjuk, hogy λ=0 esetén $\underset{\_}{u}{W}^{\text{'}}$ egyébként pedig $\underset{\_}{u}{W}_{\mu /\lambda }$

• 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 ${\underset{\_}{u}}_j$ 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 ${\underset{\_}{b}}_1, . . . ,{\underset{\_}{b}}_{100}$ egy bázis V-ben. Ekkor pl. a ${\underset{\_}{v}}_{\gamma }={\underset{\_}{b}}_1+\gamma {\underset{\_}{b}}_2++{\gamma }^2{\underset{\_}{b}}_3+. . .+{\gamma }^{99}{\underset{\_}{b}}_{100} \left(\gamma \mathbf{R}\right)$ 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 F₂ 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, ${\underset{\_}{v}}_1, . . . ,{\underset{\_}{v}}_{100}$ -at. A ${\underset{\_}{v}}_{101}$ -et írjuk fel ezek lineáris kombinációjaként: ${\underset{\_}{v}}_{101}={}_{i=1}^{100}{\alpha }_i{\underset{\_}{v}}_i$ Ha itt valamelyik α_i=0, akkor az ennek megfelelő ${\underset{\_}{v}}_i$ kivételével a többi $100 {\underset{\_}{v}}_j$ vektor nyilván összefüggő, ami ellentmondás. Így minden α_i=1, vagyis a ${\underset{\_}{v}}_{101}$ vektor egyértelműen meghatározott, tehát a rendszer tovább nem bővíthető.

Az F₉₇ 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 F₂-nél látott gondolatmenethez hasonlóan a ${\underset{\_}{v}}_{101}={}_{i=1}^{100}{\alpha }_i{\underset{\_}{v}}_i$ 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 ${\underset{\_}{v}}_{101}={}_{i=1}^{100}{\underset{\_}{v}}_i$ Tegyük fel, hogy létezne még egy ${\underset{\_}{v}}_{102}={}_{i=1}^{100}{\beta }_i{\underset{\_}{v}}_i$ vektor. A skatulyaelv alapján van olyan i≠j, amelyre β_i=β_j, pl. β₁=β₂. Ekkor ${\underset{\_}{v}}_{102}-{\beta }_1{\underset{\_}{v}}_{101}$ előállítható ${\underset{\_}{v}}_3, . . . ,{\underset{\_}{v}}_{100}$ lineáris kombinációjaként, és így a ${\underset{\_}{v}}_3, . . . ,{\underset{\_}{v}}_{102}$ vektorok lineárisan összefüggők, ami ellentmondás.

Az F₁₀₁ test felett már 102 ilyen tulajdonságú vektor is létezik: legyen ${\underset{\_}{v}}_1, . . . ,{\underset{\_}{v}}_{100}$ tetszőleges bázis, ${\underset{\_}{v}}_{101}={}_{i=1}^{100}{\underset{\_}{v}}_i$ és ${\underset{\_}{v}}_{102}={}_{i=1}^{100}i{\underset{\_}{v}}_i$ 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 F₉₇-nél látott gondolatmenethez hasonlóan feltehető, hogy ${\underset{\_}{v}}_{101}={}_{i=1}^{100}{\underset{\_}{v}}_i$ és ${\underset{\_}{v}}_{102}={}_{i=1}^{100}{\beta }_i{\underset{\_}{v}}_i$ 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 ${\underset{\_}{v}}_{103}={}_{i=1}^{100}{\gamma }_i{\underset{\_}{v}}_i$ 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. δ₁=δ₂, akkor ${\underset{\_}{v}}_{103}-{\delta }_1{\underset{\_}{v}}_{102}$ előállítható ${\underset{\_}{v}}_3, . . . ,{\underset{\_}{v}}_{100}$ lineáris kombinációjaként, és így a ${\underset{\_}{v}}_3, . . . ,{\underset{\_}{v}}_{100},{\underset{\_}{v}}_{102},{\underset{\_}{v}}_{103}$ vektorok lineárisan összefüggők, ami ellentmondás. Szorozzuk össze a(z F₁₀₁-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 F₂ feletti rangját s, a Q feletti rangját pedig t. Vegyünk s darab (F₂ felett) lineárisan független oszlopot, ezeknek 2^s-1 számú nemtriviális lineáris kombinációja képezhető. Így a mátrixnak bármely 2^s-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 2^s-1-nél több oszlop Q felett sem lehet független. Ebből következik, hogy t≤2^s-1. Megfordítva, megmutatjuk, hogy tetszőleges (s≤)t≤ 2^s-1 esetén létezik olyan t×t-es 0-1 mátrix, amelynek az F₂ 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=2^s-1 esetre igazolni. Ha ugyanis s≤t’<

<2^s-1, akkor hagyjunk el a megfelelő (2^s-1)×(2^s-1) méretű A mátrixból 2^s-1-t’ számú oszlopot úgy, hogy a megmaradók között szerepeljen s olyan oszlop, amelyek F₂ felett függetlenek. Ekkor a megmaradó t’ számú oszlop Q felett továbbra is független, tehát ennek a ( 2^s-1)×t’ méretű B mátrixnak a Q feletti rangja t’, az F₂ feletti rangja pedig s. Tartsunk most meg B-ből s olyan sort, amelyek F₂ 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 F₂ feletti rangja pedig s.

Legyen tehát t=2^s-1, és készítsünk egy olyan t×t-es 0-1 mátrixot, amelynek az F₂ feletti rangja s, a Q feletti rangja pedig t. A mátrix első s oszlopába soronként rendre az 1,2,…,2^s-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 F₂ 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 (2^s-1)×(2^s-1) méretű 0-1 mátrixot kapunk. Megmutatjuk, hogy ennek az oszlopai a Q felett függetlenek, vagyis a Q feletti rang 2^s-1. Ebből a konstrukció és az elején látottak alapján az is következik, hogy az F₂ 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 2^s×(2^s-1) méretű A_s mátrix bármely oszlopában a 2^s darab elem fele 1, másik fele pedig 0. Ez s=1-re nyilvánvaló. Legyen s-1-re az első s-1 oszlopvektor ${\underset{\_}{a}}_1, . . . ,{\underset{\_}{a}}_{s-1}$ (minden ${\underset{\_}{a}}_i$ vektornak 2^s-1 komponense van). Ekkor s-re a konstrukció szerint a következőképpen kapjuk meg az első s oszlopot (ezek mindegyike 2^s komponensből áll):

Mivel az indukciós feltevés szerint az ${\underset{\_}{a}}_i$ vektorok komponenseinek pontosan a fele volt 1-es, ezért ez a tulajdonság öröklődik a ${\underset{\_}{b}}_j$ 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 F₂ felett vett nemtriviális lineáris kombinációjaként, azaz néhány ${\underset{\_}{b}}_j$ összegeként kapjuk. Ha az összeadandók között nem szerepel a ${\underset{\_}{b}}_1$ 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 ${\underset{\_}{b}}_1$ -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 A_s mátrix bármely két oszlopában az azonos helyeken szereplő 1-esek száma 2^s-2. Legyen $\underset{\_}{u}$ és $\underset{\_}{v}$ két tetszőleges oszlop, és legyen x azoknak a helyeknek a száma, ahol mindkettőben 1-es szerepel. Ekkor $\underset{\_}{u}$-nak és $\underset{\_}{v}$ -nek is további 2^s-1-x olyan komponense van, ahol az illető vektorban 1-es áll. Az F₂ felett képzett $\underset{\_}{u}+\underset{\_}{v}$ vektor a konstrukció alapján előfordul A_s oszlopai között és $\underset{\_}{u}+\underset{\_}{v}$ -ben azokra a helyekre kerül 1-es, ahol $\underset{\_}{u}$ -ban és $\underset{\_}{v}$ -ben különböző értékek szerepeltek. Így $\underset{\_}{u}+\underset{\_}{v}$ -ben az 1-esek száma 2(2^s-1-x)=2^s-1. Innen x= 2^s-2, ahogy állítottuk.

Az A_s mátrix ${\underset{\_}{v}}_1, . . . ,{\underset{\_}{v}}_t$ 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 ${}_{i=1}^t{\alpha }_i{\underset{\_}{v}}_i=\underset{\_}{0}$ Képezzük mindkét oldalnak egy tetszőleges ${\underset{\_}{v}}_j$ 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 ${\alpha }_j{2}^{s-1}+{}_{i\ne j}{\alpha }_j{2}^{s-2}=0$ azaz $2^{s-2}\left({\alpha }_j+{}_{i=1}^t{\alpha }_i\right)=0$ 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 A_s 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 $Y, Z\subseteq X$).