Ugrás a tartalomhoz

Lineáris algebra

Freud Róbert (2014)

ELTE Eötvös Kiadó

C. függelék - MEGOLDÁSOK

C. függelék - MEGOLDÁSOK

1. Determinánsok

• 1.1.5 b) Válasz: 2 n - 4 / 5 + 1   ahol x az x szám felső egész részét jelenti, azaz a legkisebb olyan egész számot, amely ≥x.

Bizonyítás: Egy rögzített permutációban tekintsünk egy a<b elempárt, és jelöljük m(a,b)-vel azoknak a c elemeknek a számát, amelyek a és b között helyezkednek el és amelyekre a<c<b. Az ilyen c-ket az adott cserénél fontos elemeknek fogjuk nevezni. [Pl. a 3165472 permutációban m(2,6)=2, mert az 5 és a 4 a fontos elemek.] Ekkor az a és b cseréjénél az inverziószám 2m(a,b)+1-gyel változik, ugyanis az a-nak és a b-nek az egymáshoz és a fontos elemekhez való viszonya változik meg.

Legyen egy adott permutációban M az összes m(a,b) érték maximuma. A bizonyítandó állítás az előzőek alapján azzal ekvivalens, hogy (i) bármely

permutációra Mn-4/5  és (ii) van olyan permutáció, amelyre

M = n - 4 / 5   .

Először (i)-et igazoljuk. Vegyünk egy tetszőleges permutációt. Azzal az esettel foglalkozunk, amikor az 1 és n számok egyike sem az első vagy utolsó elem. A fennmaradó esetekben ugyanis hasonló (csak egyszerűbb) meggondolásokat kell alkalmazni (és kiderül, hogy akkor még nagyobb M adódik), ezt nem részletezzük.

Tegyük fel, hogy az első, illetve az utolsó helyen álló elem a k, illetve az r, továbbá az n (mondjuk) előrébb áll, mint az 1, azaz a permutáció kn…1…r alakú.

Megmutatjuk, hogy a k, az n, az 1 és az r kivételével minden elem fontos az alábbi öt csere közül legalább az egyiknél: (A) k és n; (B) k és 1; (C) n és 1; (D) n és r; (E) 1 és r.

Valóban, a permutációban a k és az n között álló elemek közül a k-nál nagyobbak (A)-nál fontosak, a k-nál kisebbek pedig (B)-nél. Az n és az 1 között állók valamennyien fontosak (C)-nél [emellett esetleg (B)-nél és/vagy (D)-nél is]. Végül, az 1 és az r között álló elemek közül az r-nél nagyobbak (D)-nél, az r-nél kisebbek pedig (E)-nél fontosak.

Így n-4≤m(k,n)+m(1,k)+m(1,n)+m(r,n)+m(1,r)≤5M, ahonnan Mn-4/5 , amint állítottuk.

Rátérve (ii)-re, nyilván elég az n=5t+4 esettel foglalkozni. Könnyű ellenőrizni, hogy az (i)-beli gondolatmenet alapján megsejthető

konstrukció egy megfelelő permutációt szolgáltat.

1.1.7 c) Válasz: páratlan k esetén minden páros n>k, páros k≠0 esetén n=2k+1 kivételével minden n>k, k=0 esetén minden n>0.

Szükségesség: (i) n>k nyilvánvaló. (ii) Az összes inverziószám nk/2, tehát páratlan k esetén n páros kell hogy legyen. (iii) Az első elem pontosan akkor áll k másikkal inverzióban, ha k darab nála kisebb van, tehát ha az első elem k+1. Hasonlóan az utolsó elem n-k. Ez n=2k+1>1-re nyilván lehetetlen.

Elégségesség: Jelöljük /s,t\-vel, ha az 1,2,…,s számoknak létezik olyan permutációja, amelyben minden elem pontosan t másikkal áll inverzióban. Az alábbi két összefüggést fogjuk felhasználni:

(A)  /c,k-d,   /d,k-c /c+d,k

(B)  /f,k,   /g,k /uf+vg,k  ahol u,v tetszőleges pozitív egészek.

