Permutační matice
![](http://upload.wikimedia.org/wikipedia/commons/1/16/HuitRois.png)
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 a jednotkový prvek a nulový prvek příslušného tělesa , obvykle tělesa reálných čísel. Permutační matice řádu odpovídá permutaci na množině . Pro permutaci je příslušná permutační matice
definována po složkách
kde značí Kroneckerovo delta.
Permutační matici lze také definovat pomocí vektorů přirozené báze (standardně sloupcových). Permutační matice je pak daná po řádcích:
Ukázka
Permutaci
přísluší permutační matice:
Například obrazem čísla v permutaci je číslo , a proto má v prvním řádku jedničku až ve čtvrtém sloupci.
![](http://upload.wikimedia.org/wikipedia/commons/thumb/2/2d/Permutation_matrix%3B_P_%2A_column.svg/180px-Permutation_matrix%3B_P_%2A_column.svg.png)
Použití
Je-li permutační matice vynásobena sloupcovým vektorem , pak výsledkem je sloupcový vektor, jehož prvky byly přerovnány podle permutace :
Podobně součin matice s permutační maticí zleva dá matici , jež obsahuje řádky matice přerovnané podle permutace .
![](http://upload.wikimedia.org/wikipedia/commons/thumb/a/a3/Permutation_matrix%3B_row_%2A_P.svg/257px-Permutation_matrix%3B_row_%2A_P.svg.png)
Analogický vztah platí pro součin řádkového vektoru s transpozicí permutační matice zprava:
Vzhledem k tomu, že permutační matice je ortogonální, platí, že když se matice vynásobí permutační maticí zprava, jsou v součinu přerovnané sloupce matice podle inverzní permutace .
Vlastnosti
![](http://upload.wikimedia.org/wikipedia/commons/thumb/e/e0/Symmetric_group_3%3B_Cayley_table%3B_matrices.svg/220px-Symmetric_group_3%3B_Cayley_table%3B_matrices.svg.png)
![](http://upload.wikimedia.org/wikipedia/commons/thumb/c/cb/Symmetric_group_3%3B_Cayley_table%3B_positions.svg/220px-Symmetric_group_3%3B_Cayley_table%3B_positions.svg.png)
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í:
Reálné permutační matice jsou proto vždy ortogonální. Permutační matice mají plnou hodnost .
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í je:
Zobrazení 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 . 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 existuje celočíselná mocnina taková, že platí:
- ,
kde je jednotková matice odpovídajícího řádu. Nejmenší kladné s touto vlastností se rovná řádu prvku v obecné lineární grupě. Uvedená mocnina je rovna nejmenšímu společnému násobku délek disjunktních cyklů v permutaci .
Determinant
Determinant permutační matice je buď nebo a odpovídá znaménku související permutace:
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 . 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 ve druhém řádku zapsán počet čísel, která jsou větší než a jsou v tabulce vlevo od ; toto číslo odpovídá počtu inverzí, jichž se účastní.
Pro permutační matici pro permutaci uvedené v úvodu jde o tabulku:
Řádek | 1 | 2 | 3 | 4 | 5 | 6 | 7 | 8 | |
---|---|---|---|---|---|---|---|---|---|
Číslo sloupce s 1 | 3 | 5 | 8 | 1 | 7 | 4 | 2 | 6 | |
Počet inverzí | 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 pak je:
Vlastní čísla
Vlastní čísla reálné permutační matice nejsou nutně všechny reálná, ale leží na komplexní jednotkové kružnici. Jsou-li délky cyklů permutace , pak vlastní čísla související permutační matice jsou komplexní jednotky:
pro a . Reálná permutační matice má tedy vlastní číslo , právě když a jsou nesoudělná čísla a odpovídající permutace má alespoň jeden cyklus délky dělitelné . 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 s násobnosti rovné celkovému počtu cyklů odpovídající permutace .
Norma
Protože reálné permutační matice jsou ortogonální, platí pro jejich spektrální normu:
Norma součtu sloupců a řádků reálné permutační matice je:
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 |
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, věží. Ty mají být rozmístěny na šachovnici velikosti 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 , kde v každém sloupci i řádku je právě jeden nenulový prvek. Monomiální matice mají rozklad
- ,
kde je permutační matice a je diagonální matice, jejíž diagonální prvky jsou všechny nenulové prvky matice . Regulární monomiální matice s maticovým násobením coby grupovou operací tvoří monomiální grupu , což je další podgrupa obecné lineární grupy . 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 nebo je a všechny ostatní položky jsou rovny .
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
Externí odkazy
Obrázky, zvuky či videa k tématu permutační matice na Wikimedia Commons
- Permutation Matrix v encyklopedii MathWorld (anglicky)