Miskolci Egyetem. Diszkrét matek I. Vizsga-jegyzet. Hegedűs Ádám Imre

Miskolci Egyetem

Diszkrét matek I. Vizsga-jegyzet

Hegedűs Ádám Imre 2010.12.28.

Hegedűs Ádám Imre (KEB7GY)

Diszkrét matek I.

Vizsga-jegyzet

KOMBINATORIKA Permutáció Ismétlés nélküli permutáció alatt néhány különböző dolognak a sorba rendezését értjük. Az "ismétlés nélküli" arra utal, hogy a sorba rendezendő elemek különbözőek, azaz nem ismétlődnek. Egy n elemű halmaz összes permutációinak a száma:


 = ! =  ∙  − ∙  −  ∙ … ∙  ∙

Megjegyzés: Definíció szerint 0! = 1.

Példa: Hányféleképpen sorakozhatnak fel egy egyenes sorban egy 26 fős osztály tanulói? Az osztálynak, mint 26 elemű halmaznak 26! permutációja van, azaz ennyiféle sorrend lehetséges. Ismétléses permutáció alatt néhány, egymástól nem feltétlenül különböző dolognak a sorba rendezését értjük. Ha egy n elemű multihalmazban s különböző elem fordul elő, mégpedig az i-edik fajta elem ki-szer (és így n = k1 + k2 + .. .+ ks), akkor a multihalmaz összes ismétléses permutációinak a száma:




 ,  ,…, 

=

!

! ∙  ! ∙… ∙  !

Példa: Hányféleképpen lehet sorba rendezni az a, a, a, b, c, c, d, d betűket? Itt n=8 elemünk van, s=4 fajta, a betűből k1=3, b betűből k2=1, c és d betűkből k3=k4=2 darab, így a képlet alapján sorrend lehetséges. 8! ;;;

P = = 1680 3! ∙ 1! ∙ 2! ∙ 2!

Kombináció

Az ismétlés nélküli kombinációt alkalmazzuk akkor, ha adott egy véges halmaz, melynek n darabszámú elemeiből k elemszámú halmazokat (kombinatorika nevén osztályokat) akarunk mindenféle módon képezni (és minden elem csak egyszer fordul elő). Ezt úgy hívjuk, hogy n elem kad osztályú ismétlés nélküli kombinációja. Az ismétlés nélküli kombináció képlete:

, =

!

! ∙  !

 vagy binomiális együtthatókkal kifejezve:  

Az ismétléses kombinációt alkalmazzuk, amikor adott n elemekből k elemszámú multihalmazokat képzünk, ahol adva van legalább 1 multiplikált elem. Az ismétléses kombináció képlete:

Variáció

 , = 

+ −  - binominális együtthatóval kifejezve.

Ismétlés nélküli valamint ismétléses variáció során egyaránt úgy járunk el, hogy osztályok szerint permutálunk. Vagyis eszerint azon túl, hogy n elem k-ad osztályú kombinációit állítjuk fel, permutálnunk is kell azokat. Az előző kombinatorikai operációkhoz hasonlóan változik a variáció aszerint, hogy ismétléses vagy ismétlés nélküli: amennyiben legalább 1 elem multiplikált, akkor ismétléses-, ellenben ismétlés nélküli variációról van szó. Az ismétlés nélküli variáció képlete: Az ismétléses variáció képlete:

2010. december 28.

, =

 , = 

!

 !

2/16

Hegedűs Ádám Imre (KEB7GY)

Diszkrét matek I.

Vizsga-jegyzet

BINOMIÁLIS TÉTEL A binomiális tétel egy matematikai (algebrai) tétel, mely a következő képletben foglalható össze: %

% # + $ = &   #%' $' ' %

'()

Részletesebben (szummajel használata nélkül):

    * + +  =   * +) +   * + + … +   * + +   *) + ) − 

ahol n természetes szám (n ∈ ℕ), a,b pedig valós vagy komplex számok, vagy általánosabban, egy kommutatív félgyűrű elemei; továbbá a képletben szereplő ún. binomiális együtthatók a  ! következőképp számolhatóak ki:   = ! ∙ − ! ; n! pedig az n faktoriálisát jelenti.

Az általános tag képlete ( k+1-edig elem! ):

 . / =   * +

Példa: Számítsuk ki az E=(x2+01)10 kifejezés balról hetedik tagját: 10 10 23 = 4 5 6  7 01 8 = 4 5 6  1  = 2106  1  6 4

