Permutáló mátrix

A Wikipédiából, a szabad lexikonból.

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.

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.

Tartalomjegyzék

1 Példák
2 Főindex
3 A permutáló mátrix átrendezi az elemeket
4 A permutáló mátrixok csoportja
5 Külső hivatkozások

[szerkesztés] 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}$

[szerkesztés] Főindex

A fentiek szerint egy P permutáló mátrix minden i sorindenxhez 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(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, pl. az A permutáló mátrix i-edik (sor-)főindexe f_A(i).

[szerkesztés] 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 a(z XP) szorzatmátrix j-oszlopa sora 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}$

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

$B p 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:

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

[szerkesztés] 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, pl. $\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.