Lineáris algebra/Permutáló mátrixok

A permutáló mátrix fogalma

Definíció (P.1.):

---

Egy n×n-es mátrixot permutáló mátrixnak (magyarul: á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.

A fentiek szerint egy P permutáló mátrix minden i∈N_n sorindexéhez létezik egy f(i) oszlopinex, 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(j) 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 mást nem mondunk, főindexen sor-főindexet értünk.

A „permutáló mátrix” kifejezés rövidítésére a p.m. betűket is alkalmazzuk a továbbiakban.

Példák

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

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

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. Az A,B 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 C sor-főindexei rendre 2,3,1,4; míg oszlop-főindexei rendre 3,1,2,4.

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

Hogyan megy ez a gyakorlatban?

Vektorok átrendezése

A permutáló mátrixokkal való szorzás felcseréli a vektorok elemeit, azok sorrendjét megváltoztatja. Jelöljük a továbbiakban az (1 2 3 ... n) sorvektort p_n*-gal, transzponáltját pedig p_n-nel! Példa arra, mit csinál a fenti A mátrix p₂* = (1 2)-vel, illetve a B mátrix a p₃* = (1 2 3)-mal mint sorvektorral (a vektorokat jobbról szorozva a mátrixokkal); illetve a megfelelő oszlopvektorral (ezeket balról szorozva a mátrixokkal):

• $p_2^{*}A$ $=$ $\left(\begin{array}{cc}1& 2\end{array}\right)\cdot \left(\begin{array}{cc}0& 1\\ 1& 0\end{array}\right)$ $=$ $\left(\begin{array}{cc}(12)(01)& (12)(10)\end{array}\right)$ $=$
  

$=$ $\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)$ $=$ $\left(\begin{array}{c}(01)(12)\\ (10)(12)\end{array}\right)$ $=$ $\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)$
  

Ha sorvektort szorzunk a permutáló mátrixszal jobbról, akkor eredményül szintén sorvektort kapunk. A sorvektort az oszlopokkal kombináljuk, vagyis a j-edik eredményoszlopban (a sorvektor és a permutáló mátrix j-edik oszlopának kombinációja) csak az a sorelem szerepel 1 együtthatóval, amelynek indexe megegyezik az oszlopban álló egyes sorindexével - a sor többi eleme 0-val szorzódva eltűnik. Tehát sorvektor szorzásakor, a j-edik oszlop kiszámításakor meg kell nézni, a j-edik oszlopban hányadik elem 1-es, legyen a k-adik, és ekkor a sorvektor k-adik eleme lesz az eredményvektor j-edik eleme.

A továbbiakban, tömörsége miatt, az illusztrációk során elsősorban az oszlopvektoros jelölésmódot alkalmazva beszélünk a permutáló mátrixokról.

Mátrixok átrendezése

MIndezek után talán nem is meglepő, hogy a permutáló mátrixszal való szorzás magukat a mátrixokat is átrendezi: a vele való jobbról szorzás a sorok elemeit (azaz az oszlopokat) cseréli fel egymás között, míg a velük való balról szorzás a másik szorzandó mátrix oszlopainak elemeit (azaz: a sorokat) cserélgeti.

Illusztrációul: legyen $C=\left(\begin{array}{ccc}1& 2& 3\\ 10& 20& 30\\ 100& 200& 300\end{array}\right)$. Ekkor

• $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)$
• $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)$
  

Ezeket összefoglalva is érdemes kimondani:

A főindexalak és az átrendezési törvények

Definíció (főindexalak):

---

Egy π(n): N(n)→N(n) kölcsönösen egyértelmű (bijektív) függvényt e halmaz (az 1,2,...,n elemek) egy permutációjának, avagy átrendezésének nevezzük. Szokás még az „n-edrendű permutáció” elnevezés használata is. Azt, hogy a permutáció melyik elemet melyik elembe viszi, így jelöljük: $\left(\begin{array}{cccc}1& 2& ...& n\\ \pi (1)& \pi (2)& ...& \pi (n)\end{array}\right)$, még rövidebben csak így: $\left(\begin{array}{cccc}\pi (1)& \pi (2)& ...& \pi (n)\end{array}\right)$.

