Znaménko permutace

Znaménko permutace (značené obvykle jako sgn(σ), též označováno jako parita permutace) je charakteristika konkrétní permutace (seřazení množiny čísel), která vyjadřuje, zda je počet inverzí této permutace (počet prvků prohozených oproti seřazené posloupnosti) sudý či lichý. Vyjadřuje se čísly ±1 či pouze příslušným znaménkem +/-: sudý počet inverzí odpovídá kladnému znaménku, lichý zápornému. Tuto vlastnost lze zapsat tak, že

sgn(σ) = (−1)ⁿ,

kde n je počet inverzí permutace, nebo počet cyklů sudé délky^[1].

Definice inverze

Inverze v permutaci p je dvojice prvků a, b taková, že a < b a zároveň p(a) > p(b).

Příklad

Permutaci si lze představit jako dvouřádkovou matici:

${\displaystyle {\begin{pmatrix}a&b&c&d\\\sigma (a)&\sigma (b)&\sigma (c)&\sigma (d)\end{pmatrix}}}$

např. matice

${\displaystyle {\begin{pmatrix}1&2&3&4\\1&2&3&4\end{pmatrix}}}$

má počet inverzí 0, proto bude znaménko +. Pro jinou permutaci

${\displaystyle {\begin{pmatrix}1&2&3&4\\2&3&1&4\end{pmatrix}}}$

platí:

${\displaystyle 1<2<3<4;(1<3;1<4;2<4)}$, potom permutace:

${\displaystyle 2<3>1<4;(2>1;3>1)}$ - obě inverze jsou uvedené v závorce

má dvě inverze a znaménko bude +.

Alternativní výpočet

Znaménko permutace lze také vypočítat tak, že za n ve vzorci dosadíme počet cyklů sudé délky.

Permutaci zapsanou ve formě matice:

${\displaystyle {\begin{pmatrix}1&2&3&4\\2&3&1&4\end{pmatrix}}}$

lze také zapsat pomocí cyklů:

${\displaystyle (1,2,3)(4)}$

Ze zápisu pomocí cyklů vidíme, že počet cyklů sudé délky je roven 0. Dosadíme tedy do vzorce:

sgn(σ) = (−1)⁰ = 1

výsledek je kladný, znaménko je tedy +.

Vlastnosti

Jsou-li ${\displaystyle \pi _{1}}$ a ${\displaystyle \pi _{2}}$ dvě permutace na množině ${\displaystyle M}$, pak znaménko permutace jejich složení je rovno součinu znamének jednotlivých permutací, tedy

${\displaystyle \operatorname {sgn} {(\pi _{1}\circ \pi _{2})}={\operatorname {sgn}(\pi _{1})}\;{\operatorname {sgn}(\pi _{2})}}$

Znaménko inverzní permutace je určeno jako

${\displaystyle \operatorname {sgn} \pi ^{-1}=\operatorname {sgn} \pi }$

Je-li permutace ${\displaystyle \pi }$ součinem nezávislých cyklů ${\displaystyle \pi =\pi _{1}\circ \pi _{2}\circ ...\circ \pi _{m}}$, kde každý z cyklů ${\displaystyle \pi _{i}}$ má délku ${\displaystyle k_{i}+1}$, pak

${\displaystyle \operatorname {sgn} \pi =\Pi _{i=1}^{m}{(-1)}^{k_{i}}={(-1)}^{\sum _{i=1}^{m}k_{i}}}$

Reference

Související články

• Patnáctka
• Transpozice (algebra)
• Funkce signum
• Levi-Civitův symbol