(A) igazolásához legyenek a /c,k-d\, illetve /d,k-c\ feltételt biztosító permutációk i1,…,ic, illetve j1,…,jd, ekkor megfelel a d+i1,…,d+ic,j1,…,jd permutáció. (B) esetében az egyik kiindulási permutációt az 1,2,…,f, majd az f+1,…,2f stb. (u-1)f+1,…,uf blokkokra, utána pedig a másikat az uf+1,…,uf+g stb. blokkokra kell alkalmazni.

Az állítást k szerinti teljes indukcióval bizonyítjuk. Ha k=0 vagy 1, akkor az állítás nyilvánvaló. Tegyük fel, hogy az állítás igaz minden k’<k-ra és tetszőleges megfelelő n-re. Tekintsük most k-t, és legyen először k<n≤2k és kn páros. Legyen n=c+d, 1≤c,dk és c páros (általában n-nek több ilyen c+d előállítása is van). Ekkor c>k-d és d>k-c, tehát /c,k-d\ mindenképpen igaz és d(k-c)≡kn≡0 (mod 2) miatt /d,k-c\ is fennáll, ezért (A) alapján /c+d,k\=/n,k\ is érvényes. (A /d,k-c\-vel baj van, ha éppen d=2(k-c)+1, azonban ekkor vehetjük n-nek egy másik c+d előállítását, illetve ha csak egy van, akkor az /n,k\ állítás könnyen igazolható közvetlenül.) Ezután az n>2k eseteket a már bizonyított n≤2k-ból (B) felhasználásával láthatjuk be.

Megjegyezzük még, hogy (A) helyett a „fordított” permutációból adódó  /n,k   /n,n-1-k tulajdonsággal is dolgozhattunk volna.

1.4.13a) Ha M a nullmátrixot választja, akkor nyilván n lépésre van szükség. Megmutatjuk, hogy minden más esetben már kevesebb lépés is elég. Legyen r az a maximális szám, hogy az A mátrixból kiválasztható r oszlop és r sor úgy, hogy az ezek metszéspontjaiban álló (r2 darab elemből képzett) r×r-es determináns nem nulla. Ekkor n-r lépés elegendő. Tegyük fel, hogy például a bal felső sarokban álló r×r-es Dr determináns nem nulla. Vegyük ekkor a bal felső sarokban az eggyel nagyobb méretű (r+1)×(r+1)-es Dr+1 determinánst, és fejtsük ki az utolsó (azaz r+1-edik) sora szerint. Ebben a kifejtésben αr+1,r+1 együtthatója (a sorok és oszlopok más elhelyezkedése esetén esetleg előjeltől eltekintve) éppen Dr, tehát nem nulla. Ezért αr+1,r+1-et meg tudjuk úgy változtatni, hogy az így keletkező D’r+1 már ne legyen nulla. Most D’r+1-t bővítsük ki egy (r+2)×(r+2)-es determinánssá A következő sorából és oszlopából az első r+2 elem hozzávételével, és ismételjük meg az előző gondolatmenetet αr+2,r+2-re. Az eljárást folytatva n-r lépés után egy (n×n-es) nemnulla determinánsú A’ mátrixot kapunk. (A megoldásban tulajdonképpen a mátrix determinánsrangját használtuk, lásd a 3.4 pontot. Ha csak azt akartuk volna igazolni, hogy n lépés mindig elég, akkor teljes indukcióval és a fenti gondolatmenet egyszerűsített változatával is célhoz érhettünk volna.)

b) Ha M olyan mátrixot választ, amelynek az első oszlopa csupa nulla, akkor n2-n lépés kevés, ugyanis M kijelölheti a mátrix többi elemét. Indukcióval megmutatjuk, hogy n2-n+1 lépés mindig elég. Az n=1 esetben ez nyilvánvaló. Legyen n>1, és tekintsük az M által megadott tetszőleges n×n-es A mátrixot és a kijelölt n2-n+1 helyet. Kell lennie olyan sornak, ahol C bármely elemet megváltoztathat (hiszen különben csak legfeljebb n(n-1) kijelölt hely lenne), továbbá van olyan oszlop, ahol nem minden elem változtatható (hiszen a mátrixban nem minden hely van kijelölve). Ha pl. az első sor és első oszlop ilyen, akkor cserélje C az első sor első elemét 1-re, az első sor többi elemét pedig 0-ra. Mivel az első sor és oszlop összesen 2n-1 eleme közül nem mindegyik van kijelölve, ezért az első sor és oszlop elhagyásával keletkező (n-1)×(n-1)-es B mátrixban legalább (n2-n+1)-(2n-2)=(n-1)2-(n-1)+1 kijelölt hely van. Az indukció alapján B átalakítható nem nulla determinánsú B’ mátrixszá. Legyen most A’ az az n×n-es mátrix, amelynek első sora A első sorából a korábban jelzett változtatással keletkezik, első oszlopa az első elemtől eltekintve megegyezik A első oszlopával, a többi elemet pedig B’ alkotja. Ekkor A’-t az első sor szerint kifejtve kapjuk, hogy det A’=det B’≠0.