RELÁCIÓK, GRÁFOK

Bináris reláció fogalma: két halmaz elemei közötti megfeleltetést értünk – amit úgynevezett gráffal szokás szemléltetni Halmazelméleti megközelítésben a relációkat, pontosabban gráfjaikat rendezett elempárokkal adjuk meg: A = { a, b, c, … } /*alaphalmaz*/ R(g) = {(a,a), (a,b), (a,c), … } /* ezek szerint tehát AxA részhalmazait képezik*/ Absztrakt megadási mód: R = (A, B, R(g)), R(g) ᴄ AxA Relációk egyenlősége: Akkor és csak akkor egyenlő két reláció, ha R1 = (A, B, R1(g)) R2 = (C, D, R2(g))

;=< A teljesülnek! ==> : @

@

? = ?

Homogén bináris reláció: Ha A = B halmaz egybeesik, akkor homogén bináris relációról beszélünk. R = (A, A, R(g)) jelölést

2010. december 28.




R = (A, R) jelölés váltja fel

3/16

Hegedűs Ádám Imre (KEB7GY)

Vizsga-jegyzet

Diszkrét matek I.

Relációk tulajdonságai: 1. reflexív, ha aRa minden a B A-ra a•

2. szimmetrikus, ha aRb ↔ bRa a•

•b

3. antiszimmetrikus, ha ( aRb és bRa) → a = b

(a két halmaz ugyan az)

4. tranzitív, ha (aRb és bRc) → aRc a•

•b

c• Ekvivalencia reláció: Feltétele: 1. reflexív 2. szimmetrikus 3. tranzitív Részbenrendezés: Feltétele: 1. reflexív 2. antiszimmetrikus 3. tranzitív Példák: 1. xRy (testvérek) – E = { emberek } – x, y ∈ E a. szimmetrikus 2. x osztja y-t – x, y ∈ N a. reflexív b. antiszimmetrikus részbenrendezés c. tranzitív 3. x ismeri y-t a. reflexív ekvivalencia reláció b. szimmetrikus c. tranzitív 4. (R, ≤) (== x ≤ y) a. reflexív részbenrendezés b. antiszimmetrikus c. tranzitív 5. (C, ~) – x, y ∈ C-re – (x ~ y == | x | = | y | ) a. reflexív ekvivalencia reláció b. szimmetrikus c. tranzitív

2010. december 28.

reláció

4/16

Hegedűs Ádám Imre (KEB7GY)

Diszkrét matek I.

Vizsga-jegyzet

Bináris relációk szorzata: Ha R = A x B és Q = B x C két bináris reláció, akkor ezek R ° Q alatt az A és C halmaz közötti relációt értjük, amit a következőképpen definiálunk: R ° Q = A x C A•

•B

R

R°Q

Q C•

Általában R ° Q ≠ Q ° R. A relációk szorzása asszociatív: ( A ° B ) ° C = A ° ( B ° C ) Bináris reláció inverze: aR-1b = bRa Homogén bináris reláció hatványozása: R1 = R R2 = R ° R Rn = R ° R ° R ° … ° R n-szer Relációs metszet: Ha R egy homogén bináris reláció az A halmazon (azaz R ᴄ A x A), akkor egy a ∈ A elem esetén az R[a] = { x ∈ A | aRx } halmazt az a elem R-re vonatkozó relációs metszetének nevezzük. Észrevehetjük, hogy • aRb → b ∈ R[a] • Ha R reflexív, akkor aRa ↔ a ∈ R[a] • Ha R egy ekvivalencia reláció, akkor R[a] neve az az a ∈ A egy ekvivalencia osztálya (R-re nézve) o Ez az elnevezés a következő tényből ered: Ha R = A x A egy ekvivalencia reláció, és a ∈ A-nak, akkor minden x, y ∈ R[a]-ra xRy (és yRx) teljesül. Biz.:

x, y ∈ R[a]
aRx és aRy
xRa, aRy → xRy → yRx
Minden x ∈ R[a]-ra szimmetria R[x]=[a] tranzitív

FÜGGVÉNYEK (összetevés, iterált, bijektivitás, invertálás)

A függvényeket olyan bináris F = A x B relációnak tekintjük, ahol minden x ∈ A-ra teljesül az F(x) = { y ∈ B | xFy } relációs metszet pontosan egy elemű.

Példa:

1∈A F[1] = { a }
F(1) = a

