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:

$$\begin{gathered} A \\ := \\ \left(\begin{array}{cc}0& 1\\ 1& 0\end{array}\right) \end{gathered}$$     $$\begin{gathered} B \\ := \\ \left(\begin{array}{ccc}0& 1& 0\\ 1& 0& 0\\ 0& 0& 1\end{array}\right) \end{gathered}$$     $$\begin{gathered} W \\ := \\ \left(\begin{array}{cccc}0& 1& 0& 0\\ 0& 0& 1& 0\\ 1& 0& 0& 0\\ 0& 0& 0& 1\end{array}\right) \end{gathered}$$

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: $$\begin{gathered} E_n \\ = \\ \left(\begin{array}{ccccc}1& 0& ...& 0& 0\\ 0& 1& ...& 0& 0\\ ...& ...& ...& ...& ...\\ 0& 0& ...& 1& 0\\ \\ 0& 0& ...& 0& 1\end{array}\right) \end{gathered}$$

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$ $=$ $\left(\begin{array}{cc}1& 2\end{array}\right)\cdot \left(\begin{array}{cc}0& 1\\ 1& 0\end{array}\right)$ $=$ $$\begin{gathered} \left(\begin{array}{cc}(1 \\ 2)(0 \\ 1)& (1 \\ 2)(1 \\ 0)\end{array}\right) \end{gathered}$$ $=$

$=$ $\left(\begin{array}{cc}(1\cdot 0+2\cdot 1)& (1\cdot 1+2\cdot 0)\end{array}\right)$ $=$ $\left(\begin{array}{cc}0+2& 1+0\end{array}\right)$ $=$ $\left(\begin{array}{cc}2& 1\end{array}\right)$

• $A{p}_2$ $=$ $\left(\begin{array}{cc}0& 1\\ 1& 0\end{array}\right)\cdot \left(\begin{array}{c}1\\ 2\end{array}\right)$ $=$ $$\begin{gathered} \left(\begin{array}{c}(0 \\ 1)(1 \\ 2)\\ (1 \\ 0)(1 \\ 2)\end{array}\right) \end{gathered}$$ $=$ $\left(\begin{array}{c}(0\cdot 1+1\cdot 2)\\ (1\cdot 1+0\cdot 2)\end{array}\right)$ $=$
  $=$ $\left(\begin{array}{c}0+2\\ 1+0\end{array}\right)$ $=$ $\left(\begin{array}{c}2\\ 1\end{array}\right)$
  

illetve $p_3^{*}B$ $=$ $\left(\begin{array}{ccc}1& 2& 3\end{array}\right)\cdot \left(\begin{array}{ccc}0& 1& 0\\ 1& 0& 0\\ 0& 0& 1\end{array}\right)$ $=$ $=$ $\left(\begin{array}{ccc}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{array}\right)$ $=$ $=$ $\left(\begin{array}{ccc}0+2+0& 1+0+0& 0+0+3\end{array}\right)$ $=$ $\left(\begin{array}{ccc}2& 1& 3\end{array}\right)$

• $B{p}_3$ $=$ $\left(\begin{array}{ccc}0& 1& 0\\ 1& 0& 0\\ 0& 0& 1\end{array}\right)\cdot \left(\begin{array}{c}1\\ 2\\ 3\end{array}\right)$ $=$ $\left(\begin{array}{c}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{array}\right)$ $=$
  $=$ $\left(\begin{array}{c}0+2+0\\ 1+0+0\\ 0+0+3\end{array}\right)$ $=$ $\left(\begin{array}{c}2\\ 1\\ 3\end{array}\right)$
  

Továbbá, legyen $$\begin{gathered} C \\ = \\ \left(\begin{array}{ccc}1& 2& 3\\ 10& 20& 30\\ 100& 200& 300\end{array}\right) \end{gathered}$$. Ekkor

