Znaménko permutace

Z Wikipedie, otevřené encyklopedie
Skočit na: Navigace, Hledání

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)n,

kde n je počet inverzí.

Definice inverze[editovat | editovat zdroj]

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

Příklad[editovat | editovat zdroj]

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

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

např. matice

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

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

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

platí:

1<2<3<4; (1<2;1<3), potom permutace:
2<3>1<4; (2>1;3>1)

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

Vlastnosti[editovat | editovat zdroj]

Jsou-li \pi_1 a \pi_2 dvě permutace na množině M, pak znaménko permutace jejich složení je rovno součinu znamének jednotlivých permutací, tedy

\sgn {(\pi_1 \circ \pi_2)} = {\sgn (\pi_1)}\;{\sgn (\pi_2)}

Znaménko inverzní permutace je určeno jako

\sgn \pi^{-1} = \sgn \pi

Je-li permutace \pi součinem nezávislých cyklů \pi = \pi_1 \circ \pi_2 \circ ... \circ \pi_m, kde každý z cyklů \pi_i má délku k_i + 1, pak

\sgn \pi = \Pi_{i=1}^m {(-1)}^{k_i} = {(-1)}^{\sum_{i=1}^m k_i}

Související články[editovat | editovat zdroj]