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

• Témák jegyzéke
• Előző fejezet (?)
• Következő fejezet (Permutáló mátrixok II.)

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

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

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{matrix}1&2&...&n\\\pi (1)&\pi (2)&...&\pi (n)\end{matrix}}\right)$, még rövidebben csak így: $\left({\begin{matrix}\pi (1)&\pi (2)&...&\pi (n)\end{matrix}}\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:={\begin{bmatrix}f(1)\\f(2)\\...\\f(n)\end{bmatrix}}\ =\ \left[f(i)\right]\$
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\ :=\ {\begin{pmatrix}0&1\\1&0\end{pmatrix}}\ =\ {\begin{bmatrix}2\\1\end{bmatrix}}$       $E\ :=\ {\begin{pmatrix}0&1&0\\0&0&1\\1&0&0\end{pmatrix}}\ =\ {\begin{bmatrix}2\\3\\1\end{bmatrix}}$

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

$E_{n}\ =\ {\begin{pmatrix}1&0&...&0&0\\0&1&...&0&0\\...&...&...&...&...\\0&0&...&1&0\\\\0&0&...&0&1\end{pmatrix}}\ =\ {\begin{bmatrix}1\\2\\...\\n-1\\n\end{bmatrix}}\ =\ {\begin{bmatrix}i\end{bmatrix}}$

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\ :=\ {\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)}$, 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; ${\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 - 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ű.

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\ :=\ {\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_{A}(1)\\f_{A}(2)\\...\\f_{A}(n)\end{bmatrix}}\ =\ \left[f_{A}(i)\right]$ és $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}}\ =\ {\begin{bmatrix}f_{B}(1)\\f_{B}(2)\\...\\f_{B}(n)\end{bmatrix}}\ =\ \left[f_{B}(i)\right]$.
   2. Ekkor $(ab)_{i,j}\ =\ \sum _{k=1}^{n}a_{i,k}b_{k,j}\ =\sum _{k\in \mathbb {N} _{n}-\left\{f_{A}(i)\right\}}a_{i,k}b_{k,j}+\sum _{k=f_{A}(i)}a_{i,k}b_{k,j}\ =\$ $\ =\sum _{k\in \mathbb {N} _{n}-\left\{f_{A}(i)\right\}}0b_{k,j}+a_{i,f_{A}(i)}b_{f(i),j}\ =$
      $=\ 0\left(\sum _{k\in \mathbb {N} _{n}-\left\{f_{A}(i)\right\}}b_{k,j}\right)+1b_{f_{A}(i),j}\ =\ 0+b_{f_{A}(i),j}\ =$
      $=\ b_{f_{A}(i),j}\ =\ {\begin{cases}0\ {\mbox{ha}}\ j=f_{B}(f_{A}(i))\\1\ {\mbox{ha}}\ j\neq f_{B}(f_{A}(i))\end{cases}}$.
   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 ${\begin{pmatrix}b_{f_{A}(i),j}\\b_{f_{A}(i),j}\\...\\b_{f_{A}(i),j}\end{pmatrix}}$ 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\ =\ {\begin{pmatrix}0&1&0&0\\0&0&0&1\\1&0&0&0\\0&0&1&0\\\end{pmatrix}}\ =\ {\begin{bmatrix}2\\4\\1\\3\end{bmatrix}}$, 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\ =\ {\begin{pmatrix}1&2&3&4\\2&4&1&3\end{pmatrix}}$ 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}\ =\ {\begin{pmatrix}0&0&1&0\\1&0&0&0\\0&0&0&1\\0&1&0&0\\\end{pmatrix}}\ =\ {\begin{bmatrix}3\\1\\4\\2\end{bmatrix}}$.

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

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\ =\ {\begin{pmatrix}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{pmatrix}}\ =\ {\begin{bmatrix}f_{P}(1)\\f_{P}(2)\\...\\f_{P}(n)\end{bmatrix}}$, és keressük azt az X n×n-es mátrixot, amelyre teljesül PX = E_n. Ha van ilyen $X\ =\ {\begin{pmatrix}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{pmatrix}}$ mátrix, akkor az átrendezési tételt alkalmazva, érvényes, hogy $(px)_{i,j}\ =\ x_{f_{P}(i),j}\ =\ {\begin{cases}0\ {\mbox{ha}}\ j=f_{X}(f_{P}(i))\\1\ {\mbox{ha}}\ j\neq f_{X}(f_{P}(i))\end{cases}}$. 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{cases}0\ {\mbox{ha}}\ j=f_{X}(f_{P}(i))\\1\ {\mbox{ha}}\ j\neq f_{X}(f_{P}(i))\end{cases}}\ =$ $=\ e_{i,j}\ =\ {\begin{cases}0\ {\mbox{ha}}\ j\neq i\\1\ {\mbox{ha}}\ j=i\end{cases}}$. 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.