BSz1 Jegyzet

9. Tétel:

Determináns definíciója, alaptulajdonságai, kiszámítása.

9.1. Permutációk

A determináns fogalmának felépítése a permutációk megértésével kezdődik. A permutáció lényegében rögzített számú elem összes lehetséges sorrendbe rendezését jelenti.

2.4.1. Definíció (Permutáció):

Permutáció alatt egy olyan $n$ tagú számsorozatot értünk, amely az $1, 2, \dots, n$ számok mindegyikét pontosan egyszer tartalmazza valamilyen $n \ge 1$ egész esetén.

A permutáció tehát az $1, 2, \dots, n$ számok egy „összekeverése”, valamilyen sorrendben való felsorolása.

Jelölésrendszer

A permutációkat általában görög betűkkel (pl. $\pi$, $\sigma$) jelöljük. Egy $\pi$ permutációban az $i$-edik helyen álló számot $\pi_i$ jelöli.

A determináns kapcsolata

Ez a fogalom a determináns definíciójában játszik kulcsszerepet, mivel a mátrix elemeiből képzett szorzatok előjelét a sorindexekhez tartozó oszlopindex-permutációk tulajdonságai határozzák meg.

Példafeladat: Permutáció azonosítása

Feladat:

Adott a $\pi = (5, 3, 1, 8, 4, 2, 6, 7)$ permutáció $n = 8$ esetén.
Mely értékek tartoznak a $\pi_1$, $\pi_4$ és $\pi_7$ helyekhez?

Első elem ($\pi_1$):

5

Negyedik elem ($\pi_4$):

8

Hetedik elem ($\pi_7$):

6

Megfigyelhető, hogy a sorozatban minden egész szám 1-től 8-ig pontosan egyszer fordul elő.

9.2. Permutációk inverziószáma

A permutáció elemeinek sorrendje alapján meghatározhatjuk, hogy a számok mennyire „keveredtek össze” az eredeti $1, 2, \dots, n$ sorrendhez képest. Ezt az eltérést az inverziók számával mérjük.

2.4.1. Definíció (Inverzió és inverziószám):

Azt mondjuk, hogy a $\pi = (\pi_1, \pi_2, \dots, \pi_n)$ permutációban a $\pi_i$ és $\pi_j$ tagok inverzióban állnak, ha $i < j$, de $\pi_i> \pi_j$.

A $\pi$ permutáció inverziószáma az összes inverzióban álló számpár száma.

Ennek jele: $I(\pi)$

Kiszámítási módszer

A gyakorlatban az inverziószámot legkönnyebben úgy számolhatjuk össze, ha minden tagnál megnézzük, hány nála kisebb tag következik utána a sorozatban, és ezeket az értékeket összeadjuk.

Példafeladat: Inverziószám meghatározása

Permutáció:

$\pi = (5, 3, 1, 8, 4, 2, 6, 7)$

A számolás menete:

  • 5 után nála kisebbek: 3, 1, 4, 2 $\rightarrow$ 4 db
  • 3 után nála kisebbek: 1, 2 $\rightarrow$ 2 db
  • 1 után nála kisebbek: - $\rightarrow$ 0 db
  • 8 után nála kisebbek: 4, 2, 6, 7 $\rightarrow$ 4 db
  • 4 után nála kisebbek: 2 $\rightarrow$ 1 db
  • 2 után nála kisebbek: - $\rightarrow$ 0 db
  • 6 után nála kisebbek: - $\rightarrow$ 0 db

Összesítés

$I(\pi) = 4 + 2 + 0 + 4 + 1 + 0 + 0 = \mathbf{11}$

Ez a permutáció páratlan inverziószámú, ami meghatározza majd a hozzá tartozó tag előjelét a determinánsban.

9.3. Bástyaelhelyezések és a kiválasztás szabálya

A determináns bonyolult összegzési képlete mögött egy egyszerű sakktábla-logika húzódik meg. Ahhoz, hogy megértsük, mely elemeket szorozzuk össze a mátrixból, hívjuk segítségül a bástyaelhelyezési feladatot.