(jelölés szerint különböztetjük meg a relációs metszettől)

Két függvény (F1 : A → B és F2: C → D) relációs értelmezésből kiindulva akkor egyenlő, ha • A = C és B = D • F1(x) = F2(x), minden x ∈ A-ra 2010. december 28.

5/16

Hegedűs Ádám Imre (KEB7GY)

Vizsga-jegyzet

Diszkrét matek I.

Függvények összetevése alatt az F ° G relációs szorzatot értjük: Példa:

F = C és G = √C

F ° G = G ( F ) → √C 

G ° F = F ( G ) → √C = x

Ebből látható, hogy általában F ° G ≠ G ° F (Vegyük csak az x-et negatív számnak!)

Egy A ≠ ∅ halmaz egyetén az 1A: A → A, 1A(x) = x függvényt identikus függvénynek nevezünk. Példa:

n-szer

F( 1A ) = 1A( F(x) ) = F(x)

Függvény iteráltja: Egy F: A → A függvény esetén definiálhatjuk Fn: A → A, Fn=F ° F ° … ° F függvényt és F1 = F-t. Az F1, F2, … Fn függvények F függvény iteráltjai. Rekurzív képlet: Fn+1 = Fn ° F Tulajdonság: Fn ° Fm = Fn+m Függvények invertálása: A függvények invertálása egyenértékű a relációk inverz-képzéséhez. Felcseréljük az értelmezési tartományát és az értékkészletét, és ugyanakkor az x és F(x) (=y) szerepét. Példa: F(x) = y = ax + b




F-1(x) = F = *G + + =

G+ *

Bijektív függvény: Az F: A → B függvényt bijektívnek nevezünk, ha minden y ∈ B-re egy és csakis egy olyan x ∈ A létezik, ami F(x)=y-ra teljesül. (Minden y ∈ B pontnak egy „őse” van A-ban, tehát egyértelműen invertálható!) Tehát, csak bijektív függvény invertálható. Ez sokszor csak az értelmezési tartomány leszűkítésével lehetséges. Példa:

F: R → R, F(x) = x2 ⇒ F: R+ → R+, F(x) = x2

PERMUTÁCIÓK

Az A halmaz permutációján az φ: A → A bijektív leképzéseket értjük. Példa:

 I φ:   = {(1,3), (2,1), (3,2)} I 

Tetszőleges n pozitív egészre az {1, 2, …, n} halmazt összes permutációinak halmazát Sn-nek nevezzük. Nem minden leképzés permutáció! Példa:  I φ:   = {(1,3), (2,1), (3,3)} I I

2010. december 28.

// Nem bijektív! (nem egy-egy értelmű)

6/16

Hegedűs Ádám Imre (KEB7GY)

Vizsga-jegyzet

Diszkrét matek I.

Két permutáció összetevése azonosan működik, mint a relációk összetevése: Példa:  I  I φ°ѱ= °  = {(1,3), (2,2), (3,1)} I   I Rekurzív képlet: φ n+1 = φ n ° φ Tulajdonság: φ n ° φ m = φ n+m

Identikus permutáció:  I :  = {(1,1), (2,2), (3,3)}  I

ε

// Önmagába képez le

Permutációk periodicitása:  I φ:   = {(1,3), (2,1), (3,2)} I 

Látható, hogy φ periodicitása 3, mert ekkor válik identikus permutációvá.

Példa: • • • •

φ= I

 I   φ2 = φ ° φ =   2 3 φ °φ=φ: 3 4 φ °φ=φ: I

 I   

I  I  I I  

FÉLCSOPORT, CSOPORT Félcsoport: Azt az algebrai struktúrát nevezzük félcsoportnak, amelyekben a művelet • nem vezet ki a alaphalmazból, tehát bináris belső művelet • asszociatív (x*y)*z=x*(y*z) Példa: (N, +) (P, +) (P, · ) (R\{0}, ·) (P(A), ∪)

// természetes számok (1,2,3, …) összeadása // páros egész számok összege // páros egész számok szorzata // valós számok szorzata // polinomok uniója

(P, +) (R\{0}, ·)

// páros egész számok összege // valós számok szorzata

Csoport: Azt az algebrai struktúrát nevezzük csoportnak, amelyekben • a művelet asszociatív = félcsoport • van semleges elem • minden elemnek inverze Példa:

2010. december 28.

