Severity: Notice
Message: Undefined offset: 1
Filename: infosekolah/leftmenudasboard.php
Line Number: 33
Line Number: 34
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 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 {\displaystyle 1} a 0 {\displaystyle 0} jednotkový prvek a nulový prvek příslušného tělesa T {\displaystyle T} , obvykle tělesa reálných čísel. Permutační matice řádu n {\displaystyle n} odpovídá permutaci ( π ( 1 ) , … , π ( n ) ) {\displaystyle (\pi (1),\ldots ,\pi (n))} na množině { 1 , … , n } {\displaystyle \{1,\ldots ,n\}} . Pro permutaci π ∈ S n {\displaystyle \pi \in S_{n}} je příslušná permutační matice
definována po složkách
kde δ i j {\displaystyle \delta _{ij}} značí Kroneckerovo delta.
Permutační matici lze také definovat pomocí vektorů přirozené báze e 1 , … e n {\displaystyle {\boldsymbol {e}}_{1},\ldots {\boldsymbol {e}}_{n}} (standardně sloupcových). Permutační matice P π {\displaystyle {\boldsymbol {P}}_{\pi }} je pak daná po řádcích:
Permutaci
přísluší permutační matice:
Například obrazem čísla 1 {\displaystyle 1} v permutaci π {\displaystyle \pi } je číslo 4 {\displaystyle 4} , a proto má P π {\displaystyle {\boldsymbol {P}}_{\pi }} v prvním řádku jedničku až ve čtvrtém sloupci.
Je-li permutační matice vynásobena sloupcovým vektorem v = ( v 1 , … , v n ) T {\displaystyle {\boldsymbol {v}}=(v_{1},\ldots ,v_{n})^{\mathrm {T} }} , pak výsledkem je sloupcový vektor, jehož prvky byly přerovnány podle permutace π {\displaystyle \pi } :
Podobně součin matice M {\displaystyle {\boldsymbol {M}}} s permutační maticí P π {\displaystyle {\boldsymbol {P}}_{\pi }} zleva dá matici P π M {\displaystyle {\boldsymbol {P}}_{\pi }{\boldsymbol {M}}} , jež obsahuje řádky matice M {\displaystyle {\boldsymbol {M}}} přerovnané podle permutace π {\displaystyle \pi } .
Analogický vztah platí pro součin řádkového vektoru s transpozicí permutační matice zprava:
v T P π T = ( v 1 , … , v n ) ( e π ( 1 ) T , … , e π ( n ) T ) = ( v π ( 1 ) , … , v π ( n ) ) {\displaystyle 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 M {\displaystyle {\boldsymbol {M}}} vynásobí permutační maticí zprava, jsou v součinu M P π {\displaystyle {\boldsymbol {MP}}_{\pi }} přerovnané sloupce matice M {\displaystyle {\boldsymbol {M}}} podle inverzní permutace π − 1 {\displaystyle \pi ^{-1}} .
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 n {\displaystyle n} .
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í π , σ ∈ S n {\displaystyle \pi ,\sigma \in S_{n}} je:
Zobrazení π ↦ P π {\displaystyle \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 G L ( n , T ) {\displaystyle \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ů.
Celočíselné mocniny permutačních matic jsou opět permutační matice. Pro libovolnou permutační matici P π {\displaystyle {\boldsymbol {P}}_{\pi }} existuje celočíselná mocnina k {\displaystyle k} taková, že platí:
kde I {\displaystyle \mathbf {I} } je jednotková matice odpovídajícího řádu. Nejmenší kladné k {\displaystyle k} s touto vlastností se rovná řádu prvku P π {\displaystyle {\boldsymbol {P}}_{\pi }} v obecné lineární grupě. Uvedená mocnina k {\displaystyle k} je rovna nejmenšímu společnému násobku délek disjunktních cyklů v permutaci π {\displaystyle \pi } .
Determinant permutační matice je buď + 1 {\displaystyle +1} nebo − 1 {\displaystyle -1} 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 π {\displaystyle \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 = π ( i ) {\displaystyle j=\pi (i)} ve druhém řádku zapsán počet čísel, která jsou větší než j {\displaystyle j} a jsou v tabulce vlevo od j {\displaystyle j} ; toto číslo a i {\displaystyle a_{i}} odpovídá počtu inverzí, jichž se j {\displaystyle j} účastní.
Pro permutační matici 8 × 8 {\displaystyle 8\times 8} pro permutaci ( 3 , 5 , 8 , 1 , 7 , 4 , 2 , 6 ) {\displaystyle (3,5,8,1,7,4,2,6)} uvedené v úvodu jde o tabulku:
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 {\displaystyle n} pak je: det P π = ( − 1 ) ∑ i = 1 n a i {\displaystyle \det {\boldsymbol {P}}_{\pi }=(-1)^{\sum \limits _{i=1}^{n}a_{i}}}
Vlastní čísla reálné permutační matice nejsou nutně všechny reálná, ale leží na komplexní jednotkové kružnici. Jsou-li l 1 , … , l s {\displaystyle l_{1},\ldots ,l_{s}} délky cyklů permutace π {\displaystyle \pi } , pak vlastní čísla související permutační matice P π {\displaystyle {\boldsymbol {P}}_{\pi }} jsou komplexní jednotky:
pro j = 1 , … , s {\displaystyle j=1,\ldots ,s} a k = 1 , … , l j {\displaystyle k=1,\ldots ,l_{j}} . Reálná permutační matice má tedy vlastní číslo e 2 π i k / m {\displaystyle e^{2\pi \mathrm {i} k/m}} , právě když k {\displaystyle k} a m {\displaystyle m} jsou nesoudělná čísla a odpovídající permutace π {\displaystyle \pi } má alespoň jeden cyklus délky dělitelné m {\displaystyle 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 {\displaystyle 1} s násobnosti rovné celkovému počtu cyklů s {\displaystyle s} odpovídající permutace π {\displaystyle \pi } .
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.
Permutační matice se používají mimo jiné:
V šachové matematice tvoří permutační matice přesně řešení problému, n {\displaystyle n} věží. Ty mají být rozmístěny na šachovnici velikosti n × n {\displaystyle 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á permutační matice nebo monomiální matice je čtvercová matice G ∈ R n × n {\displaystyle {\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
kde P ∈ T n × n {\displaystyle {\boldsymbol {P}}\in T^{n\times n}} je permutační matice a D ∈ T n × n {\displaystyle {\boldsymbol {D}}\in T^{n\times n}} je diagonální matice, jejíž diagonální prvky jsou všechny nenulové prvky matice G {\displaystyle {\boldsymbol {G}}} . Regulární monomiální matice s maticovým násobením coby grupovou operací tvoří monomiální grupu M ( n , R ) {\displaystyle \operatorname {M} (n,R)} , což je další podgrupa obecné lineární grupy GL ( n , R ) {\displaystyle \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 {\displaystyle +1} nebo − 1 {\displaystyle -1} je a všechny ostatní položky jsou rovny 0 {\displaystyle 0} .
V tomto článku byly použity překlady textů z článků Permutationsmatrix na německé Wikipedii a Permutation matrix na anglické Wikipedii.
