Vorzeichen (Permutation)

1 2 3 +1 1 3 2 −1 2 1 3 −1 2 3 1 +1 3 1 2 +1 3 2 1 −1

Alle Permutationen der Menge $\scriptstyle \{1,2,3\}$ mit zugehörigem Signum

Das Signum, auch Parität oder Vorzeichen genannt, ist in der Kombinatorik eine wichtige Kennzahl von Permutationen. Das Signum kann die Werte $+1$ oder $-1$ annehmen, wobei man im ersten Fall von einer geraden und im zweiten Fall von einer ungeraden Permutation spricht. Es gibt mehrere Möglichkeiten, gerade und ungerade Permutationen zu charakterisieren. So ist eine Permutation genau dann gerade, wenn die Anzahl der Fehlstände in der Permutation gerade ist. Jede Permutation lässt sich auch als Verkettung endlich vieler Transpositionen darstellen und ist genau dann gerade, wenn die Anzahl der dabei benötigten Transpositionen gerade ist. Eine Permutation kann zudem auch in Zykel zerlegt werden und ist genau dann gerade, wenn die Anzahl der Zykel gerader Länge gerade ist. Das Signum ist als Abbildung ein Gruppenhomomorphismus von der symmetrischen Gruppe der Permutationen in die multiplikative Gruppe über der Menge $\{+1,-1\}$. Ein wichtiges Einsatzbeispiel des Signums ist die Leibniz-Formel für Determinanten.

Definition

Ist $S_{n}$ mit $n\geq 2$ die symmetrische Gruppe aller Permutationen der Menge $\{1,\ldots ,n\}$, dann ist das Signum $\operatorname {sign} (\pi )$ einer Permutation

$\pi ={\begin{pmatrix}1&2&\cdots &n\\\pi (1)&\pi (2)&\cdots &\pi (n)\end{pmatrix}}\in S_{n}$

definiert als

$\operatorname {sign} (\pi )=\prod _{1\leq i<j\leq n}{\frac {\pi (j)-\pi (i)}{j-i}}$.

Aufgrund der Bijektivität einer Permutation tritt hierbei jeder Term $j-i$ für $1\leq i<j\leq n$ bis auf gegebenenfalls das Vorzeichen je einmal im Zähler und einmal Nenner eines Bruchs auf. Demnach kann die Funktion $\operatorname {sign}$ nur die Werte $+1$ oder $-1$ annehmen. Ist $\operatorname {sign} (\pi )=+1$, dann nennt man die Permutation $\pi$ gerade, ansonsten ungerade. Insbesondere ist das Signum der identischen Permutation $\pi (i)=i$ immer gleich $+1$.

Beispiele

Das Signum der Permutation

$\pi ={\begin{pmatrix}1&2&3\\3&1&2\end{pmatrix}}\in S_{3}$

ist gegeben durch

$\operatorname {sign} (\pi )={\frac {1-3}{2-1}}\cdot {\frac {2-3}{3-1}}\cdot {\frac {2-1}{3-2}}={\frac {2-1}{2-1}}\cdot {\frac {1-3}{3-1}}\cdot {\frac {2-3}{3-2}}=(+1)\cdot (-1)\cdot (-1)=+1$.

Jeder der drei Faktoren $2-1,3-1$ und $3-2$ tritt dabei, bis auf das Vorzeichen, je einmal im Zähler und einmal im Nenner auf.

Weitere Darstellungen

Darstellung über die Zahl der Fehlstände

In einer Permutation $\pi \in S_{n}$ nennt man ein Paar $(i,j)$ Fehlstand oder Inversion, wenn $i<j$ und $\pi (i)>\pi (j)$ gilt. Bezeichnet nun

$F(\pi )=\#\{~(i,j)\in \{1,\ldots ,n\}\times \{1,\ldots ,n\}\mid i<j,\pi (i)>\pi (j)~\}$

die Anzahl der Fehlstände einer Permutation $\pi$, dann gilt

$\operatorname {sign} (\pi )=(-1)^{F(\pi )}$.