KOMMUTATÍV CSOPORT 2+6=6+2 5,3 · 2,01 = 2,01 · 5,3

7/16

Hegedűs Ádám Imre (KEB7GY)

Diszkrét matek I.

Vizsga-jegyzet

GYŰRŰ Azt a két bináris műveletet tartalmazó algebrai struktúrát (A, +, · ) nevezzük gyűrűnek, amikben teljesülnek az alábbi axiómák: • (A, +) kommutatív csoport • (A, · ) félcsoport a·(b·c)=(a·b)·c • „+” és „·” disztributív a ( b + c ) = ab + ac ( b + c ) a = ba + ca Például gyűrűk: (Z, +, · ), (R, +, · ), (C, +, · ), (R[x], +, · ), (Mn,n (R), +, · ) Példa: (Z, +, · ) 1. Tudjuk, hogy (Z, +) kommutatív csoport 2. Tudjuk, hogy (Z, · ) félcsoport 3. Ismert, hogy Z-n teljesül, hogy a ( b + c ) = ab + ac és ( b +c ) a = ba + ca → disztributív 4. Tehát (Z, +, · ) egy gyűrű

// ugyanígy bizonyítjuk (R, +, · ) és (C, +, · )-t is

TEST Az (A, +, · ) gyűrűt testnek nevezzük, ha a gyűrű axiómáin kívül a következő axiómák is teljesülnek: • Létezik a gyűrűnek egységeleme

•

K ∈ A, λ · a = a · λ = a

Minden a ∈ A\{0}-ra létezik a-1 ∈ A úgy, hogy a · a-1 = a-1 · a = 1

Például testek: (R, +, · ), (C, +, · )

// nem test, csak gyűrű: (Z, +, · )

Példa: (R, +, · ) 1. Tudjuk, hogy (R, +, · ) egy gyűrű 2. Az 1 szám a szorzás semleges eleme Ha a ∈ R és a ≠ 0, akkor létezik * ∙ * = 1 → létezik a-1 = * , minden a ∈ R 3. Tehát (R, +, · ) egy test, és mivel a „·” és az „+” is kommutatív, így (R, +, · ) egy kommutatív test

2010. december 28.

8/16

Hegedűs Ádám Imre (KEB7GY)

Vizsga-jegyzet

Diszkrét matek I.

LINEÁRIS TÉR Legyen (V, +) egy kommutatív csoport – elemeit nevezzük „vektoroknak” – és (K, +, · ) egy kommutatív test – elemeit nevezzük „skalároknak”. A (V, + ,K) „hármast” lineáris térnek nevezzük, ha • értelmezett a „vektoroknak” és a „skalárokkal” való szorzása, vagyis egy K x V → V „külső” művelet (függvény), ahol teljesül  , LM → ∙ LM ∈  N A (V, + ,K)-t vektortérnek nevezzük, ha a lineáris tér axiómáin kívül teljesülnek a következő axiómák: • k · ( l · LM ) = ( k · l ) · LM minden k, l ∈ K számra és • k · ( LM1 + LM2 ) = k · LM1 + k · LM2 LM1 , LM2 ∈ V-re • ( k + l) · LM = k · LM + l · LM • 1k · LM = LM · 1k = LM Példa:

// háromdimenziós térvektorok skalárral való szorzásra nézve (V3, +, R) 1. Tudjuk, hogy (V3, +, R) egy kommutatív csoport, és hogy (R, +, · ) egy kommutatív test 2. Nyilvánvaló az tér-axiómák teljesülése, hiszen a V3 szolgált modellül 3. Tehát (V3, +, R) egy lineáris tér Emlékeztető vektorokhoz: FM = ( x1, x2, … , xn ) és GM = ( y1, y2, … , yn ) és λ ∈ R esetén FM + GM = ( x1 + y1, x2 + y2, … , xn + yn ) λ · FM = ( λ · x1, λ · x2, … , λ · xn )

( Mn,n (R), +, R ) // n x n-es mátrix skalárral való szorzására nézve 1. Tudjuk, hogy (Mn,n (R), +) egy kommutatív csoport, és hogy (R, +, · ) egy kommutatív test 2. Skalárral való szorzás: λ ∈ R # , # λ · P , … #S,

# , … #, … … #Q,R #S, …

K# , # ,% #,% K# T = P , … … #S,% K#S,

K# , … … K#, K#Q,R … K#S, …

K# ,% K#,% T … K#S,%

