Permutáló mátrix

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

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 E_n 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

A fentiek szerint egy P permutáló mátrix minden i sorindexhez létezik egy f(i) oszlopindex, amelyre p_i,f(i) = 1, míg a j∈N_n, j≠f(i) oszlopindexekre p_i,j=0. Az f(i) oszlopindexet a mátrix i-edik sorának főindexének, avagy sor-főindexének nevezzük, a p_i,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 p_g(j),j = 1, míg az i∈N_n, i≠g(j) sorindexekre p_i,j = 0. A g(i) oszlopindexet a mátrix i-edik oszlopának főindexének, avagy oszlop-főindexének nevezzük, a p_g(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 f_A(i).

A permutáló mátrix átrendezi az elemeket

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}}$

• $Ap_{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}}$

• $Bp_{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 ab_i,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

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

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

permutáló mátrixok témában.