Permutáló mátrix

Ez a szócikk nem tünteti fel a független forrásokat, amelyeket felhasználtak a készítése során. Emiatt nem tudjuk közvetlenül ellenőrizni, hogy a szócikkben szereplő állítások helytállóak-e. Segíts megbízható forrásokat találni az állításokhoz! Lásd még: A Wikipédia nem az első közlés helye.

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élda 2×2-es, 3×3-as és 4×4-es permutáló mátrixra:

${\displaystyle A\ :=\ {\begin{pmatrix}0&1\\1&0\end{pmatrix}}}$     ${\displaystyle B\ :=\ {\begin{pmatrix}0&1&0\\1&0&0\\0&0&1\end{pmatrix}}}$     ${\displaystyle 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:

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

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á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ó:

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

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

• ${\displaystyle Ap_{2}}$ ${\displaystyle =}$ ${\displaystyle {\begin{pmatrix}0&1\\1&0\end{pmatrix}}\cdot {\begin{pmatrix}1\\2\end{pmatrix}}}$ ${\displaystyle =}$ ${\displaystyle {\begin{pmatrix}(0\ 1)(1\ 2)\\(1\ 0)(1\ 2)\end{pmatrix}}}$ ${\displaystyle =}$ ${\displaystyle {\begin{pmatrix}(0\cdot 1+1\cdot 2)\\(1\cdot 1+0\cdot 2)\end{pmatrix}}}$ ${\displaystyle =}$
  ${\displaystyle =}$ ${\displaystyle {\begin{pmatrix}0+2\\1+0\end{pmatrix}}}$ ${\displaystyle =}$ ${\displaystyle {\begin{pmatrix}2\\1\end{pmatrix}}}$
  

illetve

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

${\displaystyle =}$ ${\displaystyle {\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}}}$ ${\displaystyle =}$

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

• ${\displaystyle Bp_{3}}$ ${\displaystyle =}$ ${\displaystyle {\begin{pmatrix}0&1&0\\1&0&0\\0&0&1\end{pmatrix}}\cdot {\begin{pmatrix}1\\2\\3\end{pmatrix}}}$ ${\displaystyle =}$ ${\displaystyle {\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}}}$ ${\displaystyle =}$
  ${\displaystyle =}$ ${\displaystyle {\begin{pmatrix}0+2+0\\1+0+0\\0+0+3\end{pmatrix}}}$ ${\displaystyle =}$ ${\displaystyle {\begin{pmatrix}2\\1\\3\end{pmatrix}}}$
  

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

• ${\displaystyle 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}}}$
• ${\displaystyle 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 ${\displaystyle 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 ${\displaystyle 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 ${\displaystyle (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}\ =\ }$ ${\displaystyle \ =\ 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: ${\displaystyle (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}\ =\ }$ ${\displaystyle \ =\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}\ =\ }$ ${\displaystyle \ =\ 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: ${\displaystyle (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}\ =\ }$ ${\displaystyle \ =\ \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\ =\ }$ ${\displaystyle \ =\ 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 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 ${\displaystyle {\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.

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

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