Tehát látható, hogy teljesülnek az axiómák, hiszen az λ-val való szorzás visszavezethető a mátrix elemeinek való szorzására: k · ( l · ai,j ) =( k · l ) · ai,j 3. Tehát ( Mn,n (R), +, R ) egy lineáris tér Vektortér alterei: Legyen (V, + ,K) egy lineáris tér és U ᴄ V, U ≠ Ø.

Az (U, + ,K) „hármast” a (V, + ,K) tér egy alterének nevezzük, ha minden u1 , u2 ∈ U-ra és λ1 , λ2 ∈ K-ra teljesül, hogy λ1 · u1 + λ2 · u2 ∈ U.

Tehát az altéren belüli művelet nem vezet ki az altérből, így maga is egy „teret” alkot V valódi részhalmazaként.

2010. december 28.

9/16

Hegedűs Ádám Imre (KEB7GY)

Vizsga-jegyzet

Diszkrét matek I.

POLINOMOK Polinomok osztása polinommal: Q(x) osztja P(x)-et, ha P(x) = Q(x) · H(x)

// H(x)osztási maradék

x – a | P(x) ↔ P(a) = 0 Példa: x – 2 | x2 – 4

// P(2) = 22 – 4 = 4 – 4 = 0

Legyen P(x) = a0xn + a1xn-1 + … an-1x + an komplex együtthatós polinom. • Ha n > 0 (ha nem konstans), akkor P(x)-nek pontosan n gyöke van. Gyöktényezős alak: a0(x-x1) (x-x2)… (x-xn)

// csak valós gyökök esetén

Példa: x2 – 4 = 1 · (x – 2)(x + 2) Zh.: x1 = 2 és x2 = -2 • •

Ha egy P(x) polinomnak van nem valós gyökei, akkor azok mindig párosával fordulnak elő. Minden (komplex együtthatós) polinom felbontható konstans, elsőfokú és negatív diszkriminánsú valós együtthatós másodfokú polinomok szorzatára. Gyöktényezős alak: a0(x-x1) (x-x2)… (x-xk)pk+1(x)…pn(x) Példa:

// valós és komplex gyököknél

x4 – 16 = 1 · (x – 2)(x + 2)(x2 + 4) Zh.: x1 = 2, x2 = -2, x3 = √ + √, x4 = √ − √

MÁTRIXOK

Mátrix szorzása skalárral: # , # , … # #, … λ · P , … … #Q,R # #S, S, … Mátrix szorzása mátrixszal: 4 1 2 3 U5W = 1 ∙ 6

K# , # ,% #,% K# T = P , … … #S,% K#S,

K# , … … K#, K# Q,R … K#S, …

4 + 2 ∙ 5 + 3 ∙ 6 = 32

K# ,% K#,% T … K#S,%

//csak azonos sor és oszlopszámú mátrixokat lehet összeszorozni.

Mátrix rangja: a mátrix rangja alatt azt értjük, hogy hány független sor, illetve oszlopot tudunk kiválasztani a mátrixunkban. Független az a sor, illetve oszlop, ami nem a többi sor, illetve oszlop egy lineáris kombinációja. Példa:

− Y=Z X −

2010. december 28.

 I ) ) −  \ − −I )  −[

−  I ) −  I ) Y) = 3 = Z ) − \ = U ) − W = rang(X − −I +2 − −I ) ) ) )

10/16

Hegedűs Ádám Imre (KEB7GY)

Vizsga-jegyzet

Diszkrét matek I.

Mátrix inverze: Y ≠ ) - szükséges feltétel: det(X -1 Y -1 Y Y Y - Ha X ∙ X = X ∙ X := En Y = U) X

// En = egységmátrix

) )W ) −

1. Kiszámítjuk a mátrix determinánsát

)

Y = ^) det(X

)

) ^= ∙ _ ) −

) ) _− )∙ _ −

) ) _+ ∙ _ −

Y transzponáltját (sorokat és oszlopokat felcseréljük) 2. Vesszük az X Y T = U) X

_ = − ≠ ) → Van inverze )

) )W ) −

Y T-ből kiindulva kiszámoljuk a mátrix andjungáltját (minden elem helyére a sorának és az 3. X oszlopának törlésével visszamaradt elemek determinánsát írjuk – sakktáblaszabályt betartjuk) ) ) ) ) +_ _ −_ _ +_ _ ) − − ) − ) − j m Y * = − _) _ + _ _ − _ )_ = U ) − ) W X i ) − − )l − ) ) ) −_ _ +_ _k h + _ )_ ) ) )

