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 Zykel der Ordnung ${}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 Zykel ${}\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 Zykel ist ${}Z$ der Wirkungsbereich. Jede Permutation ist ein Produkt von Zykeln, was wir hier ohne Beweis erwähnen. Eine solche Produktdarstellung heißt Zykeldarstellung.

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. 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äß Fakt *****, 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

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

Die Transposition ${}\tau$ vertausche die beiden Zahlen ${}k<\ell$ . Dann ist

{}{\begin{aligned}\operatorname {sgn} (\tau )&=\prod _{i<j}{\frac {\tau (j)-\tau (i)}{j-i}}\\&=\prod _{i<j,\,i,j\neq k,\ell }{\frac {\tau (j)-\tau (i)}{j-i}}\cdot \prod _{i<j,\,i=k,j\neq \ell }{\frac {\tau (j)-\tau (i)}{j-i}}\cdot \prod _{i<j,\,i\neq k,j=\ell }{\frac {\tau (j)-\tau (i)}{j-i}}\cdot \prod _{i<j,\,i=k,j=\ell }{\frac {\tau (j)-\tau (i)}{j-i}}\\&=\prod _{j>k,\,j\neq \ell }{\frac {j-\ell }{j-k}}\cdot \prod _{i\neq k,\,i<\ell }{\frac {k-i}{\ell -i}}\cdot {\frac {k-\ell }{\ell -k}}\\&=\prod _{j>\ell }{\frac {j-\ell }{j-k}}\cdot \prod _{i<k}{\frac {k-i}{\ell -i}}\cdot \prod _{k<j<\ell }{\frac {j-\ell }{j-k}}\cdot \prod _{k<i<\ell }{\frac {k-i}{\ell -i}}\cdot (-1)\\&=-1.\end{aligned}}

Die letzte Gleichung ergibt sich daraus, dass im ersten und im zweiten Produkt alle Zähler und Nenner positiv sind und dass im dritten und im vierten Produkt die Zähler negativ und die Nenner positiv sind, sodass sich diese (wegen der gleichen Indexmenge) Minuszeichen wegkürzen.

Die Aussage folgt dann aus der Homomorphieeigenschaft.

\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 Lemma 18.14 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

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)$ 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 nach der ersten Zeile.

\Box

<< | Kurs:Lineare Algebra (Osnabrück 2017-2018)/Teil I | >>

PDF-Version dieser Vorlesung

Arbeitsblatt zur Vorlesung (PDF)