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

Gar nicht mehr lange! Wir wünschen schon jetzt frohe Weihnachten!

Die Pausenaufgabe

Aufgabe

Zeige, dass man jede endliche Permutation durch ein überschneidungsfreies Pfeildiagramm darstellen kann.

Übungsaufgaben

Aufgabe

Berechne für die Permutation

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

die Anzahl der Fehlstände und das Vorzeichen.

Aufgabe

Berechne für die Permutation ${}\sigma$ mit

${}P$	${}1$	${}2$	${}3$	${}4$	${}5$	${}6$	${}7$	${}8$	${}9$	${}10$
${}\sigma (P)$	${}7$	${}10$	${}3$	${}9$	${}5$	${}2$	${}4$	${}1$	${}8$	${}6$

die Potenzen ${}\sigma ^{2}$ und ${}\sigma ^{3}$ . Bestimme die Zyklendarstellung für diese drei Permutationen an.

Aufgabe *

Betrachte die Permutation ${}\tau \in S_{7}$ , die durch die Wertetabelle

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

gegeben ist.

Man gebe die Zyklendarstellung von ${}\tau$ an und bestimme den Wirkungsbereich.
Berechne ${}\tau ^{3}$ und die Ordnung von ${}\tau ^{3}$ .
Bestimme die Fehlstände von ${}\tau$ und das Vorzeichen (Signum) von ${}\tau$ .
Schreibe ${}\tau$ als Produkt von Transpositionen und bestimme erneut das Vorzeichen von ${}\tau$ .

Aufgabe *

Betrachte die beiden Permutationen

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

und

${}x$	${}1$	${}2$	${}3$	${}4$	${}5$	${}6$	${}7$	${}8$
${}\tau (x)$	${}4$	${}5$	${}2$	${}8$	${}6$	${}7$	${}1$	${}3$

Berechne ${}\sigma \tau$ und ${}\tau \sigma$ . Bestimme die Anzahl der Fehlstände und das Vorzeichen von ${}\tau$ . Man gebe die Zyklendarstellung von ${}\sigma$ und von ${}\sigma ^{3}$ an. Was ist die Ordnung von ${}\sigma$ ?

Aufgabe *

Wir betrachten die durch die Wertetabelle

${}x$	${}1$	${}2$	${}3$	${}4$	${}5$	${}6$	${}7$	${}8$
${}F(x)$	${}3$	${}5$	${}1$	${}7$	${}8$	${}2$	${}6$	${}4$

gegebene Abbildung ${}F$ von

{}M=\{1,2,\ldots ,8\}\,

in sich selbst.

Erstelle eine Wertetabelle für ${}F^{2}=F\circ F$ .
Erstelle eine Wertetabelle für ${}F^{3}=F\circ F\circ F$ .
Begründe, dass sämtliche iterierten Hintereinanderschaltungen ${}F^{n}$ bijektiv sind.
Bestimme für jedes ${}x\in M$ das minimale ${}n\in \mathbb {N} _{+}$ mit der Eigenschaft, dass
${}F^{n}(x)=x\,$

ist.
Bestimme das minimale ${}n\in \mathbb {N} _{+}$ mit der Eigenschaft, dass
${}F^{n}(x)=x\,$

für alle ${}x\in M$ ist.

Aufgabe

Zeige, dass durch die Zuordnung

S_{n}\times \{1,\ldots ,n+1\}\longrightarrow S_{n+1},\,(\varphi ,x)\longmapsto {\tilde {\varphi }},

mit

{}{\tilde {\varphi }}(k)={\begin{cases}\varphi (k){\text{ für }}k\leq n{\text{ und }}\varphi (k)<x\,,\\\varphi (k)+1{\text{ für }}k\leq n{\text{ und }}\varphi (k)\geq x\,,\\x{\text{ für }}k=n+1\,,\end{cases}}\,

eine wohldefinierte bijektive Abbildung gegeben ist.

Aufgabe

Gabi Hochster, Heinz Ngolo, Lucy Sonnenschein und Mustafa Müller wollen untereinander wichteln. Jede Person soll also genau von einer Person ein Geschenk bekommen, aber natürlich nicht von sich selbst. Wie viele Wichtelmöglichkeiten gibt es?

Aufgabe

Bestimme die Fixpunkte der Abbildung

f\colon \mathbb {R} \longrightarrow \mathbb {R} ,\,x\longmapsto x^{2}.

Aufgabe

Es sei ${}M$ eine Menge und es sei