• $$\begin{gathered} CB \\ = \\ \left(\begin{array}{ccc}1& 2& 3\\ 10& 20& 30\\ 100& 200& 300\end{array}\right)\left(\begin{array}{ccc}0& 1& 0\\ 1& 0& 0\\ 0& 0& 1\end{array}\right) \\ = \\ \left(\begin{array}{ccc}2& 1& 3\\ 20& 10& 30\\ 200& 100& 300\end{array}\right) \end{gathered}$$
• $$\begin{gathered} BC \\ = \\ \left(\begin{array}{ccc}0& 1& 0\\ 1& 0& 0\\ 0& 0& 1\end{array}\right)\left(\begin{array}{ccc}1& 2& 3\\ 10& 20& 30\\ 100& 200& 300\end{array}\right) \\ = \\ \left(\begin{array}{ccc}10& 20& 30\\ 1& 2& 3\\ 100& 200& 300\end{array}\right) \end{gathered}$$
  

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 $$\begin{gathered} A \\ := \\ \left(\begin{array}{cccc}{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{array}\right) \\ = \\ \left[\begin{array}{c}f(1)\\ f(2)\\ ...\\ f(n)\end{array}\right] \\ = \\ [f(j)] \end{gathered}$$, legyen a szorzandó mátrix $$\begin{gathered} B \\ := \\ \left(\begin{array}{cccc}{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{array}\right) \end{gathered}$$. Ekkor definíció szerint az AB n×n-es szorzatmátrix i-edik sorában és j-edik oszlopában álló eleme $$\begin{gathered} (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} \\ = \end{gathered}$$ $$\begin{gathered} = \\ 0b_{1,j}+0b_{2,j}+...+1b_{f(i),j}+...+0b_{n,j} \\ = \\ {b}_{f(i),j} \end{gathered}$$. 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: $$\begin{gathered} (ab{)}_{i,j} \\ = \\ \sum _{k=1}^n{a}_{i,k}{b}_{k,j} \\ =\sum _{k\in {\mathbb{\mathbb{N}}}_n-\{f(i)\}}{a}_{i,k}{b}_{k,j}+\sum _{k=f(i)}{a}_{i,k}{b}_{k,j} \\ = \end{gathered}$$ $$\begin{gathered} =\sum _{k\in {\mathbb{\mathbb{N}}}_n-\{f(i)\}}0b_{k,j}+a_{i,f(i)}{b}_{f(i),j} \\ = \\ 0\left(\sum _{k\in {\mathbb{\mathbb{N}}}_n-\{f(i)\}}{b}_{k,j}\right)+1b_{f(i),j} \\ = \end{gathered}$$ $$\begin{gathered} = \\ 0+b_{f(i),j} \\ = \\ {b}_{f(i),j} \end{gathered}$$, é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: $$\begin{gathered} (ba{)}_{i,j} \\ = \\ \sum _{k=1}^n{b}_{i,k}{a}_{k,j} \\ = \\ \sum _{k\in {\mathbb{\mathbb{N}}}_n-\{g(i)\}}{b}_{i,k}{a}_{k,j}+\sum _{k=g(j)}{b}_{i,k}{a}_{k,j} \\ = \end{gathered}$$ $$\begin{gathered} = \\ \sum _{k\in {\mathbb{\mathbb{N}}}_n-\{g(i)\}}{b}_{i,k}0+b_{i,g(j)}{a}_{g(j),j} \\ = \\ 0\left(\sum _{k\in {\mathbb{\mathbb{N}}}_n-\{g(j)\}}{b}_{i,k}\right)+b_{i,g(j)}1 \\ = \end{gathered}$$ $$\begin{gathered} = \\ 0+b_{i,g(j)} \\ = \\ {b}_{i,g(j)} \end{gathered}$$, 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{gathered} \left(\begin{array}{cc}0& 1\\ 1& 0\end{array}\right)+\left(\begin{array}{cc}1& 0\\ 0& 1\end{array}\right) \\ = \\ \left(\begin{array}{cc}1& 1\\ 1& 1\end{array}\right) \end{gathered}$$, 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.