Permutační matice

V matematice se permutační maticí nazývá čtvercová matice, ve které má každý řádek i sloupec jen jednu nenulovou hodnotu a to jedničku. Permutační matice reprezentují permutace konečné množiny. Pokud je permutační matice vynásobena vektorem, pak se složky vektoru přerovnají podle této permutace. Permutační matice jsou ortogonální, dvojitě stochastické a celočíselné unimodulární. Množina permutačních matic daného řádu tvoří podgrupu obecné lineární grupy vzhledem k součinu matic. Permutační matice se používají v lineární algebře, kombinatorice a kryptografii.

Definice

Permutační matice je čtvercová matice, ve které je právě jeden prvek v každém řádku a v každém sloupci roven jedné a všechny ostatní prvky jsou rovny nule. Obecně jsou $1$ a $0$ jednotkový prvek a nulový prvek příslušného tělesa $T$ , obvykle tělesa reálných čísel. Permutační matice řádu $n$ odpovídá permutaci $(\pi (1),\ldots ,\pi (n))$ na množině $\{1,\ldots ,n\}$ . Pro permutaci $\pi \in S_{n}$ je příslušná permutační matice

{\boldsymbol {P}}_{\pi }\in T^{n\times n}

definována po složkách

{\boldsymbol {P}}_{ij}=\delta _{\pi (i),j}={\begin{cases}1,&{\text{pokud }}\pi (i)=j\\0,&{\text{jinak,}}\end{cases}}

kde $\delta _{ij}$ značí Kroneckerovo delta.

Permutační matici lze také definovat pomocí vektorů přirozené báze ${\boldsymbol {e}}_{1},\ldots {\boldsymbol {e}}_{n}$ (standardně sloupcových). Permutační matice ${\boldsymbol {P}}_{\pi }$ je pak daná po řádcích:

{\boldsymbol {P}}_{\pi }={\begin{pmatrix}{\boldsymbol {e}}_{\pi (1)}^{\mathrm {T} }\\\vdots \\{\boldsymbol {e}}_{\pi (n)}^{\mathrm {T} }\end{pmatrix}}

Ukázka

Permutaci

\pi ={\begin{pmatrix}1&2&3&4\\4&1&3&2\\\end{pmatrix}}\in S_{4}

přísluší permutační matice:

{\boldsymbol {P}}_{\pi }={\begin{pmatrix}{\boldsymbol {e}}_{4}^{\mathrm {T} }\\{\boldsymbol {e}}_{1}^{\mathrm {T} }\\{\boldsymbol {e}}_{3}^{\mathrm {T} }\\{\boldsymbol {e}}_{2}^{\mathrm {T} }\end{pmatrix}}={\begin{pmatrix}0&0&0&1\\1&0&0&0\\0&0&1&0\\0&1&0&0\end{pmatrix}}\in T^{4\times 4}

Například obrazem čísla $1$ v permutaci $\pi$ je číslo $4$ , a proto má ${\boldsymbol {P}}_{\pi }$ v prvním řádku jedničku až ve čtvrtém sloupci.

{\boldsymbol {P}}_{\pi }\cdot (1,2,3,4)^{\mathrm {T} }=(4,1,3,2)^{\mathrm {T} }

Použití

Je-li permutační matice vynásobena sloupcovým vektorem ${\boldsymbol {v}}=(v_{1},\ldots ,v_{n})^{\mathrm {T} }$ , pak výsledkem je sloupcový vektor, jehož prvky byly přerovnány podle permutace $\pi$ :

{\boldsymbol {P}}_{\pi }{\boldsymbol {v}}={\begin{pmatrix}{\boldsymbol {e}}_{\pi (1)}^{\mathrm {T} }\\\vdots \\{\boldsymbol {e}}_{\pi (n)}^{\mathrm {T} }\end{pmatrix}}{\begin{pmatrix}v_{1}\\\vdots \\v_{n}\end{pmatrix}}={\begin{pmatrix}v_{\pi (1)}\\\vdots \\v_{\pi (n)}\end{pmatrix}}

Podobně součin matice ${\boldsymbol {M}}$ s permutační maticí ${\boldsymbol {P}}_{\pi }$ zleva dá matici ${\boldsymbol {P}}_{\pi }{\boldsymbol {M}}$ , jež obsahuje řádky matice ${\boldsymbol {M}}$ přerovnané podle permutace $\pi$ .

(1,2,3,4){\boldsymbol {P}}_{\pi }=(2,4,3,1)

Analogický vztah platí pro součin řádkového vektoru s transpozicí permutační matice zprava:

$v^{\mathrm {T} }{\boldsymbol {P}}_{\pi }^{\mathrm {T} }=(v_{1},\ldots ,v_{n})\left({\boldsymbol {e}}_{\pi (1)}^{\mathrm {T} },\ldots ,{\boldsymbol {e}}_{\pi (n)}^{\mathrm {T} }\right)=(v_{\pi (1)},\ldots ,v_{\pi (n)})$

Vzhledem k tomu, že permutační matice je ortogonální, platí, že když se matice ${\boldsymbol {M}}$ vynásobí permutační maticí zprava, jsou v součinu ${\boldsymbol {MP}}_{\pi }$ přerovnané sloupce matice ${\boldsymbol {M}}$ podle inverzní permutace $\pi ^{-1}$ .

Vlastnosti

Tabulka grupy po 3! = 6 permutací tříprvkové množiny. Součin dvou permutačních matic je opět permutační matice.

Pozice 6 matic v grupové tabulce výše. Pouze jednotkové matice jsou symetrické kolem hlavní diagonály, takže symetrická grupa není abelovská. Jedná se také o permutační matice řádu 6, proto jsou znázorněné i odpovídající cykly.

Inverze

Permutační matice je vždy regulární, přičemž inverzí permutační matice je její transpozice. Transponovaná matice je permutační maticí inverzní permutace, takže platí:

{\boldsymbol {P}}_{\pi }^{-1}={\boldsymbol {P}}_{\pi }^{\mathrm {T} }={\boldsymbol {P}}_{\pi ^{-1}}

Reálné permutační matice jsou proto vždy ortogonální. Permutační matice mají plnou hodnost $n$ .

Součin

Součin dvou permutačních matic je opět permutační matice, která odpovídá složení příslušných permutací. Permutační matice složení dvou permutací $\pi ,\sigma \in S_{n}$ je:

{\boldsymbol {P}}_{\pi \circ \sigma }={\boldsymbol {P}}_{\pi }{\boldsymbol {P}}_{\sigma }

Zobrazení $\pi \mapsto {\boldsymbol {P}}_{\pi }$ tedy představuje homomorfismus. Množina permutačních matic spolu s násobením matic tvoří grupu, konkrétně podgrupu obecné lineární grupy $\mathrm {GL} (n,T)$ . Vzhledem k tomu, že každou permutaci lze rozložit na transpozice, může být libovolná permutační matice získána jako součin elementárních matic odpovídajících záměnám dvou řádků.

Mocniny

Celočíselné mocniny permutačních matic jsou opět permutační matice. Pro libovolnou permutační matici ${\boldsymbol {P}}_{\pi }$ existuje celočíselná mocnina $k$ taková, že platí:

{\boldsymbol {P}}_{\pi }^{k}=\mathbf {I}

,

kde $\mathbf {I}$ je jednotková matice odpovídajícího řádu. Nejmenší kladné $k$ s touto vlastností se rovná řádu prvku ${\boldsymbol {P}}_{\pi }$ v obecné lineární grupě. Uvedená mocnina $k$ je rovna nejmenšímu společnému násobku délek disjunktních cyklů v permutaci $\pi$ .

Determinant

Determinant permutační matice je buď $+1$ nebo $-1$ a odpovídá znaménku související permutace:

\det {\boldsymbol {P}}_{\pi }=\operatorname {sgn} (\pi )

Celočíselná permutační matice unimodulární. Stopa celočíselné permutační matice odpovídá počtu pevných bodů permutace.

Determinant permutační matice lze určit pomocí následujícího schématu, ve kterém je počítán počet inverzí příslušné permutace $\pi$ . Vychází z tabulky permutace, kde pro každý řádek matice je v tabulce zapsáno číslo sloupce obsahující jedničku v daném sloupci. Pod tím je pro každé číslo $j=\pi (i)$ ve druhém řádku zapsán počet čísel, která jsou větší než $j$ a jsou v tabulce vlevo od $j$ ; toto číslo $a_{i}$ odpovídá počtu inverzí, jichž se $j$ účastní.

Pro permutační matici $8\times 8$ pro permutaci $(3,5,8,1,7,4,2,6)$ uvedené v úvodu jde o tabulku:

Řádek	$i$	1	2	3	4	5	6	7	8
Číslo sloupce s 1	${\textstyle \pi (i)}$	3	5	8	1	7	4	2	6
Počet inverzí	$a_{i}$	0	0	0	3	1	3	5	2

Je-li celkový počet inverzí sudé číslo, jako zde, pak je determinant 1, jinak −1. Odpovídající vzorec pro permutační maticí řádu $n$ pak je: $\det {\boldsymbol {P}}_{\pi }=(-1)^{\sum \limits _{i=1}^{n}a_{i}}$

Vlastní čísla