Diese Darstellung folgt daraus, dass in der Definition des Signums alle Faktoren im Nenner positiv sind, während ein Faktor im Zähler immer genau dann negativ ist, wenn ein Fehlstand vorliegt. Das Vorzeichen des gesamten Produkts ergibt sich somit aus der Anzahl der Fehlstände. Die maximale Anzahl der Fehlstände einer Permutation $\pi \in S_{n}$ beträgt dabei ${\tfrac {n(n-1)}{2}}$, was genau dann der Fall ist, wenn die Permutation die Reihenfolge aller Zahlen umkehrt.

Beispiel

Die Fehlstände der Permutation

$\pi ={\begin{pmatrix}1&2&3&4&5\\2&1&4&5&3\end{pmatrix}}\in S_{5}$

sind $(1,2),(3,5)$ und $(4,5)$, somit ist die Permutation ungerade.

Darstellung über die Zahl der Transpositionen

Eine Transposition $\tau _{kl}$ mit $k<l$ ist eine Permutation, die lediglich die zwei Zahlen $k$ und $l$ vertauscht, das heißt $k$ auf $l$ sowie $l$ auf $k$ abbildet und die übrigen Zahlen festlässt. Für das Signum einer Transposition gilt

$\operatorname {sign} (\tau _{kl})=-1$,

denn jede Transposition lässt sich als Verkettung einer ungeraden Zahl von Nachbarschaftsvertauschungen der Form $\tau _{k,k+1}$ durch

$\tau _{kl}=(\tau _{l-1,l}\circ \tau _{l-2,l-1}\circ \cdots \circ \tau _{k+1,k+2})\circ (\tau _{k,k+1}\circ \cdots \circ \tau _{l-2,l-1}\circ \tau _{l-1,l})$

darstellen. Hierbei wird zunächst die Zahl $l$ durch sukzessive Nachbarschaftsvertauschungen an die Stelle $k$ gebracht und dann die Zahl $k$ von der Stelle $k+1$ durch sukzessive Nachbarschaftsvertauschungen an die Stelle $l$. Nachdem jede dieser Nachbarschaftsvertauschungen genau einen Fehlstand erzeugt, ist die Gesamtzahl der Fehlstände einer Transposition

$F(\tau _{kl})=(l-k)+(l-k-1)=2(l-k)-1$

und damit immer ungerade. Jede Permutation $\pi \in S_{n}$ lässt sich nun als Verkettung von höchstens $n-1$ Transpositionen darstellen. Jede dieser Transpositionen vertauscht dabei jeweils die kleinste Zahl $k$, für die $\pi (k)\neq k$ gilt, mit derjenigen Zahl $l>k$, für die $\pi (l)=k$ gilt. Ist $M(\pi )$ die Anzahl der dabei benötigten Transpositionen, dann gilt

$\operatorname {sign} (\pi )=(-1)^{M(\pi )}$.

Es gibt natürlich noch weitere Möglichkeiten, eine Permutation als Verkettung von Transpositionen darzustellen. Handelt es sich dabei aber um eine gerade Permutation, dann ist die Zahl der benötigten Transpositionen immer gerade, handelt es sich um eine ungerade Permutation immer ungerade.

Beispiel

Die Permutation

$\pi ={\begin{pmatrix}1&2&3&4\\3&2&4&1\end{pmatrix}}\in S_{4}$

lässt sich durch $\pi =\tau _{34}\circ \tau _{14}$ darstellen und ist damit gerade. Eine weitere Darstellung als Verkettung von Transpositionen wäre etwa $\pi =\tau _{23}\circ \tau _{12}\circ \tau _{23}\circ \tau _{34}$.

Darstellung über die Zahl und Länge der Zykel

Ein zyklische Permutation $\sigma _{k_{1},\ldots ,k_{m}}$, kurz Zykel, ist eine Permutation, die die Zahlen $k_{1},\ldots ,k_{m}$ zyklisch vertauscht, das heißt $k_{1}$ auf $k_{2}$ abbildet, $k_{2}$ auf $k_{3}$ bis hin zu $k_{m}$ auf $k_{1}$. Ein Zykel der Länge zwei entspricht gerade einer Transposition zweier Zahlen. Jeder Zykel der Länge $m>1$ kann als Verkettung von $m-1$ Transpositionen geschrieben werden:

$\sigma _{k_{1},\ldots ,k_{m}}=\tau _{k_{1},k_{2}}\circ \cdots \circ \tau _{k_{m-1},k_{m}}$.

Da Transpositionen ungerade sind, ist das Signum eines Zykels der Länge $m$ damit

