| |
| Autor |
  Permutationsmatrizen, orthogonale Matrizen |
|
Talvin
Ehemals Aktiv 
Dabei seit: 13.03.2021
Mitteilungen: 34
Wohnort: Köln
 |  Themenstart: 2021-05-13
|
Hallo zusammen,
ich habe folgende Aufgabe gemacht und möchte gerne wissen, ob ihr mit der Lösung einverstanden seid und bräuchte mal einen Tipp für den dritten Teil:
\
Es Seien e_1,...,e_n \in\IR die Einheitsvektoren, aufgefasst als Spaltenvektoren. Eine Matrix A\in\IR heißt Permutationsmatrix, wenn es eine Permutation \pi\in S_n mit A:=E_\pi := (e_\pi(1),...,e_\pi(n)) gibt.
Man zeige:
(i) Jede Permutationsmatrix ist invertierbar, und die kanonische Abbildung \sigma: S_n -> GL(n,\IR), \pi -> E_\pi, definiert einen injektiven Gruppenhomomorphismus.
Invertierbar ist eine Permutationsmatrix, weil man mittels einfachen Spaltentausches wieder die Einheitsmatrix erhält.
Wenn man für $\pi,\delta\in S_n$ und die Permutationsmatrizen $A:=E_{\pi}, B:=E_{\delta}$ mal $\sigma(\pi)\cdot\sigma(\delta) = A\cdot B =: C$ betrachtet, sieht man
$$c_{lk} = \sum_{j=1}^n a_{lj}\cdot b_{jk} =
\begin{cases}
1, & \text{falls j ex. mit $a_{lj}=b_{jk}=1$, also $\delta(k)=j, \pi(j) = l$}.\\
0, & \text{sonst}.
\end{cases},$$
also, dass $C$ gerade $\sigma(\pi\circ\delta)$ ist.
$\sigma$ ist also ein Gruppenhomomorphismus und die Injektivität ergibt sich dann daraus, dass offenbar nur die identische Permutation auf die Einheitsmatrix abgebildet wird.
\
(ii) Es gilt E_\pi \in O(n) für alle \pi\in S_n.
Die vertauschten Einheitsvektoren bilden eine ONB, also ist $E_{\pi}$ immer orthogonal.
\
(iii) Es sei A = (a_ij) \in O(n) eine orthogonale Matrix mit Koeffizienten a_ij >= 0. Dann ist A bereits eine Permutationsmatrix.
Wenn A eine orthogonale Matrix ist, müssen die Spalten eine ONB bilden. Dabei muss für alle Einträge der Matrix schonmal $a_{ij} \leq 1$ gelten, weil sonst der j-te Spaltenvektor nicht normiert sein kann.
Mir fällt nichts besseres, als die sehr schwammige Begründung ein, dass wegen $a_{ij} \geq 0$ aus "kombinatorischen" Gründen keine Spalte mehr als einen Eintrag haben kann, weil sonst die Spalten keine Basis mehr bilden.
Hier wäre ich für eine vernünftige Argumentation oder einen Tipp sehr dankbar, ich komme nicht drauf 🙁
Danke!
LG Tim
(Bosch, Lineare Algebra, 7.5 Aufgabe 3, für die, die das irgendwann vllt. mal suchen, es gibt ja leider kaum Lösungen im Buch)
|
 Profil
|
Nuramon
Senior 
Dabei seit: 23.01.2008
Mitteilungen: 3738
 |  Beitrag No.1, eingetragen 2021-05-13