Y )-val. Y T –t det(X 4. Végül elosztjuk az X Y -1 = X

 )  U )  ) W  ) Y

nop;

5. Ellenőrzés:

=



Y=X Y ∙X Y -1 = P) Y -1 ∙ X X 

VEKTOROK

qqq nop;

) − ) −  ∙ U ) − ) W = P) − ) ) 

)  ) T ∙ U) ) −



) ) ) W = U) ) − ) )



)T − ) )W

* ∙ + = |*||+| st u

// Merőlegesség esetén a ∙ $ = 0 // a ∙ $ értéke egy skaláris szám Derékszöget bezáró tengelyeket tartalmazó koordinátarendszerben: // Például: R3

Skaláris szorzat:



* ∙ + = & * + = * + + * + + … + * + (

2010. december 28.

11/16

Hegedűs Ádám Imre (KEB7GY)

* × + = |*||+|  u

Vektoriális szorzat:

Vizsga-jegyzet

Diszkrét matek I.

x̅ * × + = w* +

Kiszámítása determinánssal:

Vegyes szorzat: abc = ( a x b ) ∙ c

z̅ * +

// Párhuzamosság esetén a x b = 0 // a x b értéke egy újabb vektor

̅ *I w, ahol +I

* *+s = }~ *, +, s = ^* *I

Kiszámítása determinánssal:

Két vektor által bezárt szög:

x̅, z̅, és ̅ az egységvektorok.

+ + +I

s s ^ sI

€ = *sst  |#|∙|+|  #∙+

Ha tudjuk a skaláris szorzatukat:

Lineáris függetlenség: Egy vektor lineárisan független, ha nem hozható létre a tér többi lineárisan független vektorainak segítségével. Példa:

‚M = 1,0,0

ƒ„ = 0,1,0

…M = 0,0,1

A háromdimenziós tér egységvektorai

LINEÁRIS EGYENLETRENDSZER Cramer-szabály: a1,1x1 + a1,2x2 + … + a1,nxn = b1 a2,1x1 + a2,2x2 + … + a2,nxn = b2 … an,1x1 + an,2x2 + … + an,nxn = bn

* , *, Dn,n = † … *,



* , … *, … … *,‡ *, …

// Csak akkor használtató a Cramer-szabály, ha det( Dn,n ) ≠ 0 // Csak n x n-es determinánsra alkalmazható

* , + *, + †; P T … |…| *, 

Módszer lényege: Behelyettesítjük a fődeterminánsba a keresett xi-edik oszlopába a szabad tagok oszlopát, és az így létrejött determináns determinánsa adja meg az xi értékét.

+ + ˆF = †  … +

* , … *, … … *,‡ *, …

2010. december 28.

* , * , *, * †; ˆF = † , … … *, *,

+ … + … … *,‡ + …

* , * , *, * †; … ; ˆF = † , … … * *, ,

* , … *, … … *,‡ *, …

+ + †; … + 12/16

Hegedűs Ádám Imre (KEB7GY) Gauss-módszer: a1,1x1 + a1,2x2 + … + a1,nxn = b1 a2,1x1 + a2,2x2 + … + a2,nxn = b2 … an,1x1 + an,2x2 + … + an,nxn = bn

* , * , * *, P , … … *, *,

Vizsga-jegyzet

Diszkrét matek I.

// Csak akkor használtató a Gauss-módszer, Y)≠0 ha det( ; // Csak n x n-es determinánsra alkalmazható



… * , + … * + , *,‡ … ‰  AT |…| … *, 