$\operatorname {sign} (\sigma _{k_{1},\ldots ,k_{m}})=(-1)^{m-1}$.

Ein Zykel ist also genau dann gerade, wenn seine Länge ungerade ist. Jede Permutation $\pi \in S_{n}$ lässt sich nun eindeutig als Verkettung von $s\leq n$ disjunkten Zykeln darstellen. Sind $m_{1},\ldots ,m_{s}$ die Längen dieser Zykel, dann gilt

$\operatorname {sign} (\pi )=(-1)^{m_{1}-1}\cdot \ldots \cdot (-1)^{m_{s}-1}=(-1)^{m_{1}+\ldots +m_{s}-s}$.

Eine Permutation ist demach genau dann gerade, wenn die Summe der Längen der einzelnen Zykel minus der Anzahl der Zykel gerade ist. Da Zykel ungerader Länge das Signum nicht verändern, ist eine Permutation genau dann gerade, wenn die Anzahl der Zykel gerader Länge gerade ist.

Beispiel

Die Permutation

$\pi ={\begin{pmatrix}1&2&3&4&5&6\\3&6&4&1&5&2\end{pmatrix}}\in S_{6}$

zerfällt in drei disjunkte Zykel, in Zykelschreibweise $\pi =(1~3~4)(2~6)(5)$. Da die Summe $3+2+1-3$ ungerade ist, ist die Permutation ebenfalls ungerade. Einerzykel können in der Zykelschreibweise und bei der Zählung auch weggelassen werden, ohne die Summe und damit das Signum zu verändern.

Eigenschaften

Inverse Permutationen

Für das Signum der inversen Permutation $\pi ^{-1}$ von $\pi$ gilt:

$\operatorname {sign} (\pi ^{-1})=\prod _{i<j}{\frac {j-i}{\pi (j)-\pi (i)}}=\prod _{i<j}{\frac {\pi (j)-\pi (i)}{j-i}}=\operatorname {sign} (\pi )$

Durch Invertierung ändert sich also das Signum einer Permutation nicht.

Verkettung von Permutationen

Für die Verkettung zweier Permutationen $\tau ,\pi \in S_{n}$ gilt:

${\begin{aligned}\operatorname {sign} (\tau \circ \pi )&=\prod _{i<j}{\frac {\tau (\pi (j))-\tau (\pi (i))}{j-i}}=\prod _{i<j}{\frac {\tau (\pi (j))-\tau (\pi (i))}{\pi (j)-\pi (i)}}\cdot \prod _{i<j}{\frac {\pi (j)-\pi (i)}{j-i}}=\\&=\prod _{\pi (i)<\pi (j)}{\frac {\tau (j)-\tau (i)}{j-i}}\cdot \prod _{i<j}{\frac {\pi (j)-\pi (i)}{j-i}}=\operatorname {sign} (\tau )\cdot \operatorname {sign} (\pi )\end{aligned}}$

Diese Eigenschaft wurde oben bei der Herleitung der verschiedenen Darstellungen des Signums bereits implizit verwendet. Demnach ist die Verkettung zweier Permutationen genau dann gerade, wenn beide das gleiche Signum aufweisen.

Homomorphie

Durch die Multiplikativität des Signums stellt die Abbildung

$\operatorname {sign} \colon S_{n}\to \{+1,-1\}$

einen Gruppenhomomorphismus von $(S_{n},\circ )$ in die multiplikative Gruppe $(\{+1,-1\},\cdot )$ dar. Diese Eigenschaft wird in der Theorie der Determinanten, beispielsweise der Leibniz-Formel verwendet. Der Kern dieses Homomorphismus ist die Menge der geraden Permutationen. Sie bildet einen Normalteiler von $S_{n}$, die alternierende Gruppe $A_{n}$. Die Menge der ungeraden Permutationen bildet jedoch keine Untergruppe von $S_{n}$.

Siehe auch

• Levi-Civita-Symbol

Literatur

• Albrecht Beutelspacher: Lineare Algebra. Eine Einführung in die Wissenschaft der Vektoren, Abbildungen und Matrizen. 6. Auflage. Vieweg, 2009, ISBN 3-528-56508-X. 
• Siegfried Bosch: Lineare Algebra. Springer, 2009, ISBN 3-540-76437-2.