Legyen A n×n-es permutáló mátrix, melyre igaz, hogy i-edik sorában az f(i)-edik elem (a főelem) 1-es, a többi nulla. Ekkor a mátrixot hasonlóan jelöljük, mintha permutációról lenne szó, csak szögletes zárójelek közé írjuk, jelezve, hogy ez nem oszlopvektor, hanem permutáló mátrix rövid alakja. A következő jelölésről van szó:

$A:=\left[\begin{array}{c}f(1)\\ f(2)\\ ...\\ f(n)\end{array}\right]=[f(i)]$
Ezt a szimbólumot az A permutáló mátrix főindexalakjának nevezzük és röviden az [A] ill. [f_A(i)] szimbólumokkal is jelöljük. Ne feledjük, ez azt jelenti, hogy a p.m.-szal balról szorzás esetén az i-edik sorba kell a szorzandó mátrix f(j)-edik sorát átpakolni.

Példák

(A B mátrix helyett olyat kerestünk, ami nem szimmetrikus, hogy látszódjék: a sorokban lévő egyes oszlopindexe - és nem az oszlopelem sorindexe - adja a szögletes zárójeles jelölés ugyanazon sorban lévő elemét):

$A:=\left(\begin{array}{cc}0& 1\\ 1& 0\end{array}\right)=\left[\begin{array}{c}2\\ 1\end{array}\right]$       $E:=\left(\begin{array}{ccc}0& 1& 0\\ 0& 0& 1\\ 1& 0& 0\end{array}\right)=\left[\begin{array}{c}2\\ 3\\ 1\end{array}\right]$

Nevezetes példa permutáló mátrixra az n×n-es E_n egységmátrix, melynek alakja és főindexalakja:

$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)=\left[\begin{array}{c}1\\ 2\\ ...\\ n-1\\ n\end{array}\right]=\left[\begin{array}{c}i\end{array}\right]$

Az átrendezési törvények

Permutáló mátrixszal való szorzás balról a szorzandó mátrix sorait egymáshoz viszonyítva átrendezi, a sor mint vektor (az elemsorrend) azonban nem változik; míg a jobbról szorzás az oszlopokat rendezi át, az oszlopok elemsorrendjének megtartásával.