F\colon M\longrightarrow M

eine Abbildung. Zeige, dass ${}F$ genau dann einen Fixpunkt besitzt, wenn der Durchschnitt des Graphen von ${}F$ mit der Diagonalen ${}\triangle ={\left\{(x,x)\in M\times M\mid x\in M\right\}}$ nicht leer ist.

Aufgabe

Berechne die Determinanten aller ${}3\times 3$ -Matrizen, bei denen in jeder Spalte und in jeder Zeile genau einmal ${}1$ und zweimal ${}0$ steht.

Aufgabe

Es sei ${}M={\{1,\ldots ,n\}}$ und sei ${}\pi$ eine Permutation auf ${}M$ . Die zugehörige Permutationsmatrix ${}M_{\pi }$ ist dadurch gegeben, dass

{}a_{\pi (i),i}=1\,

ist und alle anderen Einträge ${}0$ sind. Zeige, dass

{}\det M_{\pi }=\operatorname {sgn} (\pi )\,

ist.

Aufgabe *

a) Man gebe ein Beispiel für eine ${}4\times 4$ - Permutationsmatrix, bei der in jeder Diagonalen (Haupt-, Neben- und Gegendiagonalen) höchstens eine ${}1$ steht.

b) Zeige, dass es keine Lösung zu a) gibt, bei der ${}a_{11}=1$ ist.

Aufgabe

Es sei ${}K$ ein Körper und sei

{}M={\left\{{\begin{pmatrix}a&b\\c&d\end{pmatrix}}\mid a,b,c,d\in K,\,ad-bc\neq 0\right\}}\,

die Menge aller invertierbaren ${}2\times 2$ - Matrizen.

a) Zeige (ohne Bezug zur Determinante), dass ${}M$ mit der Matrizenmultiplikation eine Gruppe bildet.

b) Zeige (ohne Bezug zur Determinante), dass die Abbildung

M\longrightarrow K^{\times },\,{\begin{pmatrix}a&b\\c&d\end{pmatrix}}\longmapsto ad-bc,

ein Gruppenhomomorphismus ist.

Aufgabe

Bestimme mittels der Leibniz-Formel die Determinante der Matrix

{\begin{pmatrix}3&4&5\\9&8&7\\1&2&3\end{pmatrix}}.

Es sei ${}(G,e,\circ )$ eine Gruppe. Eine Teilmenge ${}H\subseteq G$ heißt Untergruppe von ${}G$ wenn folgendes gilt.

${}e\in H$ .
Mit ${}g,h\in H$ ist auch ${}g\circ h\in H$ .
Mit ${}g\in H$ ist auch ${}g^{-1}\in H$ .

Die Weihnachtsaufgabe für die ganze Familie

Aufgabe

Welches Bildungsgesetz liegt der Folge

1,\,11,\,21,\,1211,\,111221,\,312211,\,...

zugrunde?

(Es wird behauptet, dass diese Aufgabe für Grundschulkinder sehr einfach und für Mathematiker sehr schwierig ist.)

Aufgaben zum Abgeben

Aufgabe (2 Punkte)

Es sei ${}M$ eine Menge und sei ${}M=\biguplus _{i\in I}M_{i}$ eine Partition von ${}M$ , d.h. jedes ${}M_{i}$ ist eine Teilmenge von ${}M$ und ${}M$ ist die disjunkte Vereinigung der ${}M_{i}$ . Zeige, dass die Produktgruppe

\prod _{i\in I}\operatorname {Perm} \,(M_{i})

eine Untergruppe von ${}\operatorname {Perm} \,(M)$ ist.

Aufgabe (2 Punkte)

Zeige, dass jede gerade Permutation ${}\sigma \in S_{n}$ , ${}n\geq 3$ , ein Produkt aus Dreierzykeln ist.

Aufgabe (5 Punkte)

Es sei ${}\sigma$ ein Zykel der Ordnung ${}n$ . Zeige, dass man ${}\sigma$ als Produkt von ${}n-1$ Transpositionen schreiben kann, aber nicht mit einer kleineren Anzahl von Transpositionen.

Aufgabe (4 Punkte)

Es sei ${}m\geq n$ . Wie viele injektive Abbildungen gibt es von ${}{\{1,\ldots ,n\}}$ nach ${}\{1,\ldots ,m\}$ und wie viele surjektive Abbildungen gibt es von ${}{\{1,\ldots ,n\}}$ nach ${}\{1,\ldots ,m\}$ ?