2.4.2. Feladat (Bástyaelhelyezés):

Hányféleképpen helyezhető el a sakktáblán 8 bástya úgy, hogy semelyik kettő ne üsse egymást?

Szabály: Két bástya akkor üti egymást, ha egy sorban vagy egy oszlopban vannak.

Következtetés: Úgy kell elhelyezni a bástyákat, hogy minden sorban és minden oszlopban pontosan 1 legyen.

Kapcsolat a mátrixokkal

Ha a sakktáblát egy $(n \times n)$-es mátrixnak tekintjük, a determináns minden egyes tagja egy olyan szorzat lesz, amelyben az elemeket „bástyaelhelyezés-szerűen” válogattuk össze.

Ez azt jelenti, hogy a mátrixból úgy választunk ki $n$ darab elemet, hogy semelyik kettő ne legyen azonos sorban vagy oszlopban.

♜
♜
♜
♜
♜
♜
♜
♜
♜
♜
♜
♜
♜
♜
♜
♜

2.4. ábra: Példák érvényes elhelyezésekre

A bástyák és a permutációk

Miért tanultunk permutációkat az előbb? Mert minden ilyen bástyaelhelyezés egyértelműen megfeleltethető egy $\pi$ permutációnak:

  • A bástya sorindexe legyen $i$ ($i=1, \dots, n$).
  • A bástya oszlopindexe legyen $\pi_i$ (a permutáció $i$-edik eleme).
„Mivel minden sorban ($i$) és minden oszlopban ($\pi_i$) pontosan egy bástya áll, az oszlopindexek sorozata ($\pi_1, \pi_2, \dots, \pi_n$) az $1, 2, \dots, n$ számok egy permutációja lesz.”

Ez a logikai lépés vezet el minket a determináns végleges definíciójához.

9.4. A determináns definíciója

Most már minden eszközünk megvan ahhoz, hogy definiáljuk egy négyzetes mátrix determinánsát. A definíció alapja, hogy összegezzük az összes lehetséges bástyaelhelyezéshez tartozó szorzatot, és minden szorzatot ellássunk a megfelelő előjellel.

2.4.4. Definíció (Determináns):

Legyen $A$ egy $(n \times n)$-es mátrix. Az $A$ mátrix determinánsán az alábbi összeget értjük:

$$\det(A) = \sum_{\pi} (-1)^{I(\pi)} \cdot a_{1,\pi_1} \cdot a_{2,\pi_2} \cdot \dots \cdot a_{n,\pi_n}$$

Ahol az összegzés az $1, 2, \dots, n$ számok összes lehetséges $\pi$ permutációjára kiterjed ($n!$ darab tag), és $I(\pi)$ a $\pi$ permutáció inverziószámát jelöli.

A képlet összetevői

Szorzatok: Minden tag egy bástyaelhelyezésnek felel meg: minden sorból és minden oszlopból pontosan egy elem szerepel benne.
Előjelek: Ha a permutáció páros ($I(\pi)$ páros), a szorzat pozitív előjellel szerepel; ha páratlan, akkor negatívval.

Példafeladat: $2 \times 2$-es determináns levezetése

Feladat:

Alkalmazza a definíciót az $A = \begin{pmatrix} a_{1,1} & a_{1,2} \\ a_{2,1} & a_{2,2} \end{pmatrix}$ mátrixra!

1. Permutációk kigyűjtése ($n=2$)

  • $\pi^{(1)} = (1, 2) \implies I(\pi^{(1)}) = 0$ (páros)
  • $\pi^{(2)} = (2, 1) \implies I(\pi^{(2)}) = 1$ (páratlan)

2. A tagok felírása

  • Első tag: $(-1)^0 \cdot a_{1,1} a_{2,2} = + a_{1,1} a_{2,2}$
  • Második tag: $(-1)^1 \cdot a_{1,2} a_{2,1} = - a_{1,2} a_{2,1}$

Végeredmény

$\det(A) = a_{1,1} a_{2,2} - a_{1,2} a_{2,1}$