Y ) = rang ( Y // Ha rang( ; ;B ) → létezik megoldás

Y) együttható mátrix ( X

YB ) kibővített mátrix ( X

Módszer lényege: Vesszük az Y ;B (kibővített) mátrix determinánsát. Felső háromszög determináns hozunk létre • A főátló alá nullákat hozunk létre úgy, hogy az épp kinullázandó elem fölötti sor valahányszorosát hozzáadjuk a kinullázandó sorhoz úgy, hogy a kinullázandó elem nulla legyen. Tulajdonságok determinánsokra: o két sor felcserélhető, mert az egyenletek sorrendje nem befolyásolja a megoldásokat o két oszlop felcserélhető, mert a különböző fokszámú ismeretlenek sorrendje nem befolyásolja a megoldásokat, de figyelni kell arra, hogy a végeredménykor a már felcserélt oszlopok rendje szerint állnak elő a megoldások •

A háromszög-determináns formában alulról behelyettesítésével az x1, x2, … , xn előáll.

Kompatibilitás

indulva,

és

az

ismeretlenek

// n = ismeretlenek száma kompatibilis

Y ) = rang ( Y határozott, ha rang( X XB ) = n // egy megoldás

Y ) = rang ( Y határozatlan, ha rang( X XB ) < n // végtelen (paraméteres) megoldás

Y ) ≠ rang ( Y inkompatibilis, ha rang( X XB ) // nincs megoldás

2010. december 28.

13/16

Hegedűs Ádám Imre (KEB7GY)

Diszkrét matek I.

Vizsga-jegyzet

LINEÁRIS KOMBINÁCIÓ Lineáris kombináció: Ha Š , Š , … , Š% ∈ ‹ és λ1, λ2, … , λn ∈ K tetszőleges, akkor a λ1 ∙ Š + λ2 ∙ Š + … + λn ∙ Š% összeget a Š , Š , … , Š% vektorok egy lineáris kombinációjának nevezzük.

Lineárisan független az a vektor, amely nem állítható össze a vektortér többi vektorainak egy lineáris kombinációjával.

GENERÁTOR-RENDSZER Fogalma: Azt mondjuk, hogy a L , L , … , L (lineárisan független vektorokból álló) vektorrendszer a (V, +, K) vektortér egy generátorrendszere, ha minden Š ∈ V vektor előállítható úgy, mint a L , L , … , L valamely lineáris kombinációja, azaz λ1 ∙ L + λ2 ∙ L + … + λn ∙ L = L , ahol λ1, λ2, … , λn ∈ K A (V3, +, R)-ben az x̅, z̅, ̅ egységvektorok egy generátor-rendszert alkotnak, és segítségükkel bármely vektor felírható e vektor egy lineáris kombinációjaként.

Példa:

BÁZIS

A { L , L , … , L } c V vektorrendszer a V lineáris tér bázisának nevezzük, ha teljesülnek az alábbi axiómák egyszerre: • generátor-rendszere V-nek • lineárisan független vektorrendszer Példa:

(V3, +, R)-nek { x̅, z̅, ̅ } bázisa 1. Láttuk, hogy generátorrendszer 2. Mivel x̅, z̅, ̅ nincsenek egy síkban, ezért lineárisan függetlenek

x̅ ∙ z̅ = ( 1,0,0) ∙ (0,1,0) = 1 ∙ 0 + 0 ∙ 1 + 0 ∙ 0 = 0 + 0 + 0 = 0 → merőlegesek egymásra z̅ ∙ ̅ = ( 0,1,0) ∙ (0,0,1) = 0 ∙ 0 + 1 ∙ 0 + 0 ∙ 1 = 0 + 0 + 0 = 0 → merőlegesek egymásra

̅ ∙ x̅ = ( 0,0,1) ∙ (1,0,0) = 0 ∙ 1 + 0 ∙ 0 + 1 ∙ 0 = 0 + 0 + 0 = 0 → merőlegesek egymásra

Mivel x̅, z̅, ̅ vektorok páronként merőlegesek egymásra, így egyikük sem állítható elő a másik kettő egy lineáris kombinációjával.

3. Tehát (V3, +, R)-nek { x̅, z̅, ̅ } igenis bázisa

LINEÁRIS TRANSZFORMÁCIÓ

Legyenek (V, +, K) és (W, +, K) lineáris terek ugyanazon (K, +, ∙ ) test felett. (általában R felett) Az L: V → W függvény lineáris transzformációjának nevezzük, ha minden L , L ∈  és λ1, λ2 ∈ K-ra teljesül L( λ1 ∙ L + λ2 ∙ L = λ1 ∙ Œ L + λ2 ∙ Œ L

Tulajdonság: 1. L( L + L = Œ L + Œ L

2. L( λ ∙ L = λ ∙ Œ L

3. L( )L = ) 2010. december 28.

14/16

Hegedűs Ádám Imre (KEB7GY)

Vizsga-jegyzet

Diszkrét matek I.

4. A lineáris transzformációk összetevése is lineáris transzformáció Példa: Legyenek (U, +, K), (V, +, K) és (W, +, K) ugyanazon (K, +, ∙ ) test felett, és L1: U → V lineáris transzformációk L2: V → W Legyen L , L ∈  és λ1, λ2 ∈ K tetszőleges

Tekintsük L1 ° L2: U → W összetett függvényt

L1 ° L2 ( λ1 ∙ Ž + λ2 ∙ Ž ) = L2 ( L1 ( λ1 ∙ Ž + λ2 ∙ Ž ) = = L2 ( λ1 ∙ Œ  Ž ) + L2 ( λ2 ∙ Œ  Ž ) = λ1 ∙ L2 ( L1 ( Ž ) ) + λ2 ∙ L2 ( L1( Ž ) ) = = λ1 ∙ L2 ° L1 ( Ž ) + λ2 ∙ L2 ° L1 ( Ž )  Tehát L1 ° L2 teljesíti a lineáris transzformáció axiómáit, így maga is egy lineáris transzformáció Lineáris transzformáció mátrixos alakja: (V, +, K) és (W, +, K) n, illetve m dimenziós vektorterek és L: V → W egy lineáris transzformáció. V-nek legyen B1 = { o , o , … , o% } egy bázisa W-nek legyen B2 = {  ,  , … , S } egy bázisa

Ekkor minden x ∈ V-re és y ∈ W igaz, hogy F = x1 ∙ o + x2 ∙ o + … + xn ∙ o% és G = y1 ∙  + y2 ∙   + … + ym ∙  S Œ

G →  G , G , … , G‘ =

Œ

F →  F , F , … , F =

F → G = Œ  F ⇒  F , F , … , F  →  G , G , … , G‘ 

Tudjuk, hogy G = L( F ) = L( x1 ∙ o + x2 ∙ o + … + xn ∙ o% ) = = x1 ∙ L( o ) + x2 ∙ L( o ) + … + xn ∙ L( o% ) W

W

W

G =  Œ F = = x1 ∙ Œ o = + x2 ∙ Œ o = + … + xn ∙ Œ o% = 

Most felírjuk a B2 bázisban az L( o ), L( o ), … , L( o% ) ∈ W vektorokat L( o ) = a1,1 ∙  + a2,1 ∙  + … + am,1 ∙ % → ’ * , , *, , … , *‘, “=



L( o ) = a1,2 ∙  + a2,2 ∙  + … + am,2 ∙ % →  * , , *, , … , *‘, = … L( o% ) = a1,n ∙  + a2,n ∙  + … + am,n ∙ % →  * , , *, , … , *‘, = 2010. december 28.

15/16

Hegedűs Ádám Imre (KEB7GY) Ezt egy mátrixba írjuk:

m

* , * , * *, P , … … *‘, *‘,

n

Y ;

Diszkrét matek I. 6 … * , … * 6 , *,‡ … T P| … |T … *‘, 6”

Y ∙ F Tehát G = Œ F  = X 

Vizsga-jegyzet

C=

Y egy olyan n x m-es mátrix, aminek oszlopvektorai az Œ o = , Œ o = , … , Œ o% = Az ;    koordinátavektorok, azaz a B1 bázis o , o , … , o% vektorainak az L( o ), L( o ), … , L( o% ) képei a B2 bázisban felírva. Példa:

T: V3 → V3, T( L = a L vektor „tükörképe” az XY síkra.

S = B1 = B2 = { x̅, z̅, ̅ }

L( x̅ = x̅ =  , ), )

L( z̅ = z̅ = ), , )

L( ̅ = - ̅ = ), ), −

Y = U) ; )

) ) )W ) −

C = ( x1, x2, x3 )

) T ( x1, x2, x3 )S = U) ) )

// Tükörképe a „Z-tengelyre”

F ) ) W ∙ UF  W FI • −

Y ∙ F , akkor az X Y mátrix Ha L: V → W egy bijektív lineáris transzformáció, é– Œ F  = X -1  

 Y ∙ F invertálható, és L : W → V inverz-transzformáció mátrixos alakja: Œ F  = X 

Y mátrix inverzét képezni. Így kapjuk az inverz lineáris Inverz képzése mátrixos alakban: az X transzformáció mátrixos alakját.

Mátrixos alak felhasználása: Igazolható, hogy a sík (R2) vektorainak origó körüli —-szöggel való elforgatása egy lineáris transzformáció (R2→ R2). Ennek mátrixos alakja az S = { x̅, z̅ } bázisra nézve: st u −  u F  G L(x,y) =   u st u

2010. december 28.

16/16