Kurs:Lineare Algebra (Osnabrück 2024-2025)/Teil I/Vorlesung 18/kontrolle

Permutationen

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

Definition Referenznummer erstellen

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 Referenznummer erstellen

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 Referenznummer erstellen

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 Referenznummer erstellen

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 Referenznummer erstellen

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 Referenznummer erstellen

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 Referenznummer erstellen

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 Referenznummer erstellen

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 Referenznummer erstellen

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 Lemma 18.10 ändern

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 Referenznummer erstellen

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 Referenznummer erstellen

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 Satz 18.13 ändern

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 Lemma 18.14 ändern

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   Referenznummer erstellen

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

Gottfried Wilhelm Leibniz (1646-1716)

Satz Referenznummer erstellen

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$