Ugrás a tartalomhoz

Lineáris algebra

Freud Róbert (2014)

ELTE Eötvös Kiadó

4. Vektorterek

4. Vektorterek

• 4.2.12 e) Indirekt, tegyük fel, hogy V=i=1kWi  ahol a Wi-k valódi alterei a V-nek. Feltehetjük, hogy k a minimális lehetséges darabszám. Ekkor W1 i=2kWi  hiszen különben W1-et elhagyva V= i=2kWi is teljesülne. Legyenek u_ és v_ olyan vektorok, amelyekre u_W1 de u_Wi ha i>1, továbbá v_W1 Tekintsük a v_+λu_ λT 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≤ik és olyan λ≠λ’, amelyre v_+λu_Wi , v_+λ'u_Wi Itt i≠1, mert különben v_W1 következne. A két Wi-beli vektort kivonva kapjuk, hogy v_+λu_-v_+λ'u_=λ-λ'u_Wi  ahonnan u_Wi  ami ellentmondás.

f) Alkalmazzuk most is az e)-beli gondolatmenetet. A v_+λ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 b_0_ és c_αb_ (ilyen b_ és 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 λb_+μc_  λ, μT 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'=ϑc_+w_  ϑT ,wW  továbbá minden γT-re Wγ=ϑb_+γc_+ω_  ϑT ,w_W   Könnyen igazolható, hogy ezek valóban alterek. Megmutatjuk, hogy ezek egyike sem egyezik meg V-vel. Pl. Wγ-nak nem lehet eleme c_  Ellenkező esetben ugyanis c_=ϑb_+γc_+w_  ahonnan átrendezéssel w_=-ϑb_+1-ϑγc_ adódik. A W altérre szabott feltételünk szerint itt a jobb oldalon a nullvektor áll, ez viszont b_0_ és c_αb_ miatt csak a ϑ=1-ϑγ=0 önmagának ellentmondó esetben valósulhatna meg. Hasonlóan igazolhatjuk, hogy b_W'  Végül belátjuk, hogy tetszőleges u_V vektor benne van a megadott k+1 valódi altér egyesítésében. Legyen U=ϑu_+w_ϑT ,w_W   Ekkor U altér, és W maximalitása miatt van olyan λb_+μc_0_ vektor, amely eleme U-nak: ϑu_+w_=λb_+μc_  Itt a W-re adott feltétel szerint ϑ nem lehet 0, ezért u_ kifejezhető u_=λ/ϑb_+μ/ϑc_-1/ϑw_ alakban. Innen kapjuk, hogy λ=0 esetén u_W'  egyébként pedig u_Wμ/λ 

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 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 b_1, . . . ,b_100 egy bázis V-ben. Ekkor pl. a v_γ=b_1+γb_2++γ2b_3+. . .+γ99b_100  γR 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, v_1, . . . ,v_100 -at. A v_101 -et írjuk fel ezek lineáris kombinációjaként: v_101=i=1100αiv_i Ha itt valamelyik αi=0, akkor az ennek megfelelő v_i kivételével a többi 100 v_j vektor nyilván összefüggő, ami ellentmondás. Így minden αi=1, vagyis a v_101 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 v_101=i=1100αiv_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 v_101=i=1100v_i  Tegyük fel, hogy létezne még egy v_102=i=1100βiv_i  vektor. A skatulyaelv alapján van olyan ij, amelyre βij, pl. β12. Ekkor v_102-β1v_101 előállítható v_3, . . . ,v_100 lineáris kombinációjaként, és így a v_3, . . . ,v_102 vektorok lineárisan összefüggők, ami ellentmondás.

Az F101 test felett már 102 ilyen tulajdonságú vektor is létezik: legyen v_1, . . . ,v_100 tetszőleges bázis, v_101=i=1100v_i  és v_102=i=1100iv_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 F97-nél látott gondolatmenethez hasonlóan feltehető, hogy v_101=i=1100v_i  és v_102=i=1100βiv_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 v_103=i=1100γiv_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 γiiβ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. δ12, akkor v_103-δ1v_102 előállítható v_3, . . . ,v_100 lineáris kombinációjaként, és így a v_3, . . . ,v_100,v_102,v_103 vektorok lineárisan összefüggők, ami ellentmondás. Szorozzuk össze a(z F101-beli) γiiβ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 st’<

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

Az As mátrix v_1, . . . ,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=1tαiv_i=0_  Képezzük mindkét oldalnak egy tetszőleges 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 αj2s-1+ijαj2s-2=0  azaz 2s-2αj+i=1tαi=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 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=|YZ| mod 2 (ahol Y, ZX).