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.

Permutační matice permutace (3,5,8,1,7,4,2,6). Červené tečky označují jedničky.

Definice

editovat

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

editovat

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.

 
 

Použití

editovat

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  .

 
 

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

editovat
 
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

editovat

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

editovat

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

editovat

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

editovat

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

editovat

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  .

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

editovat

Aplikace

editovat
abcdefgh
88
77
66
55
44
33
22
11
abcdefgh
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 š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í

editovat

Monomiální matice

editovat

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  .

Reference

editovat

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

editovat
  • 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

editovat

Externí odkazy

editovat