Ez a jól ismert "főátló mínusz mellékátló" képlet, ami közvetlenül a definícióból adódik.

9.5. A determináns alaptulajdonságai

A determináns általános definíciója alapján belátható néhány olyan szabály, amely jelentősen megkönnyíti a számolást bizonyos mátrixtípusok esetén.

2.4.6. Tétel

Legyen $A$ egy $(n \times n)$-es mátrix.

i

Ha $A$-nak van csupa 0 elemet tartalmazó sora vagy oszlopa, akkor $\det(A) = 0$.

ii

Ha $A$ felsőháromszög-mátrix vagy alsóháromszög-mátrix, akkor a determinánsa a főátlóbeli elemek szorzata: $\det(A) = a_{1,1} \cdot a_{2,2} \cdot \dots \cdot a_{n,n}$

A tétel bizonyítása:

Ad (i): A determináns definíciója szerint minden tag egy $n$ tényezős szorzat, amely minden sorból és oszlopból pontosan egy elemet tartalmaz. Ha van egy tiszta nulla sor/oszlop, akkor minden egyes szorzatban szerepelni fog egy 0, így az összes tag értéke 0 lesz.

Ad (ii): Felsőháromszög-mátrix esetén a bástyaelhelyezési szabály miatt csak egyetlen olyan szorzat van, amely nem tartalmaz nullát: a főátló. Az első oszlopból csak $a_{1,1}$ választható (többi 0), a másodikból csak $a_{2,2}$ (mivel az első sor már foglalt), és így tovább. Ennek a permutációnak az inverziószáma 0, tehát az előjele pozitív.

Példafeladat: Háromszögmátrix determinánsa

Feladat:

Számítsa ki az alábbi mátrix determinánsát! $$ A = \begin{pmatrix} \mathbf{2} & 5 & -1 \\ 0 & \mathbf{3} & 4 \\ 0 & 0 & \mathbf{-1} \end{pmatrix} $$

Elemzés:

Mivel a főátló alatt minden elem 0, ez egy felsőháromszög-mátrix.

A 2.4.6. (ii) tétel alapján a megoldás:

$\det(A) = 2 \cdot 3 \cdot (-1) = \mathbf{-6}$

9.6. Elemi műveletek és a determináns

Mivel a Gauss-elimináció során elemi sorműveleteket végzünk a mátrixon, elengedhetetlen tudnunk, hogy ezek a lépések hogyan módosítják a determináns értékét.

2.4.7. Tétel

Legyen $A$ egy $(n \times n)$-es mátrix, $\lambda \in \mathbb{R}$ skalár.

i

