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í.

[editovat] Definice inverze

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

[editovat] Příklad

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 < 3;1 < 4;2 < 4

, potom permutace:

2 < 3 > 1 < 4;2 > 1;2 < 4;3 < 4

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

[editovat] Vlastnosti

Jsou-li $π$ a $\pi^\prime$ dvě permutace na množině $M$ , pak znaménko permutace jejich součinu je rovno součïnu znamének jednotlivých permutací

$\sgn {(\pi \circ \pi^{\prime})} = {\sgn (\pi)}\;{\sgn (\pi^{\prime})}$

Znaménko inverzní permutace je určeno jako

sgnπ - 1 = sgnπ

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

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

[editovat] Související články

Kategorie: Algebra | Kombinatorika

Znaménko permutace v jiných jazycích: English, Français, தமிழ்

Tento článek je převzat z české wikipedie - otevřené encyklopedie, originální článek naleznete na adrese: „http://cs.wikipedia.org/wiki/Znam%C3%A9nko_permutace“
Stránka byla naposledy upravena v Stránka byla naposledy editována 18. 11. 2007 v 03:46.
Veškerý text je dostupný za podmínek GNU Free Documentation License (Autorské právo pro podrobnosti).