Permutáló mátrix

A Wikipédiából, a szabad enciklopédiából
A hat darab 3×3-as permutáló mátrix „szorzótáblája”. A kis 3×3-as négyzetecskék jelképezik az egyes mátrixokat, a pirosra színezett cellák az 1 értékű, míg az üresen hagyottak a 0 értékű cellákat. A középen lévő táblázat elemei a sorok és oszlopok fejlécében lévő mátrixok e sorrendben vett szorzatai.

Egy n×n-es mátrixot permutáló mátrixnak („átrendező mátrixnak”) nevezünk, ha minden sorában és minden oszlopában egy és csak egy cellában 1-es áll, a többi elem a sorokban, illetve oszlopokban nulla.

Egy másik (genetikusabb szemléletű) definíció szerint, n×n-es permutáló mátrix minden olyan mátrix, mely úgy adódik, hogy az n×n-es egységmátrix sorainak vagy oszlopainak sorrendjét megváltoztatjuk.

A permutáló mátrixok nevüket onnan kapták, hogy a velük való szorzás eredményeképp az n×n-es mátrixok sorai (ha a permutáló mátrixszal balról szorzunk), illetve oszlopai átrendeződnek, azaz az eredménymátrix a permutáló mátrixszal szorzott mátrix két vagy több sorának, illetve oszlopának felcserélésével áll elő, de a sorok, illetve oszlopok (például elemeik) más tekintetben nem változnak meg.

Példák[szerkesztés | forrásszöveg szerkesztése]

Példa 2×2-es, 3×3-as és 4×4-es permutáló mátrixra:

 A \ := \ \begin{pmatrix} 0 & 1 \\ 1 & 0 \end{pmatrix}      B \ := \ \begin{pmatrix} 0 & 1 & 0 \\ 1 & 0 & 0 \\ 0 & 0 & 1 \end{pmatrix}      W \ := \ \begin{pmatrix} 0 & 1 & 0 & 0 \\ 0 & 0 & 1 &0 \\ 1 & 0 & 0 & 0 \\ 0 & 0 & 0 & 1 \end{pmatrix}

Az A sor-főindexei f(1) = 2, f(2) = 1. A B sor-főindexei f(1) = 2, f(2) = 1, f(3) = 3. A mátrixok véletlenül szimmetrikusak a főátlóra, ezért az oszlopindexek ugyanazok, mint a sorindexek: g(1) = 2, g(2) = 1; illetve g(1) = 2, g(2) = 1, g(3) = 3. A W sor-főindexei rendre 2,3,1,4; míg oszlop-főindexei rendre 3,1,2,4.

Nevezetes példa permutáló mátrixra az n×n-es En egységmátrix:

 E_{n} \ = \ \begin{pmatrix} 1 & 0 & ... & 0 & 0 \\ 0 & 1 & ... & 0 & 0 \\ ... & ... & ... & ... & ... \\ 0 & 0 & ... & 1 & 0 \\ \\ 0 & 0 & ... & 0 & 1 \end{pmatrix}

Főindex[szerkesztés | forrásszöveg szerkesztése]

A fentiek szerint egy P permutáló mátrix minden i sorindexhez létezik egy f(i) oszlopindex, amelyre pi,f(i) = 1, míg a j∈Nn, j≠f(i) oszlopindexekre pi,j=0. Az f(i) oszlopindexet a mátrix i-edik sorának főindexének, avagy sor-főindexének nevezzük, a pi,f(i) = 1 elemet pedig a mátrix i-edik sora főelemének, vagy sor-főelemének.

Hasonló igaz az oszlopokra is, minden j oszlopindexhez létezik egy g(j) sorindex, amelyre pg(j),j = 1, míg az i∈Nn, i≠g(j) sorindexekre pi,j = 0. A g(i) oszlopindexet a mátrix i-edik oszlopának főindexének, avagy oszlop-főindexének nevezzük, a pg(j),j = 1 elemet pedig a mátrix j-edik oszlopa oszlop-főelemének.

Ha több permutáló mátrix főindexeiről beszélünk, akkor alsó indexben feltüntetjük a mátrixok betűjelét, például az A permutáló mátrix i-edik (sor-)főindexe fA(i).

A permutáló mátrix átrendezi az elemeket[szerkesztés | forrásszöveg szerkesztése]

A permutáló mátrixokkal való szorzás felcseréli a vektorok elemeit, azok sorrendjét megváltoztatja. Egy X mátrix P permutáló mátrixszal való szorzása balról a szorzott mátrix (X) sorait rendezi át, mégpedig úgy, hogy a PX szorzatmátrix i-edik sora az eredeti szorzandó mátrix (X) f(i)-edik sora lesz, ahol f(i) a permutáló mátrix i-edik sorának főindexe. Egy X mátrix P permutáló mátrixszal való szorzása jobbról a szorzott mátrix (X) oszlopait rendezi át, mégpedig úgy, hogy az XP szorzatmátrix j-edik oszlopa az eredeti szorzandó mátrix (X) g(j)-edik oszlopa lesz, ahol g(j) a permutáló mátrix j-edik oszlop-főindexe.