Ha $A$ egy sorát (vagy oszlopát) megszorozzuk $\lambda$-val, a kapott $A'$ mátrix determinánsa:
$\det(A') = \lambda \cdot \det(A)$.

ii

Ha $A$ két sorát (vagy két oszlopát) felcseréljük, a kapott $A'$ mátrix determinánsa az eredeti ellentettje lesz:
$\det(A') = (-1) \cdot \det(A)$.

iii

Ha $A$ egy sorához hozzáadjuk egy másik sor $\lambda$-szorosát, a kapott $A'$ mátrix determinánsa nem változik:
$\det(A') = \det(A)$.

A sorcsere (ii) bizonyítása:

Két sor felcserélésekor a determináns minden egyes szorzatát adó bástyaelhelyezés változatlan marad, de a hozzájuk tartozó oszlopindex-permutációban két elem helyet cserél.

Tudjuk, hogy egy permutációban két elem felcserélése megváltoztatja a permutáció paritását (az inverziószám paritása ellenkezőjére vált).

Mivel minden egyes szorzat tagjai azonosak maradnak, de az előjelük a $(-1)^{I(\pi)}$ tényező miatt ellenkezőjére változik, a teljes összeg (a determináns) is az ellentettjére változik. □

Példafeladat: Determináns számítása sorműveletekkel

Feladat:

Tudjuk, hogy $\det(A) = 10$. Mennyi lesz a determinánsa annak a mátrixnak, amelyet úgy kaptunk, hogy $A$ első sorát 3-mal megszoroztuk, majd felcseréltük a második és harmadik sort?

1

Szorzás $\lambda=3$-mal $\rightarrow$ A determináns is 3-szorosára nő: $10 \cdot 3 = 30$.

2

Sorcsere $\rightarrow$ A determináns előjelet vált: $30 \cdot (-1) = -30$.

Végeredmény

$\det(A') = -30$

9.7. A determináns additivitása

A determináns egyik legfontosabb tulajdonsága, hogy „lineárisan viselkedik” az egyes soraiban. Ez azt jelenti, hogy ha egy mátrix egyetlen sorát két sorvektor összegeként kapjuk meg, akkor a determináns értéke is két külön determináns összegeként számolható el.

2.4.8. Lemma

Tegyük fel, hogy az $(n \times n)$-es $X, Y$ és $Z$ mátrixok az $i$-edik soraiktól eltekintve elemről elemre megegyeznek. Az $i$-edik soraikra viszont fennáll, hogy:

$z_{i,j} = x_{i,j} + y_{i,j} \quad \text{minden } 1 \le j \le n \text{ esetén.}$

Vagyis a $Z$ mátrix $i$-edik sora az $X$ és az $Y$ mátrixok $i$-edik sorának tagonkénti összege. Ekkor:

$\det(Z) = \det(X) + \det(Y)$

A lemma bizonyítása:

Vegyünk egy tetszőleges bástyaelhelyezést $Z$-ben, amely feleljen meg a $\pi$ permutációnak. Az ebből keletkező szorzat: $$(-1)^{I(\pi)} \cdot z_{1,\pi_1} \cdot \dots \cdot z_{i,\pi_i} \cdot \dots \cdot z_{n,\pi_n}$$

A $z_{i,\pi_i} = x_{i,\pi_i} + y_{i,\pi_i}$ behelyettesítés után a szorzat két részre bomlik: $$(-1)^{I(\pi)} \cdot z_{1,\pi_1} \cdot \dots \cdot (x_{i,\pi_i} + y_{i,\pi_i}) \cdot \dots \cdot z_{n,\pi_n}$$

Felbontva a zárójelet, és kihasználva, hogy minden $k \neq i$ esetén $z_{k,\pi_k} = x_{k,\pi_k} = y_{k,\pi_k}$, azt kapjuk, hogy minden bástyaelhelyezésnél a $Z$-beli szorzat megegyezik az $X$-beli és $Y$-beli szorzatok összegével. Ezeket minden permutációra összegezve adódik a $\det(Z) = \det(X) + \det(Y)$ egyenlőség. □

Példafeladat: Additivitás alkalmazása

Feladat:

Számítsa ki a $Z$ mátrix determinánsát a felbontás segítségével! $$ Z = \begin{pmatrix} 1 & 2 \\ 5+3 & 4+1 \end{pmatrix} $$

X mátrix:

$$ \det \begin{pmatrix} 1 & 2 \\ 5 & 4 \end{pmatrix} = 4 - 10 = -6 $$

Y mátrix:

$$ \det \begin{pmatrix} 1 & 2 \\ 3 & 1 \end{pmatrix} = 1 - 6 = -5 $$

Végeredmény a Lemma alapján:

$\det(Z) = -6 + (-5) = \mathbf{-11}$

Ugyanezt kapnánk, ha összeadnánk a számokat a sorban: $Z = \begin{pmatrix} 1 & 2 \\ 8 & 5 \end{pmatrix} \rightarrow 5 - 16 = -11$.

9.8. A (iii) típusú sorművelet bizonyítása

A Gauss-elimináció leggyakrabban használt lépése, amikor egy sorhoz egy másik sor $\lambda$-szorosát adjuk hozzá. Belátjuk, hogy ez a művelet valóban nem változtatja meg a determináns értékét.

A levezetés menete:

1

Tekintsük az $A'$ mátrixot, amely az $A$-ból úgy keletkezett, hogy az $i$-edik sorhoz hozzáadtuk a $j$-edik sor $\lambda$-szorosát. Az $A'$ mátrix $i$-edik sorának elemei:
$a'_{i,k} = a_{i,k} + \lambda \cdot a_{j,k} \quad (\text{minden } k\text{-ra})$

2

Alkalmazzuk a 2.4.8. Lemmát (additivitás) az $A'$ mátrixra! Bontsuk fel az $i$-edik sort az eredeti $i$-edik sorra és a hozzáadott $\lambda$-szoros $j$-edik sorra. Ekkor:
$\det(A') = \det(A) + \det(Y)$ Ahol $Y$ az a mátrix, amelynek $i$-edik sorában a $\lambda \cdot a_{j,k}$ elemek állnak, minden más sora pedig megegyezik $A$-val.

3

Vizsgáljuk meg $\det(Y)$ értékét! Emeljük ki $\lambda$-t az $i$-edik sorból:
$\det(Y) = \lambda \cdot \det(Y')$ Az $Y'$ mátrix $i$-edik sora most már megegyezik a $j$-edik sorával (hiszen mindkettő az eredeti mátrix $j$-edik sora).

Miért nulla $\det(Y')$?

Ha $Y'$-ben felcseréljük az $i$-edik és $j$-edik sort, a determináns előjelet vált: $\det(Y') = -\det(Y')$. Mivel a két sor azonos, a mátrix valójában nem változott a csere után sem, így az értéke csak nulla lehet.

Következésképpen $\det(Y) = 0$, tehát valóban: $\det(A') = \det(A)$. □

Gyakorlati konklúzió

Ez a bizonyítás a tartóoszlopa a determinánsok hatékony kiszámításának: bátran végezhetünk "nullázást" a Gauss-eliminációval, mert az nem változtatja meg a keresett értéket.

9.9. A determináns kiszámítása (2.4.5. fejezet)

A determináns definíciója szerinti kiszámítás $n!$ műveletet igényelne, ami már egy $10 \times 10$-es mátrixnál is több millió lépést jelentene. A gyakorlatban ezért a Gauss-elimináció egy változatát használjuk, amely a 2.4.7. Tételben megismert sorműveletek hatásait követi nyomon.

Az algoritmus lényege

A cél a mátrixot felsőháromszög-alakra hozni, miközben egy $D$ segédváltozóban tároljuk a determináns értékének változásait. Az eljárás végén a determináns értéke a $D$ szám lesz.

Gauss-elimináció a determináns kiszámítására

Bemenet: Egy $(n \times n)$-es $A$ mátrix.

1: $i \leftarrow 1; D \leftarrow 1$

2: ciklus

3:   ha $a_{i,i} \neq 0$, akkor:

4:     $D \leftarrow a_{i,i} \cdot D$

5:     Szorozzuk meg az $i$-edik sort $\frac{1}{a_{i,i}}$-vel.

6:     ha $i < n$, akkor: Minden $i < t \le n$ esetén adjuk a $t$-edik sorhoz az $i$-edik sor $(-a_{t,i})$-szeresét.

7:     $i \leftarrow i + 1$

8:   különben: (ha $a_{i,i} = 0$)

9:     ha van olyan $t > i$, amelyre $a_{t,i} \neq 0$, akkor: Cseréljük fel a két sort, és $D \leftarrow (-1) \cdot D$.

10:     különben: print "det A = 0"; stop

11: ciklus vége

Példafeladat: Algoritmus követése

Feladat:

Számítsa ki a determinánst, ha az elimináció során egy sorcserét hajtottunk végre, majd a végén a főátlóban 2, 5 és 1 értékek szerepeltek (kiemelés előtt)!

Lépések:

  • Indulás: $D = 1$
  • Sorcserénél: $D = 1 \cdot (-1) = -1$
  • Főátlóbeli elemek kiemelésekor: $D = -1 \cdot 2 \cdot 5 \cdot 1 = -10$

Végeredmény

$\det(A) = -10$

Determináns Elemzése

Laplace-kifejtés és Gauss-elimináció megjelenítéssel

3x3-as Mátrix adatai