|
\(\begingroup\)\(\renewcommand{\Re}{\operatorname{Re}}
\renewcommand{\Im}{\operatorname{Im}}
\newcommand{\End}{\operatorname{End}}
\newcommand{\id}{\operatorname{id}}
\newcommand{\GL}{\operatorname{GL}}
\newcommand{\im}{\operatorname{im}}
\newcommand{\sgn}{\operatorname{sgn}}
\newcommand{\d}{{\rm d}}
\newcommand{\rg}{\operatorname{rg}}
\newcommand{\spur}{\operatorname{spur}}
\newcommand{\Hom}{\operatorname{Hom}}
\newcommand{\tr}{\operatorname{tr}}
\newcommand{\opn}{\operatorname}\)
Hallo,
(i) und (ii) sind richtig. Bei (i) kann man die Gleichung $E_{\pi\circ \delta} = E_{\pi}E_{\delta}$ auch prüfen, indem man für jeden Basisvektor $e_i$ die Gleichung $E_{\pi\circ \delta}e_i = E_{\pi}E_{\delta}e_i$ nachrechnet. Das ist übersichtlicher als jeden Koeffizienten einzeln auszurechnen.
zu (iii):
Angenommen in der $j$-ten Spalte von $A$ sind genau $k$ Nulleinträge. Zeige, dass die restlichen Spalten von $A$ dann in einem Unterraum der Dimension $k$ enthalten sein müssen.\(\endgroup\)
|
Profil
|
Talvin
Ehemals Aktiv
Dabei seit: 13.03.2021
Mitteilungen: 34
Wohnort: Köln
| Beitrag No.2, vom Themenstarter, eingetragen 2021-05-19
|
Hallo Nuramon,
danke für deine Antwort, ich hab leider erst jetzt wieder Zeit gehabt, mich damit weiter zu beschäftigen.
Das zu der (ii) ist auf jeden Fall eine gute Idee, zu der (iii) hab ich jetzt mit deiner Hilfe Folgendes:
Angenommen, $a_j$ hat genau k Nulleinträge.
Wenn die restlichen Vektoren nicht in einem Unterraum der Dimension k enthalten wären, gäbe es eine Zeile i, sodass $0 < a_{ij} \leq a_{il}$ für ein $l\neq j$ gilt.
Dann ist aber das (Standard-)Skalarprodukt von $a_j$ und $a_l$ größer als 0 und die Spalten sind also keine ONB.
Daraus folgt dann, dass jede Spalte nur einen Eintrag haben kann und diese müssen dann alle 1 sein, weil die Vektoren sonst nicht normiert wären.
So ich hoffe das stimmt jetzt so, vielen Dank nochmal!
|
Profil
|
Nuramon
Senior
Dabei seit: 23.01.2008
Mitteilungen: 3738
| Beitrag No.3, eingetragen 2021-05-19
|
\(\begingroup\)\(\renewcommand{\Re}{\operatorname{Re}}
\renewcommand{\Im}{\operatorname{Im}}
\newcommand{\End}{\operatorname{End}}
\newcommand{\id}{\operatorname{id}}
\newcommand{\GL}{\operatorname{GL}}
\newcommand{\im}{\operatorname{im}}
\newcommand{\sgn}{\operatorname{sgn}}
\newcommand{\d}{{\rm d}}
\newcommand{\rg}{\operatorname{rg}}
\newcommand{\spur}{\operatorname{spur}}
\newcommand{\Hom}{\operatorname{Hom}}
\newcommand{\tr}{\operatorname{tr}}
\newcommand{\opn}{\operatorname}\)
Das klingt als hättest du die Idee verstanden. Aber nur zur Sicherheit: Von welchem Unterraum mit Dimension $k$ ist hier die Rede?
Die Ungleichung $a_{ij}\leq a_{il}$ muss nicht gelten. Es reicht aber bereits $a_{il}a_{ij}>0$.\(\endgroup\)
|
Profil
|
Talvin
Ehemals Aktiv
Dabei seit: 13.03.2021
Mitteilungen: 34
Wohnort: Köln
|  Beitrag No.4, vom Themenstarter, eingetragen 2021-05-21
|
Hallo Nuramon,
stimmt, die Ungleichung ist quatsch (edit: könnte man aber oBdA annehmen nicht?), ich wollte nur sagen, dass beide Einträge größer 0 sind und damit eben auch deren Produkt, wie du sagst.
Wegen dem Unterraum musste ich jetzt doch nochmal genauer nachdenken, weil es mir dann doch nicht ganz so offensichtlich war, es vernünftig aufzuschreiben; hast mich auf jeden Fall erwischt.😁
Ich glaube im Endeffekt ist einfach der Unterraum, der von genau k der Einheitsvektoren $e_i$ (die zur Standardbasis von $\IR^n$ gehören) erzeugt wird, gemeint.
Wenn es so einen nicht gibt, sodass die besagten "restlichen Vektoren" darin enthalten sind, dann sind durch diese mehr als k verschiedene Zeilen durch Werte > 0 belegt.
Da die Spalten eine Basis bilden müssen, kann also jeder Vektor nur einen Eintrag haben, weil er sonst den anderen sozusagen Dimensionen klaut und alleine dafür zuständig wäre, mehr als eine Dimension aufzuspannen, was nicht geht.
(Wenn die restlichen Vektoren in einem Unterraum der dim K enthalten sind, können sie insb. nicht mehr als diesen Unterraum erzeugen)
Stimmt das?
|
Profil
|
Nuramon
Senior
Dabei seit: 23.01.2008
Mitteilungen: 3738
| Beitrag No.5, eingetragen 2021-05-22
|
\(\begingroup\)\(\renewcommand{\Re}{\operatorname{Re}}
\renewcommand{\Im}{\operatorname{Im}}
\newcommand{\End}{\operatorname{End}}
\newcommand{\id}{\operatorname{id}}
\newcommand{\GL}{\operatorname{GL}}
\newcommand{\im}{\operatorname{im}}
\newcommand{\sgn}{\operatorname{sgn}}
\newcommand{\d}{{\rm d}}
\newcommand{\rg}{\operatorname{rg}}
\newcommand{\spur}{\operatorname{spur}}
\newcommand{\Hom}{\operatorname{Hom}}
\newcommand{\tr}{\operatorname{tr}}
\newcommand{\opn}{\operatorname}\)
Was du schreibst stimmt alles, aber mir fehlt immer noch die konkrete Definition dieses Unterraums. Von welchen $k$ Einheitsvektoren wird der denn aufgespannt? Das hast du noch nicht näher angegeben.
\showon Auflösung
Es geht um den Unterraum, der aus all denen Vektoren besteht, die Nichtnulleinträge höchstens in den $k$ Zeilen haben, in denen die $j$-te Spalte Nulleinträge hat.
\showoff
\(\endgroup\)
|
Profil
|
Talvin
Ehemals Aktiv
Dabei seit: 13.03.2021
Mitteilungen: 34
Wohnort: Köln
|  Beitrag No.6, vom Themenstarter, eingetragen 2021-05-22
|
Ah du hast Recht!
Ich brauche ja die Aussage, dass die restlichen Vektoren genau in dem Unterraum, den du beschreibst, enthalten sind. Nicht in irgendeinem der dim k.
Das ist im Beweis wirklich unklar. Sehr gut, dass du nachgehakt hast👍
|
Profil
|
Talvin hat die Antworten auf ihre/seine Frage gesehen.
Talvin hat selbst das Ok-Häkchen gesetzt. |
|
All logos and trademarks in this site are property of their respective owner. The comments are property of their posters, all the rest © 2001-2023 by Matroids Matheplanet
This web site was originally made with PHP-Nuke, a former web portal system written in PHP that seems no longer to be maintained nor supported. PHP-Nuke is Free Software released under the GNU/GPL license.
Ich distanziere mich von rechtswidrigen oder anstößigen Inhalten, die sich trotz aufmerksamer Prüfung hinter hier verwendeten Links verbergen mögen.
Lesen Sie die
Nutzungsbedingungen,
die Distanzierung,
die Datenschutzerklärung und das Impressum.
[Seitenanfang]
|
Home / Seite ohne Frame
2023-09-30 16:09 U <
Wie unterstütze ich den Matheplaneten mit Geld?
