Kurs:Lineare Algebra (Osnabrück 2015-2016)/Teil I/Vorlesung 18/latex
\setcounter{section}{18}
\epigraph { Wahr ist wahre Freundschaft doch wohl nur, wenn sie begrenzt ist. } { Bertolt Brecht }
\zwischenueberschrift{Permutationen}
In dieser Vorlesung stellen wir eine weitere Beschreibung für die Determinante mit Hilfe von Permutationen vor.
\inputdefinition
{}
{
Zu einer Menge $M$ nennt man die Menge
\mavergleichskettedisp
{\vergleichskette
{ \operatorname{Aut} \, (M)
}
{ =} { \operatorname{Perm} \,( M)
}
{ =} { { \left\{ \varphi:M \longrightarrow M \mid \varphi \text{ bijektiv} \right\} }
}
{ } {
}
{ } {
}
}
{}{}{}
der bijektiven Selbstabbildungen die \definitionswort {Automorphismengruppe}{} oder die \definitionswort {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 \maabb {\varphi} {M} {M } {} nennt man auch eine \stichwort {Permutation} {.}
Für eine endliche Menge
\mavergleichskette
{\vergleichskette
{I
}
{ = }{\{1 , \ldots , n\}
}
{ }{
}
{ }{
}
{ }{
}
}
{}{}{}
schreibt man
\mavergleichskettedisp
{\vergleichskette
{S_n
}
{ =} {\operatorname{Perm} \,(I)
}
{ } {
}
{ } {
}
{ } {
}
}
{}{}{.}
Eine endliche Permutation kann man beispielsweise mit einer
\zusatzklammer {vollständigen} {} {}
Wertetabelle oder mit einem Pfeildiagramm beschreiben.
\bild{ \begin{center}
\includegraphics[width=5.5cm]{\bildeinlesung {Permutation8.png} }
\end{center}
\bildtext {} }
\bildlizenz { Permutation8.png } {} {MGausmann} {Commons} {CC-by-sa 4.0} {}
\bild{ \begin{center}
\includegraphics[width=5.5cm]{\bildeinlesung {Composicion_de_permutaciones.svg} }
\end{center}
\bildtext {} }
\bildlizenz { Composicion de permutaciones.svg } {} {Drini} {Commons} {CC-by-SA 3.0} {}
\bild{ \begin{center}
\includegraphics[width=5.5cm]{\bildeinlesung {050712 perm 0.png} }
\end{center}
\bildtext {} }
\bildlizenz { 050712 perm 0.png } {} {Magnus Manske} {Commons} {gemeinfrei} {}
\inputdefinition
{}
{
Es sei $M$ eine endliche Menge und $\pi$ eine
\definitionsverweis {Permutation}{}{}
auf $M$. Man nennt $\pi$ einen \definitionswort {Zykel der Ordnung}{} $r$, wenn es eine $r$-elementige Teilmenge
\mavergleichskette
{\vergleichskette
{Z
}
{ \subseteq }{M
}
{ }{
}
{ }{
}
{ }{
}
}
{}{}{}
derart gibt, dass $\pi$ auf
\mathl{M \setminus Z}{} die Identität ist und $\pi$ die Elemente aus $Z$ zyklisch vertauscht. Wenn
\mavergleichskette
{\vergleichskette
{Z
}
{ = }{ \{z, \pi(z),\, \pi^2(z) , \ldots , \pi^{r-1}(z)\}
}
{ }{
}
{ }{
}
{ }{
}
}
{}{}{}
ist, so schreibt man einfach
\mavergleichskettedisp
{\vergleichskette
{ \pi
}
{ =} { \langle z, \pi(z),\, \pi^2(z) , \ldots , \pi^{r-1}(z) \rangle
}
{ } {
}
{ } {
}
{ } {
}
}
{}{}{.}
}
\inputbeispiel{}
{
Wir betrachten die Permutation
\wertetabellefuenfausteilzeilen { $x$ }
{\mazeileundfuenf {1} {2} {3} {4} {5
} }
{ $\pi (x)$ }
{\mazeileundfuenf {2} {1} {5} {3} {4
} }
Man kann sie als Produkt der beiden
\definitionsverweis {Zykel}{}{}
\mathl{\langle 1, 2 \rangle}{} und
\mathl{\langle 3, 5, 4 \rangle}{} schreiben.
}
Ein Element
\mavergleichskette
{\vergleichskette
{ x
}
{ \in }{ M
}
{ }{}
{ }{}
{ }{}
}
{}{}{}
mit
\mavergleichskette
{\vergleichskette
{\pi (x)
}
{ = }{x
}
{ }{
}
{ }{
}
{ }{
}
}
{}{}{}
nennt man
\definitionsverweis {Fixpunkt}{}{}
der Permutation. Der \stichwort {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 \stichwort {Zykeldarstellung} {.}
\inputdefinition
{}
{
Zu einer natürlichen Zahl $n$ nennt man die Zahl
\mavergleichskettedisp
{\vergleichskette
{n!
}
{ \defeq} { n(n-1)(n-2) \cdots 3 \cdot 2 \cdot 1
}
{ } {
}
{ } {
}
{ } {
}
}
{}{}{}
die \definitionswort {Fakultät}{} von $n$
\zusatzklammer {sprich $n$ Fakultät} {} {.}
}
\inputfaktbeweis
{Endliche Permutationsgruppe/Anzahl/Fakt}
{Lemma}
{}
{
\faktsituation {}
\faktvoraussetzung {Es sei $M$ eine endliche Menge mit $n$ Elementen.}
\faktfolgerung {Dann besitzt die
\definitionsverweis {Permutationsgruppe}{}{}
\mavergleichskette
{\vergleichskette
{ \operatorname{Perm} \,( M)
}
{ \cong }{ S_n
}
{ }{
}
{ }{
}
{ }{
}
}
{}{}{}
genau $n!$ Elemente.}
\faktzusatz {}
\faktzusatz {}
}
{
Es sei
\mavergleichskette
{\vergleichskette
{ M
}
{ = }{ { \{ 1 , \ldots , n \} }
}
{ }{
}
{ }{
}
{ }{
}
}
{}{}{.}
Für die $1$ gibt es $n$ mögliche Bilder, für $2$ gibt es noch
\mathl{n-1}{} mögliche Bilder, für $3$ gibt es noch
\mathl{n-2}{} mögliche Bilder, usw. Daher gibt es insgesamt
\mavergleichskettedisp
{\vergleichskette
{ n(n-1)(n-2) \cdots 2 \cdot 1
}
{ =} { n !
}
{ } {
}
{ } {
}
{ } {
}
}
{}{}{}
mögliche Permutationen.
\zwischenueberschrift{Transpositionen}
\inputdefinition
{}
{
Eine \definitionswort {Transposition}{} auf einer endlichen Menge $M$ ist eine \definitionsverweis {Permutation}{}{} auf $M$, die genau zwei Elemente miteinander vertauscht und alle anderen Elemente unverändert lässt.
}
\inputfaktbeweis
{Endliche Permutation/Darstellung mit Transpositionen/Fakt}
{Lemma}
{}
{
\faktsituation {}
\faktvoraussetzung {Jede
\definitionsverweis {Permutation}{}{}
auf einer endlichen Menge $M$}
\faktfolgerung {kann man als Produkt von
\definitionsverweis {Transpositionen}{}{}
schreiben.}
\faktzusatz {}
\faktzusatz {}
}
{
Wir beweisen die Aussage durch Induktion über die Anzahl der Menge $M$. Für
\mavergleichskette
{\vergleichskette
{ { \# \left( M \right) }
}
{ = }{ 1
}
{ }{
}
{ }{
}
{ }{
}
}
{}{}{}
ist nichts zu zeigen, sei also
\mavergleichskette
{\vergleichskette
{ { \# \left( M \right) }
}
{ \geq }{ 2
}
{ }{
}
{ }{
}
{ }{
}
}
{}{}{.}
Die Identität ist das leere Produkt aus Transpositionen. Es sei also $\pi$ nicht die Identität, und sei
\mavergleichskette
{\vergleichskette
{ \pi(x)
}
{ = }{ y
}
{ \neq }{x
}
{ }{
}
{ }{
}
}
{}{}{.}
Es sei $\tau$ die Transposition, die $x$ und $y$ vertauscht. Dann ist $y$ ein
\definitionsverweis {Fixpunkt}{}{}
von $\pi \tau$, und man kann $\pi \tau$ auffassen als eine Permutation auf
\mavergleichskette
{\vergleichskette
{ M'
}
{ = }{M \setminus \{y\}
}
{ }{
}
{ }{
}
{ }{
}
}
{}{}{.}
Nach Induktionsvoraussetzung gibt es dann Transpositionen $\tau_j$ auf $M'$ mit
\mavergleichskette
{\vergleichskette
{\pi \tau
}
{ = }{ \prod_j \tau_j
}
{ }{
}
{ }{
}
{ }{
}
}
{}{}{}
auf $M'$. Dies gilt dann auch auf $M$, und daher ist
\mavergleichskette
{\vergleichskette
{ \pi
}
{ = }{ { \left( \prod_j \tau_j \right) } \tau
}
{ }{
}
{ }{
}
{ }{
}
}
{}{}{.}
\zwischenueberschrift{Das Signum einer Permutation}
\inputdefinition
{}
{
Es sei
\mavergleichskette
{\vergleichskette
{ M
}
{ = }{ { \{ 1 , \ldots , n \} }
}
{ }{
}
{ }{
}
{ }{
}
}
{}{}{}
und sei $\pi$ eine
\definitionsverweis {Permutation}{}{}
auf $M$. Dann heißt die Zahl
\mavergleichskettedisp
{\vergleichskette
{ \operatorname{sgn}(\pi)
}
{ =} { \prod_{ i < j } \frac{ \pi( j ) - \pi( i )}{ j - i }
}
{ } {
}
{ } {
}
{ } {
}
}
{}{}{}
das \definitionswort {Signum}{}
\zusatzklammer {oder das \definitionswort {Vorzeichen}{}} {} {}
der Permutation $\pi$.
}
Das Signum ist
\mathkor {} {1} {oder} {-1} {,}
da im Zähler und im Nenner die bis auf das Vorzeichen gleichen Differenzen
\mathl{\pm ( j-i)}{} stehen. Es gibt für das Signum also nur zwei mögliche Werte. Bei
\mathl{\operatorname{sgn}(\sigma)=1}{} spricht man von einer
\definitionswortenp{geraden Permutation}{} und bei
\mathl{\operatorname{sgn}(\sigma)=-1}{} von einer
\definitionswortenp{ungeraden Permutation}{.}
\inputdefinition
{}
{
Es sei
\mavergleichskette
{\vergleichskette
{ M
}
{ = }{ { \{ 1 , \ldots , n \} }
}
{ }{
}
{ }{
}
{ }{
}
}
{}{}{}
und sei $\pi$ eine
\definitionsverweis {Permutation}{}{}
auf $M$. Dann heißt ein Indexpaar
\mavergleichskettedisp
{\vergleichskette
{i
}
{ <} {j
}
{ } {
}
{ } {
}
{ } {
}
}
{}{}{}
ein \definitionswort {Fehlstand}{} von $\pi$, wenn
\mavergleichskette
{\vergleichskette
{ \pi (i)
}
{ > }{ \pi (j)
}
{ }{
}
{ }{
}
{ }{
}
}
{}{}{}
ist.
}
\inputfaktbeweis
{Permutation/Signum über Fehlstände/Fakt}
{Lemma}
{}
{
\faktsituation {}
\faktvoraussetzung {Es sei
\mavergleichskette
{\vergleichskette
{ M
}
{ = }{ { \{ 1 , \ldots , n \} }
}
{ }{
}
{ }{
}
{ }{
}
}
{}{}{}
und sei $\pi$ eine
\definitionsverweis {Permutation}{}{}
auf $M$. Es sei
\mavergleichskette
{\vergleichskette
{k
}
{ = }{ { \# \left( F \right) }
}
{ }{
}
{ }{
}
{ }{
}
}
{}{}{}
die Anzahl der
\definitionsverweis {Fehlstände}{}{}
von $\pi$.}
\faktfolgerung {Dann ist das
\definitionsverweis {Signum}{}{}
von $\pi$ gleich
\mavergleichskettedisp
{\vergleichskette
{ \operatorname{sgn}(\pi)
}
{ =} { (-1)^k
}
{ } {
}
{ } {
}
{ } {
}
}
{}{}{.}}
\faktzusatz {}
\faktzusatz {}
}
{
Wir schreiben
\mavergleichskettealign
{\vergleichskettealign
{ \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
}
}
{}
{}{,}
da nach dieser Umordnung sowohl im Zähler als auch im Nenner das Produkt aller positiven Differenzen steht.
\inputbeispiel{}
{
Wir betrachten die Permutation
\wertetabellesechsausteilzeilen { $x$ }
{\mazeileundfuenf {1} {2} {3} {4} {5} }
{ {6
} }
{ $\sigma(x)$ }
{\mazeileundfuenf {2} {4} {6} {5} {3} }
{ {1} }
mit der Zyklendarstellung
\mathdisp {\langle 1 , 2, 4, 5, 3, 6 \rangle} { . }
Die Fehlstände sind
\mathdisp {(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
\mavergleichskette
{\vergleichskette
{ (-1)^9
}
{ = }{-1
}
{ }{
}
{ }{
}
{ }{
}
}
{}{}{}
gemäß
Fakt *****,
und die Permutation ist ungerade.
}
Das Signum ist ein Gruppenhomomorphismus im Sinne der folgenden Definition.
\inputdefinition
{}
{
Es seien
\mathkor {} {(G, \circ, e_G)} {und} {(H, \circ, e_H)} {}
\definitionsverweis {Gruppen}{}{.}
Eine
\definitionsverweis {Abbildung}{}{}
\maabbdisp {\psi} {G} {H
} {}
heißt \definitionswort {Gruppenhomomorphismus}{,} wenn die Gleichheit
\mavergleichskettedisp
{\vergleichskette
{ \psi( g \circ g')
}
{ =} { \psi (g) \circ \psi (g')
}
{ } {
}
{ } {
}
{ } {
}
}
{}{}{}
für alle
\mavergleichskette
{\vergleichskette
{g,g'
}
{ \in }{G
}
{ }{
}
{ }{
}
{ }{
}
}
{}{}{}
gilt.
}
\inputfaktbeweis
{Permutation/Signum/Gruppenhomomorphismus/Fakt}
{Satz}
{}
{
\faktsituation {}
\faktfolgerung {Die durch das
\definitionsverweis {Signum}{}{}
gegebene Zuordnung
\maabbeledisp {} {S_n} {\{1,-1\}
} {\pi} {\operatorname{sgn}(\pi)
} {,}
ist ein
\definitionsverweis {Gruppenhomomorphismus}{}{.}}
\faktzusatz {}
\faktzusatz {}
}
{
Es seien zwei Permutationen
\mathkor {} {\pi} {und} {\rho} {}
gegeben. Dann ist
\mavergleichskettealignhandlinks
{\vergleichskettealignhandlinks
{ \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)
}
}
{
\vergleichskettefortsetzungalign
{ =} { \prod_{ k < \ell } \frac{ \pi( \ell ) - \pi( k )}{ \ell - k } \operatorname{sgn}(\rho )
}
{ =} { \operatorname{sgn}(\pi) \operatorname{sgn}(\rho)
}
{ } {}
{ } {}
}
{}{.}
\inputfaktbeweis
{Permutation/Signum über Transpositionen/Fakt}
{Lemma}
{}
{
\faktsituation {}
\faktvoraussetzung {Es sei
\mavergleichskette
{\vergleichskette
{ M
}
{ = }{ { \{ 1 , \ldots , n \} }
}
{ }{
}
{ }{
}
{ }{
}
}
{}{}{}
und sei $\pi$ eine
\definitionsverweis {Permutation}{}{}
auf $M$. Es sei
\mavergleichskettedisp
{\vergleichskette
{ \pi
}
{ =} { \tau_1 \cdots \tau_r
}
{ } {
}
{ } {
}
{ } {
}
}
{}{}{}
als ein Produkt von $r$
\definitionsverweis {Transpositionen}{}{}
geschrieben.}
\faktfolgerung {Dann gilt für das
\definitionsverweis {Signum}{}{}
die Darstellung
\mavergleichskettedisp
{\vergleichskette
{ \operatorname{sgn}(\pi)
}
{ =} {(-1)^r
}
{ } {
}
{ } {
}
{ } {
}
}
{}{}{.}}
\faktzusatz {}
\faktzusatz {}
}
{
Die Transposition $\tau$ vertausche die beiden Zahlen
\mavergleichskette
{\vergleichskette
{ k
}
{ < }{ \ell
}
{ }{
}
{ }{
}
{ }{
}
}
{}{}{.}
Dann ist
\mavergleichskettealign
{\vergleichskettealign
{ \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)
}
}
{
\vergleichskettefortsetzungalign
{ =} { -1
}
{ } {}
{ } {}
{ } {}
}
{}{.}
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
\zusatzklammer {wegen der gleichen Indexmenge} {} {}
Minuszeichen wegkürzen.
Die Aussage folgt dann aus der Homomorphieeigenschaft.
\inputbemerkung
{}
{
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
\definitionsverweis {Fehlständen}{}{}
sprechen und die
\definitionsverweis {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
\mavergleichskettedisp
{\vergleichskette
{ \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
\maabbdisp {\varphi} {I} { { \{ 1 , \ldots , n \} }
} {.}
Die Permutation $\pi$ auf $I$ definiert auf
\mathl{{ \{ 1 , \ldots , n \} }}{} die Permutation
\mavergleichskette
{\vergleichskette
{ \pi'
}
{ = }{\varphi \pi \varphi^{-1}
}
{ }{
}
{ }{
}
{ }{
}
}
{}{}{.}
Sei
\mavergleichskette
{\vergleichskette
{\pi
}
{ = }{ \tau_1 \cdots \tau_r
}
{ }{
}
{ }{
}
{ }{
}
}
{}{}{}
eine Darstellung als Produkt von $r$ Transpositionen auf $I$. Dann gilt
\mavergleichskettedisp
{\vergleichskette
{ \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
\mavergleichskette
{\vergleichskette
{ \tau_j'
}
{ = }{ \varphi \tau_j \varphi^{-1}
}
{ }{
}
{ }{
}
{ }{
}
}
{}{}{.}
Dies sind ebenfalls Transpositionen, sodass die Parität von $r$ durch das Signum von $\pi'$ festgelegt ist.
}
\zwischenueberschrift{Die Leibnizformel für die Determinante}
\bild{ \begin{center}
\includegraphics[width=5.5cm]{\bildeinlesung {Gottfried_Wilhelm_Leibniz_c1700.jpg} }
\end{center}
\bildtext {Gottfried Wilhelm Leibniz (1646-1716)} }
\bildlizenz { Gottfried Wilhelm Leibniz c1700.jpg } {Johann Friedrich Wentzel d. Ä.} {AndreasPraefcke} {Commons} {PD} {http://archiv.bbaw.de/archiv/archivbestaende/abteilung-sammlungen/gesamtbestand-des-kunstbesitzes/gelehrtengemaelde/gelehrtengemalde-seiten/VZLOBO-0031.html}
\inputfaktbeweis
{Determinante/Leibnizformel/Fakt}
{Satz}
{}
{
\faktsituation {Für die
\definitionsverweis {Determinante}{}{}
einer
$n \times n$-\definitionsverweis {Matrix}{}{}
\mavergleichskettedisp
{\vergleichskette
{ M
}
{ =} { { \left( a_{ij} \right) }_{ij}
}
{ } {
}
{ } {
}
{ } {
}
}
{}{}{}
gilt}
\faktfolgerung {
\mavergleichskettedisp
{\vergleichskette
{ \det M
}
{ =} { \sum_{ \pi \in S_{ n } } \operatorname{sgn}(\pi ) a_{1 \pi (1)} \cdots a_{ n \pi( n)}
}
{ } {
}
{ } {
}
{ } {
}
}
{}{}{.}}
\faktzusatz {}
\faktzusatz {}
}
{
Wir führen Induktion über
\mavergleichskette
{\vergleichskette
{ n
}
{ \geq }{ 1
}
{ }{
}
{ }{
}
{ }{
}
}
{}{}{,}
wobei der Induktionsanfang klar ist. Es sei also
\mavergleichskette
{\vergleichskette
{ n
}
{ \geq }{ 2
}
{ }{
}
{ }{
}
{ }{
}
}
{}{}{.}
Die Menge der Permutationen
\mavergleichskette
{\vergleichskette
{ \pi
}
{ \in }{ S_n
}
{ }{
}
{ }{
}
{ }{
}
}
{}{}{}
kann man aufspalten, indem man nach
\mathl{\pi(1)}{} sortiert und die bijektive Abbildung
\maabbdisp {\pi {{|}}_{ \{2 , \ldots , n\} }} {\{2 , \ldots , n\} } { \{1 , \ldots , n\} \setminus \{i\}
} {}
als eine Permutation $\rho$ auf
\mathl{\{1 , \ldots , n-1\}}{} auffasst, indem man beide Mengen ordnungstreu mit
\mathl{\{1 , \ldots , n-1\}}{} identifiziert. Dies ergibt eine Bijektion
\mavergleichskette
{\vergleichskette
{ S_{n, i}
}
{ \cong }{ S_{n-1 }
}
{ }{
}
{ }{
}
{ }{
}
}
{}{}{,}
wobei hier
\mathl{S_{n, i}}{} die Menge der Permutationen auf
\mathl{{ \{ 1 , \ldots , n \} }}{} bezeichnet, die $1$ auf $i$ abbilden. Zwischen den Signa besteht dabei die Beziehung
\mavergleichskettedisp
{\vergleichskette
{ \operatorname{sgn}( \pi )
}
{ =} { (-1)^{i-1} \operatorname{sgn}( \rho )
}
{ =} { (-1)^{i+1} \operatorname{sgn}( \rho )
}
{ } {
}
{ } {
}
}
{}{}{,}
da man
\mathl{i-1}{} Transpositionen braucht, um die $i$-te Stelle und die erste Stelle zu vertauschen. Es besteht also insgesamt eine natürliche Bijektion
\mavergleichskettedisp
{\vergleichskette
{S_n
}
{ =} { \biguplus_{i \in \{1 , \ldots , n\} } S_{n, i }
}
{ =} { \biguplus_{i \in \{1 , \ldots , n\} } S_{n-1 }
}
{ } {
}
{ } {
}
}
{}{}{.}
Somit gilt
\mavergleichskettealignhandlinks
{\vergleichskettealignhandlinks
{ \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_{1 i} \sum_{ \pi \in S_{n,i} } \operatorname{sgn}( \pi ) \prod_{j = 2}^n a_{j \pi (j) }
}
{ =} { \sum_{i = 1}^n a_{1 i} \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}
}
}
{
\vergleichskettefortsetzungalign
{ =} { \det M
}
{ } {}
{ } {}
{ } {}
}
{}{,}
wobei $M_{1i}$ die Streichungsmatrix zur ersten Zeile und $i$-ten Spalte ist
\zusatzklammer {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.