Kurs:Lineare Algebra (Osnabrück 2017-2018)/Teil I/Vorlesung 18

„Wahr ist wahre Freundschaft doch wohl nur, wenn sie begrenzt ist.“

Bertolt Brecht

Permutationen

In dieser Vorlesung stellen wir eine weitere Beschreibung für die Determinante mit Hilfe von Permutationen vor.

Definition

Zu einer Menge ${}M$ nennt man die Menge

${}\operatorname {Aut} \,(M)=\operatorname {Perm} \,(M)=\left\{\varphi :M\longrightarrow M\mid \varphi {\text{ bijektiv}}\right\}\,$

der bijektiven Selbstabbildungen die Automorphismengruppe oder die Permutationsgruppe zu ${}M$.

Die Verknüpfung ist die Hintereinanderschaltung von Abbildungen und somit assoziativ, die Identität ist das neutrale Element. Das inverse Element zu einer bijektiven Abbildung ist einfach die Umkehrabbildung. Damit handelt es sich um eine Gruppe. Eine bijektive Selbstabbildung ${}\varphi \colon M\rightarrow M$ nennt man auch eine Permutation.

Für eine endliche Menge  ${}I=\{1,\ldots ,n\}$  schreibt man

${}S_{n}=\operatorname {Perm} \,(I)\,.$

Eine endliche Permutation kann man beispielsweise mit einer (vollständigen) Wertetabelle oder mit einem Pfeildiagramm beschreiben.

Definition

Es sei ${}M$ eine endliche Menge und ${}\pi$ eine Permutation auf ${}M$. Man nennt ${}\pi$ einen Zyklus der Ordnung ${}r$ (oder der Länge ${}r$), wenn es eine ${}r$-elementige Teilmenge  ${}Z\subseteq M$  derart gibt, dass ${}\pi$ auf ${}M\setminus Z$ die Identität ist und ${}\pi$ die Elemente aus ${}Z$ zyklisch vertauscht. Wenn  ${}Z=\{z,\pi (z),\,\pi ^{2}(z),\ldots ,\pi ^{r-1}(z)\}$  ist, so schreibt man einfach

${}\pi =\langle z,\pi (z),\,\pi ^{2}(z),\ldots ,\pi ^{r-1}(z)\rangle \,.$

Beispiel

Wir betrachten die Permutation

${}x$	${}1$	${}2$	${}3$	${}4$	${}5$
${}\pi (x)$	${}2$	${}1$	${}5$	${}3$	${}4$

Man kann sie als Produkt der beiden Zyklen ${}\langle 1,2\rangle$ und ${}\langle 3,5,4\rangle$ schreiben.

Ein Element  ${}x\in M$  mit  ${}\pi (x)=x$  nennt man Fixpunkt der Permutation. Der Wirkungsbereich einer Permutation ist die Menge der Punkte aus ${}M$, die keine Fixpunkte sind. Bei einem Zyklus ist ${}Z$ der Wirkungsbereich. Jede Permutation ist ein Produkt von Zyklen, was wir hier ohne Beweis erwähnen. Eine solche Produktdarstellung heißt Zyklendarstellung.

Definition

Zu einer natürlichen Zahl ${}n$ nennt man die Zahl

${}n!:=n(n-1)(n-2)\cdots 3\cdot 2\cdot 1\,$

die Fakultät von ${}n$ (sprich ${}n$ Fakultät).

Lemma

Es sei ${}M$ eine endliche Menge mit ${}n$ Elementen.

Dann besitzt die Permutationsgruppe  ${}\operatorname {Perm} \,(M)\cong S_{n}$  genau ${}n!$ Elemente.

Beweis

Es sei  ${}M=\{1,\ldots ,n\}$.  Für die ${}1$ gibt es ${}n$ mögliche Bilder, für ${}2$ gibt es noch ${}n-1$ mögliche Bilder, für ${}3$ gibt es noch ${}n-2$ mögliche Bilder, usw. Daher gibt es insgesamt

${}n(n-1)(n-2)\cdots 2\cdot 1=n!\,$

mögliche Permutationen.

$\Box$

Transpositionen

Definition

Eine Transposition auf einer endlichen Menge ${}M$ ist eine Permutation auf ${}M$, die genau zwei Elemente miteinander vertauscht und alle anderen Elemente unverändert lässt.

Eine Transposition ist also ein Zykel der Länge ${}2$.

Lemma

Jede Permutation auf einer endlichen Menge ${}M$

kann man als Produkt von Transpositionen schreiben.

Beweis