ca) Azonos az 1.2.7 feladattal.

cb) Ha M olyan mátrixot választ, amelynek a főátlója csupa egyes, a főátló fölött pedig minden elem nulla, akkor (n2-n)/2 lépés kevés, ugyanis M kijelölheti a mátrix többi elemét. Indukcióval megmutatjuk, hogy 1+(n2-n)/2 lépés mindig elég. Az n=1 esetben ez nyilvánvaló. Legyen n>1, és tekintsük az M által megadott tetszőleges n×n-es A mátrixot és a kijelölt 1+(n2-n)/2 helyet.

Ha minden oszlopban van legalább egy kijelölt hely, akkor ezeket változtassuk meg úgy, hogy minden oszlopban az elemek összege 0 legyen. Ekkor minden sort az utolsó sorhoz hozzáadva egy csupa 0 sor keletkezik, tehát a determináns nulla.

Ha pl. az első oszlopban egyetlen hely sincs kijelölve, de minden elem nulla, akkor semmit sem kell változtatnunk.

Ha az első oszlopban egyetlen hely sincs kijelölve és pl. α11≠0, akkor minden sorból vonjuk ki az első sor megfelelő többszörösét, hogy az első oszlop többi eleme nullává váljon. Most hagyjuk el az első sort és oszlopot, az így keletkező (n-1)×(n-1)-es B1 mátrixban legalább

kijelölt hely van, így az indukció alapján ez átalakítható nulla determinánsú B’ mátrixszá. „Vezessük át” az ennek megfelelő változtatást az eredeti A mátrixba. Az így kapott A’ mátrixot az első oszlop „kinullázása” után az első sor szerint kifejtve a kívánt detA’=detB’=0 adódik.

1.4.14 Megfelel bármely olyan mátrix, amelynek a determinánsa nulla, de egyik Aij előjeles aldeterminánsa sem nulla, ugyanis αij -t megváltoztatva az i-edik sor (vagy a j-edik oszlop) szerinti kifejtés értéke biztosan megváltozik. Ilyen mátrixot pl. úgy gyárthatunk, hogy veszünk egy (n-1)×(n-1)-es mátrixot, amelynek a determinánsa nem nulla és kiegészítjük egy n-edik sorral és oszloppal úgy, hogy a keletkező n×n-es mátrixban minden sor és minden oszlop összege nulla legyen (vö. az 1.4.11 feladattal).

1.5.6 A mértani sorozat összegképletét használva az i-edik sor j-edik eleme 1+αiβj+ . . . +αin-1βjn-1  tehát minden sor egy n-tagú összeg. Ennek alapján a determinánst nn darab determináns összegére bonthatjuk, amelyek mindegyikében az i-edik sor j-edik eleme αikβjk alakú, ahol 0≤kn-1. Az így keletkező determinánsok közül igen sokban lesz két egyforma sor, ezek értéke nulla. A fennmaradó determinánsokban a j-edik oszlop elemei rendre α1π1βjπ1, α2π2βjπ2, . . . , αnπnβjπn  ahol π(1),…,π(n) a 0,1,…,n-1 számok valamilyen permutációja. Az α1π1, . . . , αnπn számoknak a sorokból történő kiemelése és I(π) számú sorcsere után éppen V1,…,βn) marad. Az eredeti determinánsunk értéke így Vβ1, . . . ,βn-1Iπα1π1 . . . αnπn=Vβ1, . . . ,βn Vα1, . . . ,αn — Egy másik megoldási lehetőség a determinánsok szorzástételének (2.2.4 Tétel) alkalmazása (lásd a 2.2.8 feladatot).