Vlastní čísla reálné permutační matice nejsou nutně všechny reálná, ale leží na komplexní jednotkové kružnici. Jsou-li $l_{1},\ldots ,l_{s}$ délky cyklů permutace $\pi$ , pak vlastní čísla související permutační matice ${\boldsymbol {P}}_{\pi }$ jsou komplexní jednotky:

\lambda _{jk}=e^{2\pi \mathrm {i} k/l_{j}}

pro $j=1,\ldots ,s$ a $k=1,\ldots ,l_{j}$ . Reálná permutační matice má tedy vlastní číslo $e^{2\pi \mathrm {i} k/m}$ , právě když $k$ a $m$ jsou nesoudělná čísla a odpovídající permutace $\pi$ má alespoň jeden cyklus délky dělitelné $m$ . Násobnost tohoto vlastního čísla pak odpovídá počtu takových cyklů. Reálná permutační matice má proto vždy vlastní číslo $1$ s násobnosti rovné celkovému počtu cyklů $s$ odpovídající permutace $\pi$ .

Norma

Protože reálné permutační matice jsou ortogonální, platí pro jejich spektrální normu:

\|{\boldsymbol {P}}_{\pi }\|_{2}=1

Norma součtu sloupců a řádků reálné permutační matice je:

\|{\boldsymbol {P}}_{\pi }\|_{1}=\|{\boldsymbol {P}}_{\pi }\|_{\infty }=1

Reálná permutační matice je tedy dvojitě stochastická matice. Podle Birkhoffovy–von Neumannovy věty je čtvercová matice dvojitě stochastická právě tehdy, když se jedná o konvexní kombinaci permutačních matic.

Speciální případy

Permutační maticí identické permutace je jednotková matice .
Permutační matice je symetrická, právě když je základní permutace sama involucí, neboli sama k sobě inverzní.
Jestliže má permutační matice blokovou strukturu, pak základní permutaci lze reprezentovat jako součet permutací.

Aplikace

	a	b	c	d	e	f	g	h
8									8
7									7
6									6
5									5
4									4
3									3
2									2
1									1
	a	b	c	d	e	f	g	h

Osm věží na šachovnici, které se navzájem neohrožují. Jsou rozestavěny podle permutace (3,5,8,1,7,4,2,6) z úvodního obrázku.

Permutační matice se používají mimo jiné:

V lineární algebře jako elementární matice v Gaussově eliminaci k řešení soustav lineárních rovnic,
v kombinatorice v maticové reprezentaci permutačních grup,
v kryptografii jako součásti procedur blokového šifrování.

V šachové matematice tvoří permutační matice přesně řešení problému, $n$ věží. Ty mají být rozmístěny na šachovnici velikosti $n\times n$ tak, aby se navzájem neohrožovaly. Obtížněji řešitelný je problém osmi dam, ve kterém jsou věže nahrazeny dámami, které se mohou pohybovat i diagonálně. Řešením problému osmi dam jsou také permutační matice.

Zobecnění

Monomiální matice

Zobecněná permutační matice nebo monomiální matice je čtvercová matice ${\boldsymbol {G}}\in R^{n\times n}$ , kde v každém sloupci i řádku je právě jeden nenulový prvek. Monomiální matice mají rozklad

{\boldsymbol {G}}={\boldsymbol {P}}{\boldsymbol {D}}

,

kde ${\boldsymbol {P}}\in T^{n\times n}$ je permutační matice a ${\boldsymbol {D}}\in T^{n\times n}$ je diagonální matice, jejíž diagonální prvky jsou všechny nenulové prvky matice ${\boldsymbol {G}}$ . Regulární monomiální matice s maticovým násobením coby grupovou operací tvoří monomiální grupu $\operatorname {M} (n,R)$ , což je další podgrupa obecné lineární grupy $\operatorname {GL} (n,R)$ . Speciální monomiální matice jsou permutační matice se znaménky, neboli matice, ve kterých je v každém řádku i sloupci právě jeden prvek roven $+1$ nebo $-1$ je a všechny ostatní položky jsou rovny $0$ .

Odkazy

Reference

V tomto článku byly použity překlady textů z článků Permutationsmatrix na německé Wikipedii a Permutation matrix na anglické Wikipedii.

Literatura

HLADÍK, Milan. Lineární algebra (nejen) pro informatiky. 1.. vyd. Praha: Matfyzpress, 2019. 328 s. ISBN 978-80-7378-378-5. S. 39.
OLŠÁK, Petr. Lineární algebra [online]. Praha: 2007 [cit. 2023-02-20]. Dostupné online.

Související články

Levi-Civitův symbol

Externí odkazy

Obrázky, zvuky či videa k tématu permutační matice na Wikimedia Commons
Permutation Matrix v encyklopedii MathWorld (anglicky)