Wir beweisen die Aussage durch Induktion über die Anzahl der Menge ${}M$. Für  ${}{\#\left(M\right)}=1$  ist nichts zu zeigen, sei also  ${}{\#\left(M\right)}\geq 2$.  Die Identität ist das leere Produkt aus Transpositionen. Es sei also ${}\pi$ nicht die Identität, und sei  ${}\pi (x)=y\neq x$.  Es sei ${}\tau$ die Transposition, die ${}x$ und ${}y$ vertauscht. Dann ist ${}y$ ein Fixpunkt von ${}\pi \tau$, und man kann ${}\pi \tau$ auffassen als eine Permutation auf  ${}M'=M\setminus \{y\}$.  Nach Induktionsvoraussetzung gibt es dann Transpositionen ${}\tau _{j}$ auf ${}M'$ mit  ${}\pi \tau =\prod _{j}\tau _{j}$  auf ${}M'$. Dies gilt dann auch auf ${}M$, und daher ist  ${}\pi =\left(\prod _{j}\tau _{j}\right)\tau$. 

$\Box$

Das Signum einer Permutation

Definition

Es sei  ${}M=\{1,\ldots ,n\}$  und sei ${}\pi$ eine Permutation auf ${}M$. Dann heißt die Zahl

${}\operatorname {sgn} (\pi )=\prod _{i<j}{\frac {\pi (j)-\pi (i)}{j-i}}\,$

das Signum (oder das Vorzeichen) der Permutation ${}\pi$.

Das Signum ist ${}1$ oder ${}-1$, da im Zähler und im Nenner die bis auf das Vorzeichen gleichen Differenzen ${}\pm (j-i)$ stehen. Der Faktor ${}r-s$ im Zähler wird von ${}\pm (\pi ^{-1}(r)-\pi ^{-1}(s))$ aus getroffen. Es gibt für das Signum also nur zwei mögliche Werte. Bei  ${}\operatorname {sgn} (\pi )=1$  spricht man von einer geraden Permutation und bei  ${}\operatorname {sgn} (\pi )=-1$  von einer ungeraden Permutation.

Definition

Es sei  ${}M=\{1,\ldots ,n\}$  und sei ${}\pi$ eine Permutation auf ${}M$. Dann heißt ein Indexpaar

${}i<j\,$

ein Fehlstand von ${}\pi$, wenn  ${}\pi (i)>\pi (j)$  ist.

Lemma

Es sei  ${}M=\{1,\ldots ,n\}$  und sei ${}\pi$ eine Permutation auf ${}M$. Es sei  ${}k={\#\left(F\right)}$  die Anzahl der Fehlstände von ${}\pi$.

Dann ist das Signum von ${}\pi$ gleich

${}\operatorname {sgn} (\pi )=(-1)^{k}\,.$

Beweis

Wir schreiben

${}{\begin{aligned}\operatorname {sgn} (\pi )&=\prod _{i<j}{\frac {\pi (j)-\pi (i)}{j-i}}\\&=\prod _{(i,j)\in F}{\frac {\pi (j)-\pi (i)}{j-i}}\prod _{(i,j)\not \in F}{\frac {\pi (j)-\pi (i)}{j-i}}\\&=(-1)^{k}\prod _{(i,j)\in F}{\frac {\pi (i)-\pi (j)}{j-i}}\prod _{(i,j)\not \in F}{\frac {\pi (j)-\pi (i)}{j-i}}\\&=(-1)^{k},\end{aligned}}$

da nach dieser Umordnung sowohl im Zähler als auch im Nenner das Produkt aller positiven Differenzen steht.

$\Box$

Beispiel

Wir betrachten die Permutation

${}x$	${}1$	${}2$	${}3$	${}4$	${}5$	${}6$
${}\sigma (x)$	${}2$	${}4$	${}6$	${}5$	${}3$	${}1$

mit der Zyklendarstellung

$\langle 1,2,4,5,3,6\rangle .$

Die Fehlstände sind

$(1,6),\,(2,5),\,(2,6),\,(3,4),\,(3,5),\,(3,6),\,(4,5),\,(4,6),\,(5,6),$

es gibt also ${}9$ Stück davon. Das Signum ist also  ${}(-1)^{9}=-1$  gemäß Lemma 18.10, und die Permutation ist ungerade.

Das Signum ist ein Gruppenhomomorphismus im Sinne der folgenden Definition.

Definition

Es seien ${}(G,\circ ,e_{G})$ und ${}(H,\circ ,e_{H})$ Gruppen. Eine Abbildung

$\psi \colon G\longrightarrow H$

heißt Gruppenhomomorphismus, wenn die Gleichheit

${}\psi (g\circ g')=\psi (g)\circ \psi (g')\,$

für alle  ${}g,g'\in G$  gilt.

Satz

Die durch das Signum gegebene Zuordnung

$S_{n}\longrightarrow \{1,-1\},\,\pi \longmapsto \operatorname {sgn} (\pi ),$

ist ein Gruppenhomomorphismus.

Beweis

Es seien zwei Permutationen ${}\pi$ und ${}\rho$ gegeben. Dann ist

${}{\begin{aligned}\operatorname {sgn} (\pi \circ \rho )&=\prod _{i<j}{\frac {(\pi \circ \rho )(j)-(\pi \circ \rho )(i)}{j-i}}\\&=\left(\prod _{i<j}{\frac {(\pi \circ \rho )(j)-(\pi \circ \rho )(i)}{\rho (j)-\rho (i)}}\right)\prod _{i<j}{\frac {\rho (j)-\rho (i)}{j-i}}\\&=\left(\prod _{i<j,\,\rho (i)<\rho (j)}{\frac {\pi (\rho (j))-\pi (\rho (i))}{\rho (j)-\rho (i)}}\right)\left(\prod _{i<j,\,\rho (i)>\rho (j)}{\frac {\pi (\rho (j))-\pi (\rho (i))}{\rho (j)-\rho (i)}}\right)\,\operatorname {sgn} (\rho )\\&=\left(\prod _{i<j,\,\rho (i)<\rho (j)}{\frac {\pi (\rho (j))-\pi (\rho (i))}{\rho (j)-\rho (i)}}\right)\left(\prod _{i<j,\,\rho (i)>\rho (j)}{\frac {\pi (\rho (i))-\pi (\rho (j))}{\rho (i)-\rho (j)}}\right)\,\operatorname {sgn} (\rho )\\&=\prod _{k<\ell }{\frac {\pi (\ell )-\pi (k)}{\ell -k}}\operatorname {sgn} (\rho )\\&=\operatorname {sgn} (\pi )\operatorname {sgn} (\rho ).\,\end{aligned}}$

$\Box$

Lemma

Das Signum einer Transposition

ist ${}-1$.

Beweis

Die Transposition ${}\tau$ vertausche die beiden Zahlen  ${}k<\ell$.  Wenn  ${}k+1<\ell$,  und wenn ${}\rho$ die Transposition der Nachbarn ${}k$ und ${}k+1$ und ${}{\tilde {\tau }}$ die Transposition von ${}k+1$ und ${}\ell$ bezeichnet, so besteht die Beziehung

${}\tau =\rho \circ {\tilde {\tau }}\circ \rho \,,$

was man direkt auf den relevanten Elementen ${}k,k+1,\ell$ überprüfen kann. Aufgrund der Homomorphieeigenschaft gilt also  ${}\operatorname {sgn} (\tau )=\operatorname {sgn} ({\tilde {\tau }})$.  Daher genügt es, die Aussage für Transpositionen zu beweisen, die zwei benachbarte Elemente vertauschen. Solche Transpositionen haben aber nur einen Fehlstand, und somit folgt die Aussage aus Lemma 18.10.

$\Box$

Korollar

Es sei  ${}M=\{1,\ldots ,n\}$  und sei ${}\pi$ eine Permutation auf ${}M$. Es sei

${}\pi =\tau _{1}\cdots \tau _{r}\,$

als ein Produkt von ${}r$ Transpositionen geschrieben.

Dann gilt für das Signum die Darstellung

${}\operatorname {sgn} (\pi )=(-1)^{r}\,.$

Beweis

Dies folgt aus Lemma 18.14 und Satz 18.13.

$\Box$

Bemerkung  

Es sei ${}I$ eine beliebige Menge mit ${}n$ Elementen, die nicht geordnet sein muss, und sei ${}\pi$ eine Permutation auf ${}I$. Dann kann man nicht von Fehlständen sprechen und die Definition des Signums ist nicht direkt anwendbar. Man kann sich jedoch an Korollar 18.15 orientieren, um das Signum auch in dieser leicht allgemeineren Situation zu erklären. Dazu schreibt man ${}\pi$ als Produkt von ${}r$ Transpositionen und definiert

${}\operatorname {sgn} (\pi )={\begin{cases}1\,,{\text{ falls }}r{\text{ gerade ist}}\,,\\-1\,,{\text{ falls }}r{\text{ ungerade ist}}\,.\end{cases}}\,$

Um einzusehen, dass dies wohldefiniert ist, betrachtet man eine Bijektion

$\varphi \colon I\longrightarrow \{1,\ldots ,n\}.$

Die Permutation ${}\pi$ auf ${}I$ definiert auf ${}\{1,\ldots ,n\}$ die Permutation  ${}\pi '=\varphi \pi \varphi ^{-1}$.  Sei  ${}\pi =\tau _{1}\cdots \tau _{r}$  eine Darstellung als Produkt von ${}r$ Transpositionen auf ${}I$. Dann gilt

${}\pi '=\varphi \pi \varphi ^{-1}=\varphi \tau _{1}\cdots \tau _{r}\varphi ^{-1}=\varphi \tau _{1}\varphi ^{-1}\varphi \tau _{2}\varphi ^{-1}\varphi \cdots \varphi ^{-1}\varphi \tau _{r}\varphi ^{-1}=\tau _{1}'\tau _{2}'\cdots \tau _{r}'\,$

mit  ${}\tau _{j}'=\varphi \tau _{j}\varphi ^{-1}$.  Dies sind ebenfalls Transpositionen, sodass die Parität von ${}r$ durch das Signum von ${}\pi '$ festgelegt ist.

Die Leibnizformel für die Determinante

Gottfried Wilhelm Leibniz (1646-1716)

Satz

Für die Determinante einer ${}n\times n$-Matrix

${}M=\left(a_{ij}\right)_{ij}\,$

gilt

${}\det M=\sum _{\pi \in S_{n}}\operatorname {sgn} (\pi )a_{1\pi (1)}\cdots a_{n\pi (n)}\,.$

Beweis

Wir führen Induktion über  ${}n\geq 1$,  wobei der Induktionsanfang klar ist. Es sei also  ${}n\geq 2$.  Die Menge der Permutationen  ${}\pi \in S_{n}$  kann man aufspalten, indem man nach  ${}\pi (1)=i$  sortiert und die bijektive Abbildung

$\pi {|}_{\{2,\ldots ,n\}}\colon \{2,\ldots ,n\}\longrightarrow \{1,\ldots ,n\}\setminus \{i\}$

als eine Permutation ${}\rho$ auf ${}\{1,\ldots ,n-1\}$ auffasst, indem man beide Mengen ordnungstreu mit ${}\{1,\ldots ,n-1\}$ identifiziert. Dies ergibt eine Bijektion  ${}S_{n,i}\cong S_{n-1}$,  wobei hier ${}S_{n,i}$ die Menge der Permutationen auf ${}\{1,\ldots ,n\}$ bezeichnet, die ${}1$ auf ${}i$ abbilden. Zwischen den Signa besteht dabei die Beziehung

${}\operatorname {sgn} (\pi )=(-1)^{i-1}\operatorname {sgn} (\rho )=(-1)^{i+1}\operatorname {sgn} (\rho )\,,$

da man ${}i-1$ Transpositionen braucht, um die ${}i$-te Stelle und die erste Stelle zu vertauschen. Es besteht also insgesamt eine natürliche Bijektion

${}S_{n}=\biguplus _{i\in \{1,\ldots ,n\}}S_{n,i}=\biguplus _{i\in \{1,\ldots ,n\}}S_{n-1}\,.$

Somit gilt

${}{\begin{aligned}\sum _{\pi \in S_{n}}\operatorname {sgn} (\pi )a_{1\pi (1)}\cdots a_{n\pi (n)}&=\sum _{i=1}^{n}\sum _{\pi \in S_{n,i}}\operatorname {sgn} (\pi )\prod _{j=1}^{n}a_{j\pi (j)}\\&=\sum _{i=1}^{n}a_{1i}\sum _{\pi \in S_{n,i}}\operatorname {sgn} (\pi )\prod _{j=2}^{n}a_{j\pi (j)}\\&=\sum _{i=1}^{n}a_{1i}\sum _{\rho \in S_{n-1}}(-1)^{i+1}\operatorname {sgn} (\rho )\prod _{k=1}^{n-1}(M_{1i})_{k\rho (k)}\\&=\sum _{i=1}^{n}(-1)^{i+1}a_{1i}\det M_{1i}\\&=\det M,\end{aligned}}$

wobei ${}M_{1i}$ die Streichungsmatrix zur ersten Zeile und ${}i$-ten Spalte ist (und sich die Indizierung auf diese Matrix bezieht). Für die vorletzte Gleichung geht die Induktionsvoraussetzung ein und die letzte Gleichung beruht auf der Entwicklung der Determinante nach der ersten Zeile.

$\Box$

<< | Kurs:Lineare Algebra (Osnabrück 2017-2018)/Teil I | >> PDF-Version dieser Vorlesung Arbeitsblatt zur Vorlesung (PDF)