1. Balról való szorzásnál a permutáló mátrix i-edik sorának j-edik cellájában álló egyes a szorzandó mátrix j-edik sorát teszi az i-edik sor helyére
2. Jobbról szorzásnál a permutáló mátrix j-edik oszlopának i-edik cellájában álló egyes a szorzandó mátrix i-edik oszlopát teszi a j-edik helyre.

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:=\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)]$, legyen a szorzandó mátrix $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)$. 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-\{f(i)\}}{a}_{i,k}{b}_{k,j}+\sum _{k=f(i)}{a}_{i,k}{b}_{k,j}=$ $=\sum _{k\in {\mathbb{N}}_n-\{f(i)\}}0b_{k,j}+a_{i,f(i)}{b}_{f(i),j}=0\left(\sum _{k\in {\mathbb{N}}_n-\{f(i)\}}{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-\{g(i)\}}{b}_{i,k}{a}_{k,j}+\sum _{k=g(j)}{b}_{i,k}{a}_{k,j}=$ $=\sum _{k\in {\mathbb{N}}_n-\{g(i)\}}{b}_{i,k}0+b_{i,g(j)}{a}_{g(j),j}=0\left(\sum _{k\in {\mathbb{N}}_n-\{g(j)\}}{b}_{i,k}\right)+b_{i,g(j)}1=$ $=0+b_{i,g(j)}=b_{i,g(j)}$, azaz a szorzatmátrix j-edik oszlopa a B mátrix g(j)-edik oszlopának elemeiből áll.

Gyakorlat:
Dolgozzuk át a szummajeles bizonyítást a jelek elemenkénti kifejtésével úgy, mint ahogy a balról szorzás bizonyításánál szerepel!

A főindexalak a sorindexek egy permutációja

Ha az i∈N_n indexhez hozzárendeljük az A mátrix F(A) = [f(i)] főindexalakjának i-edik f(i) elemét, az így nyert f leképezés az N_n halmazt kölcsönösen egyértelműen képezi le önmagára, azaz e halmaz egy permutációja.

(Szemléletesen ez pont azt jelenti, hogy p.m. minden sorában egy és csak egy helyen áll 1-es, a többi elem nulla).

Bizonyítás:

1. A bizonyításhoz megmutatjuk, hogy f injektív (két különböző indexhez különböző főindex tartozik); és szürjektív (f értékkészletének minden index az eleme).
   1. Legyen i,j∈N_n és i≠j; ekkor f(i)∈N_n ill. f(j)∈N_n az i-edik sor azon, az 1. definícióból következően egyértelműen létező cellájának egyértelműen létező oszlopindexe, melyre a mátrix (i,j)-edik eleme 1 (a többi nulla). Ha f(i)=f(j) lenne, ez azt jelentené, hogy az f(i)=f(j)-edik oszlopban két sor is lenne (az i-edik és j-edik is), amelyben 1-es áll. ez ellentmond a p.m. definíciójának.
   2. Megmutattuk, hogy az f függvény egy értéket csak egy helyen vesz fel, most megmutatjuk, hogy minden értéket fel is vesz. Valóban, a p.m. definíciója szerint a j-edik oszlopban van egy és csak egy egyes valamelyik sorban, ennek van sorindexe (mégpedig egyértelműen). Tehát ha j∈N_n tetszőleges (oszlop)index, ehhez van olyan i sorindex, hogy f(i)=j. QED.

Az n×n-es permutáló mátrixok száma

Jelöljük (egy T test feletti) összes n×n-es p.m. halmazát P_{T, n×n}-nel! Ha (ahogy az általában lenni szokott) nem fontos, melyik T test feletti mátrixokat nézzük, vagy a valós testről vam szó, akkor a T indexet nem írjuk ki.

(P.2.) Az n×n-es permutáló mátrixok száma n!

Tétel: |P_n×n| =n!, azaz az n×n-es permutáló mátrixok száma az n faktoriálisa.

Eszerint például 2! = 1×2 = 2 db. 2×2-es permutáló mátrix van; 5! = 1×2×3×4×5 = 120 db. 5×5-ös p.m. van; 6! = 5!×6 = 720 db. 6×6-os p.m. van, és így tovább.

Bizonyítás: Egyszerű gondolatmenet adja, hogy n! = 1×2×3× ... ×(n-1)×n db. n×n-es permutáló mátrix van. Ugyanis egy ilyen mátrixban n darab egyes van (minden sorban egy darab), és a többi elem nulla, tehát a mátrixot meghatározza, hogy melyik sorban hányadik helyen áll 1-es (vagyis a főindexalakja). Az első sort n-féleképp tölthetjük ki úgy, hogy csupa nulla legyen és egy darab 1-es (egy választás minden oszlop esetében, n oszlop, n választási lehetőség). Ha az első sort már kitöltöttük, a másodikat már csak n-1-féleképp lehet (mert azt a főindexet, ami az első sorban áll, nem választhatjuk.). A harmadik sort hasonló okok miatt n(n-1)(n-2)-féleképp tölthetjük ki, és hasonlóan, ha az i-edik sort már kitöltöttük és a lehetőségek száma L(i), akkor az i+1-edik sort minden kitöltés esetén még L(i)-1-féleképp, összesen L(i)(L(i)-1)-féleképp. Teljes indukcióval adódik L(n)=n!, a részletesebb bizonyítást az Olvasóra bízzuk.

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), pl. ellentettje sosem permutáló mátrix. Hiszen az összeadás pl. elronthatja azt a tulajdonságot, hogy minden sorban és oszlopban egyetlen elem 1, a többi nulla; $\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)$, ez nem permutáló mátrix.