Illusztráció:

  •  p_{2}^{*}A  =  \begin{pmatrix} 1 & 2 \end{pmatrix} \cdot \begin{pmatrix} 0 & 1\\ 1 & 0 \end{pmatrix}  =  \begin{pmatrix} (1 \ 2)(0 \ 1) & (1 \ 2)(1 \ 0) \end{pmatrix}  =

 =  \begin{pmatrix} (1 \cdot 0+ 2 \cdot 1) & (1 \cdot 1+2 \cdot 0) \end{pmatrix}  =  \begin{pmatrix} 0+2 & 1+0 \end{pmatrix}  =  \begin{pmatrix} 2 & 1 \end{pmatrix}

  •  A p_{2}  =  \begin{pmatrix} 0 & 1\\ 1 & 0 \end{pmatrix} \cdot \begin{pmatrix} 1 \\ 2 \end{pmatrix}  =  \begin{pmatrix} (0 \ 1)(1 \ 2) \\ (1 \ 0)(1 \ 2) \end{pmatrix}  =  \begin{pmatrix} (0 \cdot 1+ 1 \cdot 2) \\ (1 \cdot 1+0 \cdot 2) \end{pmatrix}  =
     =  \begin{pmatrix} 0+2 \\ 1+0 \end{pmatrix}  =  \begin{pmatrix} 2 \\ 1 \end{pmatrix}

illetve

 p_{3}^{*}B  =  \begin{pmatrix} 1 & 2 & 3 \end{pmatrix} \cdot \begin{pmatrix} 0 & 1 & 0 \\ 1 & 0 & 0 \\ 0 & 0 & 1 \end{pmatrix}  =

 =  \begin{pmatrix} 1 \cdot 0 + 2 \cdot 1 + 3 \cdot 0 & 1 \cdot 1 + 2 \cdot 0 + 3 \cdot 0 & 1 \cdot 0 + 2 \cdot 0 + 3 \cdot 1 \end{pmatrix}  =

 =  \begin{pmatrix} 0+2+0 & 1+0+0 & 0+0+3 \end{pmatrix}  =  \begin{pmatrix} 2 & 1 & 3 \end{pmatrix}

  •  B p_{3}  =  \begin{pmatrix} 0 & 1 & 0 \\ 1 & 0 & 0 \\ 0 & 0 & 1 \end{pmatrix} \cdot \begin{pmatrix} 1 \\ 2 \\ 3 \end{pmatrix}  =  \begin{pmatrix} 0 \cdot 1 + 1 \cdot 2 + 0 \cdot 3 \\ 1 \cdot 1+ 0 \cdot 2 + 0 \cdot 3 \\ 0 \cdot 1 + 0 \cdot 2 + 1 \cdot 3 \end{pmatrix}  =
     =  \begin{pmatrix} 0+2+0 \\ 1+0+0 \\ 0+0+3 \end{pmatrix}  =  \begin{pmatrix} 2 \\ 1 \\ 3 \end{pmatrix}

Továbbá, legyen  C \ = \ \begin{pmatrix} 1 & 2 & 3 \\ 10 & 20 & 30 \\ 100 & 200 & 300 \end{pmatrix} . Ekkor

  •  CB \ = \ \begin{pmatrix} 1 & 2 & 3 \\ 10 & 20 & 30 \\ 100 & 200 & 300 \end{pmatrix} \begin{pmatrix} 0 & 1 & 0 \\ 1 & 0 & 0 \\ 0 & 0 & 1 \end{pmatrix} \ = \ \begin{pmatrix} 2 & 1 & 3 \\ 20 & 10 & 30 \\ 200 & 100 & 300 \end{pmatrix}
  •  BC \ = \ \begin{pmatrix} 0 & 1 & 0 \\ 1 & 0 & 0 \\ 0 & 0 & 1 \end{pmatrix} \begin{pmatrix} 1 & 2 & 3 \\ 10 & 20 & 30 \\ 100 & 200 & 300 \end{pmatrix} \ = \ \begin{pmatrix} 10 & 20 & 30 \\ 1 & 2 & 3 \\ 100 & 200 & 300 \end{pmatrix}