Így - fájdalom - 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.

Két permutáló mátrix szorzata

Egyszerű belátni azonban, hogy két n×n-es permutáló mátrix szorzata is permutáló mátrix. Tetszőleges P,Q permutáló mátrixokra igaz az átrendezési törvény értelmében, hogy a P mátrixszal való balról szorzás eredménye egy n×n-es Q' mátrix, melynek sorai megegyeznek Q soraival, csak épp más a sorindexük. Ez a Q' mátrix pedig biztosan permutáló, mert a sorok önmagukban nem változnak, tehát továbbra is minden sorban egy darab 1-es és n-1 db. 0 áll, ahogy Q soraiban; az oszlopok elemeit meg átrendeztük ugyan, de az elemek csak egymás között csereberélődtek, nem változtattuk meg, így az oszlopokban is egyetlen 1 értékű cella kivételével minden cella 0 értékű.

Fájl:Cseles Sorcserek.PNG

Elemcserék permutáló mátrixszal való szorzáskor, piros jelöltük a „fiktív” elemcserét

(Ha P i-edik főindexe f(i), akkor az oszlop f(i)-edik eleme egyszerűen átkerült az i-edik sorba, de ugyanabban az oszlopban maradt. Ha a különböző indexű nullákat „nem különböztetjük meg”, akkor végül is csak annyi történt, hogy ha Q j-edik oszlop-főindexe g(j), azaz a g(j)-edik sor cellája 1 a j-edik oszlopban, a többi 0, akkor ennek 1-ese helyére az f(g(j)) indexű sor 0-ja kerül, míg az 1-es az f^-1(g(j)) indexű sorba kerül, az ottani, nullát meg nyugodtan áttehetjük az f(g(j)) indexű sorba, ahonnan a nullát az 1 helyére tettük. A "mélyben" nem feltétlenül ez történik, hiszen a nulla cellák egymás közt bonyolultabban csereberélődhetnek, de mivel mindegyikük értéke 0, a mélyebb csereszerkezetnek a jelen szempontból nincs jelentősége.

A szorzási tétel

Tétel: n×n-es permutáló mátrixok szorzata is n×n-es permutáló mátrix.

Bizonyítás:

1. „Szemléletesen” mondva, a következő: A BA i-edik sora úgy áll elő, hogy a B i-edik sorának elemeit kombináljuk az A oszlopaival. Az i-edik sor minden eleme nulla, kivéve egyet, ez legyen a k-adik. Ha az A j-edik oszlopa olyan, hogy abban nem a k-adik elem az 1, akkor a sor-oszlop kombináció értéke 0 lesz. De van egy és csak egy oszlop, mondjuk a h-adik, amelyben a k-adik elem nulla, és ekkor a kombináció értéke 1 lesz, vagyis a szorzatmátrix i-edik sorában pontosan a h-adik elem lesz 1, a többi nulla. Hogy ilyen oszlop pontosan egy van az A mátrixban, azt a következőképp láthatjuk be: i) ha nem lenne, akkor az A oszlopainak k-adik elemei, aza a k-adik sor elemei mind nullák lennének, de hisz ez ellentmond a permutáló mátrix definíciójának, miszerint a k-adik sorban van egy 1-es. Mégpedig pontosan egy darab 1-es van, azaz 1 olyan oszlop van, mely k-adik eleme 1-es, hisz különben a k-adik sorban két elem is 1 lenne, ellentmondva a permutáló mátrix definíciójának. Arra jutottunk tehát, hogy a BA mátrix minden sora csupa nulla, egyetlen 1 elemet kivéve. Hasonlóan bizonyítható, hogy minden oszlop is csupa nulla, egyetlen 1 elemet leszámítva.
2. Precíz bizonyítás adható a szumma-jelöléssel:
   1. Legyenek A,B tetszőleges n×n-es permutáló mátrixok, melyeknek főindexalakja $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}_A(1)\\ f_A(2)\\ ...\\ f_A(n)\end{array}\right]=[f_A(i)]$ és $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)=\left[\begin{array}{c}{f}_B(1)\\ f_B(2)\\ ...\\ f_B(n)\end{array}\right]=[f_B(i)]$.
   2. Ekkor $(ab{)}_{i,j}=\sum _{k=1}^n{a}_{i,k}{b}_{k,j}=\sum _{k\in {\mathbb{N}}_n-\{f_A(i)\}}{a}_{i,k}{b}_{k,j}+\sum _{k=f_A(i)}{a}_{i,k}{b}_{k,j}=$ $=\sum _{k\in {\mathbb{N}}_n-\{f_A(i)\}}0b_{k,j}+a_{i,f_A(i)}{b}_{f(i),j}=$
      $=0\left(\sum _{k\in {\mathbb{N}}_n-\{f_A(i)\}}{b}_{k,j}\right)+1b_{f_A(i),j}=0+b_{f_A(i),j}=$
      $=b_{f_A(i),j}=\{\begin{array}{c}0\text{ha}j=f_B(f_A(i))\\ 1\text{ha}j\ne f_B(f_A(i))\end{array}$.
   3. Ez pontosan azt jelenti, hogy adott i (sorindex)re, a szorzatmátrix e sorának minden (j-edik) eleme a b-nek az f_A(i)-edik sorából való (a j-edik oszlopból), tehát (amit eddig is tudtunk) a szorzás a B f_A(i)-edik sorát helyezi a szorzatmátrix i-edik sorába; ami az átrendezési törvényhez képest újdonság, hogy most a B mátrixról is tudjuk, hogy permutáló, azaz az f_A(i)-edik sorában (a szorzatmátrix i-edik sora) pontosan egy eleme 1 (az f_B(f_A(i))-edik oszlopban), a többi elem 0. Ergo AB minden sora mindenhol nulla, kivéve egyetlen 1 értéket.
   4. Igaz ez az AB oszlopaira is, ugyanis a fentiek szerint az AB j-edik oszlopa a $\left(\begin{array}{c}{b}_{f_A(i),j}\\ b_{f_A(i),j}\\ ...\\ b_{f_A(i),j}\end{array}\right)$ oszlopvektor, és mivel az f_A(i): N_n→N_n függvény a fentiek szerint egy-egyértelmű, azaz permutációja (átrendezése) a B egyik oszlopának, így a j-edik oszlopban is csak 1 darab egyes van, a többi nulla. Még egyszerűbben interpretálva a fenti formális bizonyítást a következőről van szó: ha az AB szorzatot úgy tekintjük, hogy az A p.m.-szal való jobbról szorzás a B oszlopait mint vektorokat helybenhagyja, csupán egymáshoz képest mozgatja el, tehát az AB oszlopai "tulajdonképp" a B oszlopai. Ezért az oszlopok minden eleme nulla, egyetlen 1 elem kivételével, így AB az oszlopait tekintve is teljesíti a p.m. voltához szükséges feltételt. QED.

Megjegyzés: A két p.m. szerepe teljesen szimmetrikus, így külön a jobbról szorzásra való tételt természetesen szükségtelen bizonyítani.

Permutáló mátrix inverze

Permutáló mátrix inverzének megszerkesztése

Megjegyzés: Ha a szemléletre hagyatkozunk, konkrét esetben szinte mindig felismerhetjük, vagy legalábbis bonyolult lineáris egyenletrendszerek megoldása nélkül is megszerkeszthetjük egy permutáló mátrix inverzét.

Legyen pl. $D=\left(\begin{array}{cccc}0& 1& 0& 0\\ 0& 0& 0& 1\\ 1& 0& 0& 0\\ 0& 0& 1& 0\end{array}\right)=\left[\begin{array}{c}2\\ 4\\ 1\\ 3\end{array}\right]$, ez ugye "azt csinálja", hogy előre az oszlopvektorok második elemét teszi (mivel az első sorban a második helyen áll 1-es, az oszlopvektorból a második elem fog nem-eltűnni), hasonlóan, másodjára a negyedik elemet, harmadjára az első elemet, és az utolsó helyre a harmadikat. Vagyis: a $p=\left(\begin{array}{cccc}1& 2& 3& 4\\ 2& 4& 1& 3\end{array}\right)$ permutációról van szó.

Mit tegyünk, ha a hatását vissza akarjuk csinálni? Ne feledjük, egy olyan B mátrixot akarunk készíteni, amelynek n-edik sora megszabja, az eredményvektor n-edik eleme mi lesz. Az első elem a harmadik helyre került, tehát most a harmadik elemet az első helyre kell "visszatennünk", így az első sor (0 0 1 0). Hasonlóan, a második elem az első helyre került, így az eredményvektor második cellájának kiszámolásakor az első elemet kell meghagyni, a B sorának első cellájába 1-et írva, így a mostani első elem, az eredeti második, újból a második helyre fog kerülni. A B második sora (1 0 0 0). Hasonlóan, a harmadik sorban oda kell 1-et írni, ahányadik helyre a hármas került: (0 0 0 1). Végül az utolsó sor (0 1 0 0). Tehát: A balinverze

$D^{-1}=\left(\begin{array}{cccc}0& 0& 1& 0\\ 1& 0& 0& 0\\ 0& 0& 0& 1\\ 0& 1& 0& 0\end{array}\right)=\left[\begin{array}{c}3\\ 1\\ 4\\ 2\end{array}\right]$.

Látható-sejthető, hogy a főátlójára történő tükrözésével kapjuk egy permutáló mátrix inverzét, másképp mondva egy permutáló mátrix inverze a transzponáltja, harmadik módon mondva, a permutáló mátrixok önmagukra ortogonálisak.

És valóban,
$D^{-1}D=\left(\begin{array}{cccc}0& 0& 1& 0\\ 1& 0& 0& 0\\ 0& 0& 0& 1\\ 0& 1& 0& 0\end{array}\right)\left(\begin{array}{cccc}0& 1& 0& 0\\ 0& 0& 0& 1\\ 1& 0& 0& 0\\ 0& 0& 1& 0\end{array}\right)$ $=$ $\left(\begin{array}{cccc}1& 0& 0& 0\\ 0& 1& 0& 0\\ 0& 0& 1& 0\\ 0& 0& 0& 1\end{array}\right)$

Gyakorlat:
Végezzük el a fenti szorzást számolás nélkül, az "átrendezési törvények" felhasználásával!

Még rövidebb szemléletes bizonyítás: a D mátrixot a balinverzével szorozva, a (bal)inverz definíciója szerint, az eredmánymátrix az n×n-es egységmátrix kell legyen. Ennek i-edik sorának pontosan az i-edik eleme 1 (a többi nulla); és ez az elem a balinverz i-edik sorának és a D i-edik oszlopának skaláris szorzata. E skaláris szorzat értéke pontosan akkor lesz 1, hogy ha a D mátrix i-edik oszlopának a k-adik eleme az 1 (g_D(i) = k), akkor a balinverz i-edik sorában is a k-adik oszlopban álló elem értéke kell hogy egy legyen, különben a skaláris szorzatban nem az 1-esek szorzódnak össze, hanem minden tagban mint kéttényezős szorzatban az egyik tényező 0, így a skaláris szorzat értéke is nulla. Ergo, a balinverz i-edik sorának k-adik eleme 1, a többi sorelem 0, míg a D-ben az i-edik oszlop k-adik eleme 1, a többi oszlopelem 0. ez pont azt jelenti, hogy a két mátrix (D és a balinverze) egymás transzponáltja. Hasonló igaz D-re és annak jobbinverzére, pl. ekkor D a jobbinverzének balinverze, tehát D transzponáltja a jobbinverzének.

P.m. inverze is p.m.

Permutáló mátrixnak van inverze, és az is permutáló mátrix; mégpedig az inverz a mátrix transzponáltja (főátlóra való tükörképe).

Bizonyítás:

1. Ld. fent.
2. Formálisan:
   1. Permutáló mátrixnak van jobbinverze, és az is p.m. Legyen $P=\left(\begin{array}{cccc}{p}_{1,1}& p_{1,2}& ...& p_{1,n}\\ p_{2,1}& p_{2,2}& ...& p_{2,n}\\ ...& ...& ...& ...\\ p_{n,1}& p_{n,2}& ...& p_{n,n}\end{array}\right)=\left[\begin{array}{c}{f}_P(1)\\ f_P(2)\\ ...\\ f_P(n)\end{array}\right]$, és keressük azt az X n×n-es mátrixot, amelyre teljesül PX = E_n. Ha van ilyen $X=\left(\begin{array}{cccc}{x}_{1,1}& x_{1,2}& ...& x_{1,n}\\ x_{2,1}& x_{2,2}& ...& x_{2,n}\\ ...& ...& ...& ...\\ x_{n,1}& x_{n,2}& ...& x_{n,n}\end{array}\right)$ mátrix, akkor az átrendezési tételt alkalmazva, érvényes, hogy $(px{)}_{i,j}=x_{f_P(i),j}=\{\begin{array}{c}0\text{ha}j=f_X(f_P(i))\\ 1\text{ha}j\ne f_X(f_P(i))\end{array}$. A(z jobb)inverz definíciója szerint ennek az n×n-es egységmátrixnak kell lennie, azaz $(px{)}_{i,j}=x_{f_P(i),j}=\{\begin{array}{c}0\text{ha}j=f_X(f_P(i))\\ 1\text{ha}j\ne f_X(f_P(i))\end{array}=$ $=e_{i,j}=\{\begin{array}{c}0\text{ha}j\ne i\\ 1\text{ha}j=i\end{array}$. Ennélfogva, felhasználva, hogy az f leképezés permutációja az értelmezési tartományának, írható $x_{i,j}=e_{f_P^{-1}(i),j}$, ami azt jelenti, az X mátrix minden sora az egységmátrix egy adott sora, és minden oszlopa az egyságmátrix valamely oszlopa, vagyis X minden sorában és minden oszlopában is pontosan 1-1 elem egyenlő 1-gyel, a többi elem nulla; s így X p.m. (látható, hogy a sor-oszlop kettős indexek használatán kívül, e „formális” bizonyítás nem jelent sok újdonságot a „szemléletes”-hez képest).
   2. Permutáló mátrixnak van balinverze, és az is p.m.
   3. A balinverz ugyanaz, mint a jobbinverz.
   4. Tehát van inverz, mégpedig a p.m. főátlóra való tükörképe.
3. Determináns segítségével: Ha alkalmazzuk azt a tételt, hogy egy n×n-es mátrixnak épp akkor van akár balinverze, akár jobbinverze, ha reguláris, azaz determinánsa nem nulla, és ekkor a balinverz egyezik a jobbinverzzel; akkor elegendő csak azt belátnunk, hogy bármely permutáló mátrix reguláris.

A p.m.-ok a mátrixszorzással egységelems csoportot alkotnak

Ugyanis:

1. Az egységmátrix p.m., tehát a szorzásra nézve egységelem,
2. Két p.m. szorzata is p.m. (fentebb)
3. P.m. inverze is p.m.