Bizonyítás:

  1. A balról szorzásra (sorok átrendezésére) vonatkozó állítást bizonyítjuk.
    1. Legyen A tetszőleges n×n-es permutáló mátrix, melynek főindexalakja  A \ := \ \begin{pmatrix} a_{1,1} & a_{1,2} & ... & a_{1,n} \\ a_{2,1} & a_{2,2} & ... & a_{2,n} \\ ... & ... & ... & ... \\ a_{n,1} & a_{n,2} & ... & a_{n,n} \end{pmatrix} \ = \ \begin{bmatrix} f(1) \\ f(2) \\ ... \\ f(n) \end{bmatrix} \ = \ \left[ f(j) \right] , legyen a szorzandó mátrix  B \ := \ \begin{pmatrix} b_{1,1} & b_{1,2} & ... & b_{1,n} \\ b_{2,1} & b_{2,2} & ... & b_{2,n} \\ ... & ... & ... & ... \\ b_{n,1} & b_{n,2} & ... & b_{n,n} \end{pmatrix} . Ekkor definíció szerint az AB n×n-es szorzatmátrix i-edik sorában és j-edik oszlopában álló eleme  (ab)_{i,j} \ = \ a_{i,1}b_{1,j}+a_{i,2}b_{2,j}+...+a_{i,f(i)}b_{f(i),j}+...+a_{i,n}b_{n,j} \ = \  \ = \ 0b_{1,j}+0b_{2,j}+...+1b_{f(i),j}+...+0b_{n,j} \ = \ b_{f(i),j} . Ez azt jelenti, a szorzatmátrix i-edik sorába (tehát ha az „i” indexet az abi,j kifejezésben rögzítettnek gondoljuk ) a szorzandó mátrix f(i)edik sorának elemei kerülnek, egyéb változtatás nélkül. Ezt akartuk belátni.
    2. Még precízebb bizonyítás adható a szumma-jelöléssel:  (ab)_{i,j} \ = \ \sum_{k=1}^{n}a_{i,k}b_{k,j} \ = \sum_{ k \in \mathbb{N}_{n}- \left\{ f(i) \right\} } a_{i,k}b_{k,j}+\sum_{ k = f(i)} a_{i,k}b_{k,j} \ = \  \ = \sum_{ k \in \mathbb{N}_{n}- \left\{ f(i) \right\} } 0b_{k,j}+a_{i,f(i)}b_{f(i),j} \ = \ 0 \left( \sum_{ k \in \mathbb{N}_{n}- \left\{ f(i) \right\} } b_{k,j} \right) + 1b_{f(i),j} \ = \  \ = \ 0+b_{f(i),j} \ = \ b_{f(i),j} , és az eredményből levont következtetést ld. a fentebbi szöveges sorokban. QED.
  2. A jobbról szorzásra vonatkozó állítás hasonlóan bizonyítható, csak a sor-főindexek helyett az oszlop-főindexeket kell nézni:  (ba)_{i,j} \ = \ \sum_{k=1}^{n}b_{i,k}a_{k,j} \ = \ \sum_{ k \in \mathbb{N}_{n}- \left\{ g(i) \right\} } b_{i,k}a_{k,j}+\sum_{ k = g(j)} b_{i,k}a_{k,j} \ = \  \ = \ \sum_{ k \in \mathbb{N}_{n}- \left\{ g(i) \right\} } b_{i,k}0+b_{i,g(j)}a_{g(j),j} \ = \ 0 \left( \sum_{ k \in \mathbb{N}_{n}- \left\{ g(j) \right\} } b_{i,k} \right) + b_{i,g(j)}1 \ = \  \ = \ 0+b_{i,g(j)} \ = \ b_{i,g(j)} , s ez pontosan azt jelenti, hogy a szorzatmátrix j-edik oszlopa a B g(j)-edik oszlopával egyezik meg.

A permutáló mátrixok csoportja[szerkesztés | forrásszöveg szerkesztése]

A definícióból adódóan két n×n-es permutáló mátrix összege, különbsége, számszorosa (kivéve az egyszeresét), például ellentettje sosem permutáló mátrix, például  \begin{pmatrix} 0 & 1 \\ 1 & 0 \end{pmatrix} + \begin{pmatrix} 1 & 0 \\ 0 & 1 \end{pmatrix} \ = \ \begin{pmatrix} 1 & 1 \\ 1 & 1 \end{pmatrix} , ez nem permutáló mátrix. Így a lineáris kombinálás (leszámítva a nagyon triviális esetet, amikor az egyik együttható 1, az összes többi nulla) kivezet az n×n-es permutáló mátrixok köréből.

Érvényes viszont, hogy a permutáló mátrixok a mátrixszorzásra nézve egységelemes csoportot alkotnak.

Külső hivatkozások[szerkesztés | forrásszöveg szerkesztése]

A magyar Wikikönyvekben
további információk találhatók