Matroide < Lineare Algebra < Hochschule < Mathe < Vorhilfe
|
Hallo Zusammen,
| Aufgabe | | Sei $A [mm] \in \IR^{n \times n}$. [/mm] Es seien [mm] $c_1,\ldots,c_n \in \IR^n$ [/mm] Spalten von [mm] $A\!$ [/mm] und [mm] $\mathcal{I} \subseteq 2^{\left\{1,\ldots,n\right\}}$ [/mm] mit $I [mm] \in \mathcal{I} :\gdw \left\{c_i\,|\,i \in I \right\}$ [/mm] linear unabhängig, gegeben. Zeigen Sie: [mm] $\left(\left\{1,\ldots,n\right\}, \mathcal{I}\right)$ [/mm] ist ein Matroid. |
Idee:
Zum Nachweis der Matroid-Eigenschaft müssen folgende 3 Dinge überprüft werden:
[m]\begin{gathered}
\left( {\texttt{a}} \right)\quad \left| {\left\{ {1, \ldots ,n} \right\}} \right| < \infty \hfill \\
\left( \texttt{b} \right)\quad \mathcal{I}\,{\texttt{darf nur unabhängige Teilmengen aus }}\left\{ {1, \ldots ,n} \right\}{\texttt{ enthalten}}{\texttt{, so da{\ss}}} \hfill \\
\quad \quad \;\; \forall D \in \mathcal{I}:C \subseteq D \Rightarrow C \in \mathcal{I} \hfill \\
\left( \texttt{c} \right)\quad \forall C,D \in \mathcal{I}:\left| C \right| < \left| D \right| \Rightarrow \exists b \in D - C:C + \left\{ b \right\} \in \mathcal{I} \hfill \\
\end{gathered}[/m]
Eigenschaft (a) folgt aus der Definition dieser Menge. Man muß sich also auf die anderen beiden Eigenschaften konzentrieren:
zu (b):
Wir wenden den Gauss-Algorithmus auf [mm] $A\!$ [/mm] an. Nach der Anwendung dieses Algorithmus erhalten wir [mm] $\operatorname{rang}(A)$ [/mm] linear unabhängige Spalten von [mm] $A\!$. [/mm] Dann gibt es aber eine Menge $K [mm] \in \mathcal{I}$ [/mm] mit [mm] $\left| K \right| [/mm] = [mm] \operatorname{rang}A$. [/mm] Es gilt für $K' [mm] \subseteq [/mm] K$, $K' [mm] \in \mathcal{I}$, [/mm] da sich doch die Eigenschaft der linearen Unabhängigkeit für [mm] $c_i$ [/mm] nicht ändert, wenn wir weniger linear unabhängige Spalten betrachten (hier muß man wohl über Unterverktorräume argumentieren?). Damit wäre (b) gezeigt.
zu c):
Ich weiß leider nicht, was es hier zu zeigen gibt. Nach dem Anwenden des Gauss-Algorithmus auf [mm] $A\!$, [/mm] nehmen wir uns eine bestimmte Anzahl Spalten und nummerieren diese durch Elemente aus $K [mm] \in \mathcal{I}$. [/mm] Jetzt betrachten wir die restlichen nicht durchnummerierten Spalten (wobei es von diesen mehr geben soll als von den Durchnummerierten) und nummerieren diese durch Elemente aus $K' [mm] \in \mathcal{I}$. [/mm] Es gilt jetzt also [mm] $\left| K \right| [/mm] < [mm] \left| K' \right|$. [/mm] Beide Mengen an durchnummerierten Spalten sind linear unabhängig. Füge wir nun eine zusätzliche Spalte mit einer Nummer aus [mm] $K'\!$ [/mm] zu der Menge der Spalten mit einer Nummer aus [mm] $K\!$ [/mm] hinzu, so erhalten wir trotzdem linear unabhängige Spalten. Damit wäre auch c) gezeigt.
Danke für eure Hilfe!
Viele Grüße
Karl
|
|
| |
|
| Status: |
(Antwort) fertig  | | Datum: | 19:03 Do 23.06.2005 | | Autor: | DaMenge |
Hallo Karl,
ist dir klar, was hier deine Grundmenge E und dein Unabhängigkeitssystem sind?
Also dein E ist hier einfach nur n Vektoren (die repräsentiert werden durch die Spaltenindecies i und die Matrix A) - deine unabhängige Menge sind Mengen von Vektoren, die untereinander linear unabhängig sind.
(auch hier wieder die Repräsentation über den Index)
deshalb folgen alle Kriterien aus der Linearen Algebra !!
a) klar, endliche Matrix hat nur endlichg viele Spaltenvektoren
b) eine Menge von linear unabhängigen Vektoren bleibt es, wenn man Vektoren daraus entfernt.
c) du hast zwei linear unabhängige Vektorenmengen C und D und |C|<|D| (, aber die können schon disjunkt sein), dann folgt wieder aus LA (entspr. Satz raussuchen), dass es einen Vektor aus D gibt, so dass C und dieser Vektor immernoch unabhängig sind.
Das war es schon - übrigens darfst du die Vektoren nicht einfach durch nen Gauß-algo verändern, denn die Vektoren sind fest (aber beliebig) vorgegeben.
viele Grüße
DaMenge
|
|
|
| |
|
Hallo DaMenge,
> c) du hast zwei linear unabhängige Vektorenmengen C und D
> und |C|<|D| (, aber die können schon disjunkt sein), dann
> folgt wieder aus LA (entspr. Satz raussuchen), dass es
> einen Vektor aus D gibt, so dass C und dieser Vektor
> immernoch unabhängig sind.
Der einzige Satz, wo ich denke, er könne mir helfen, ist der Steinitzsche Austauschsatz. Ich habe versucht dessen Formulierung auf meinen Fall zu übertragen aber das ist hier irgendwie verzwickt:
[mm] $M\!$ [/mm] sei eine endliche linear unabhängige Teilmenge des endlichdimensionalen Vektorraums [mm] $V\!$, [/mm] und [mm] $B\!$ [/mm] sei eine Basis von [mm] $V\!$. [/mm] Dann gibt es eine Teilmenge [mm] $B'\!$ [/mm] von [mm] $B\!$, [/mm] so daß $M [mm] \cup [/mm] B'$ eine Basis von [mm] $V\!$ [/mm] ist. Diese hat genauso viele Elemente wie [mm] $B\!$.
[/mm]
Aber was sind in meinem Fall $M, V, [mm] B\!$ [/mm] und [mm] $B'\!$?
[/mm]
[mm] $M\!$ [/mm] ist doch [mm] $\left\{c_i\,|\,i \in I\right\}$ [/mm] mit $I [mm] \in \mathcal{I}$, [/mm] oder? Aber was ist [mm] $B\!$? [/mm] Wo finde ich bei meiner Aufgabenstellung die Basis?
Vielen Dank!
Viele Grüße
Karl
|
|
|
| |
|
| Status: |
(Antwort) fertig | | Datum: | 16:47 Sa 25.06.2005 | | Autor: | DaMenge |
Hallo Karl,
dein zitierter Satz ist sicher hilfreich, aber ich denke nur in Kombination mit dem Basisergänzungssatz zu gebrauchen, denn damit bastelst du dir deine gesuchte Basis B:
also V ist natürlich der von A induzierte $ [mm] \IR^n [/mm] $ und C und D seien linear unabhängige Vektorenmengen mit |C|<|D|
jetzt konstruiere die Basis B des $ [mm] \IR^n [/mm] $ durch den ergänzungssatz mit D, d.h. du fügst noch (n-|D|) viele lin. unabhängige Vektoren dazu und hast damit B konstruiert.
so, jetzt kannst du den Satz verwenden, den du zitiert hast, wobei M=C ist, d.h. du findest eine Teilmenge B' von B so dass $ C [mm] \cup [/mm] B' $ linear unabhängig ist und Dimension n hat.
Wenn du nun bedenkst, wie groß B' sein muss, erkennt man schnell, dass ein Vektor d aus D geben muss, so dass $ C [mm] \cup [/mm] d $ immernoch linear unabhängig ist - und das wolltest du ja nur zeigen.
(bedenke hier im letzten Schritt, was passiert, wenn C (teilweise) in D liegt)
viele Grüße
DaMenge
|
|
|
| |
|
Hallo DaMenge!
> Wenn du nun bedenkst, wie groß B' sein muss, erkennt man
> schnell, dass ein Vektor d aus D geben muss, so dass [mm]C \cup d[/mm]
> immernoch linear unabhängig ist - und das wolltest du ja
> nur zeigen.
> (bedenke hier im letzten Schritt, was passiert, wenn C
> (teilweise) in D liegt)
Irgendwie komme ich hier noch nicht weiter. Ich verstehe nicht, wie ich die größe von B' abschätzen soll. Aber B' ist doch bestimmt nicht die leere Menge, also hat B' doch mindestens einen weiteren Vektor, denn ich zu C hinzufügen kann. Damit wäre die Argumentation schon abgeschlossen, oder? Muß ich den die Größe von B' abschätzen?
Grüße
Karl
|
|
|
| |
|
| Status: |
(Antwort) fertig | | Datum: | 19:24 Sa 25.06.2005 | | Autor: | DaMenge |
Hi nochmal,
ok, also du willst ja zeigen, dass es einen Vektor d aus D gibt, so dass C und d immernoch lin.unabh. sind.
Die Idee ist nun, dass in B' auf jeden Fall ein d aus D enthalten sein muss.
Wenn du dies zeigen kannst, dann gilt
$ (C [mm] \cup [/mm] B') $ = neue Basis $ [mm] \Rightarrow [/mm] $ $ (C [mm] \cup [/mm] d) $ lin. unabhängig !
Und um zu zeigen, dass ein d aus D in B' sein muss, sollte man sich überlegen, wie groß B' ist, es ist nämlich: |B'|=n-|C|
in B' können aber höchstens (n-|D|) viele Vektoren nicht aus D sein, weil aber |C|<|D| ist, ist |B'|>n-|D| und deshalb muss ein d aus D in B' enthalten sein.
Ich hoffe dir ist nun klarer, worauf ich hinaus wollte.
Ich sollte evtl. nächstemal die Beweisidee klarer formulieren.
viele Grüße
DaMenge
|
|
|
| |
|
Hallo DaMenge,
> Und um zu zeigen, dass ein d aus D in B' sein muss, sollte
> man sich überlegen, wie groß B' ist, es ist nämlich:
> |B'|=n-|C|
Bist Du dir da ganz sicher? Müßte das nicht vorraussetzen, daß [mm] $B'\!$ [/mm] und [mm] $C\!$ [/mm] disjunkt sind?
> in B' können aber höchstens (n-|D|) viele Vektoren nicht
> aus D sein, weil aber |C|<|D| ist, ist |B'|>n-|D| und
> deshalb muss ein d aus D in B' enthalten sein.
Könntest Du mir dieses Argument noch etwas ausführlicher zeigen? Ich versuche mir gerade die Situation im Beweis zu veranschaulichen:
[Dateianhang nicht öffentlich]
Ist dieses Bild so richtig? Vielleicht verstehe ich es ja besser, wenn Du es mir an dem Bild erklären könntest. 
Danke!
Viele Grüße
Karl
Dateianhänge:
Anhang Nr. 1 (Typ: gif) [nicht öffentlich]
|
|
|
| |
|
| Status: |
(Antwort) fertig | | Datum: | 12:30 So 26.06.2005 | | Autor: | DaMenge |
Guten Morgen Karl,
> > |B'|=n-|C|
>
> Bist Du dir da ganz sicher? Müßte das nicht vorraussetzen,
> daß B' und C disjunkt sind?
Also es soll doch nach dem Austauschsatz $ B' [mm] \cup [/mm] C $ eine Basis sein, deshalb kann kein c aus C in B' sein, denn sonst wäre diese Menge ja sicher nicht unabhängig.
AAAHHHHHHHH - moment : deine Version des Austauschsatzes benutzt ja nur die Vereinigung, wo doppelte Elemente ja nicht doppelt danach vorkommen. Eigentlich heißt der Austauschsatz so (vgl. Fischer) :
Wenn du eine Basis B von V hast, kannst du |C| viele Vektoren aus B mit denen aus C austauschen - nach dieser Austauschung ist $ B'=B [mm] \backslash [/mm] C $ und daher |B'|=n-|C|
> > in B' können aber höchstens (n-|D|) viele Vektoren nicht
> > aus D sein, weil aber |C|<|D| ist, ist |B'|>n-|D| und
> > deshalb muss ein d aus D in B' enthalten sein.
>
> Könntest Du mir dieses Argument noch etwas
> ausführlicher zeigen?
ok, also wie haben wir B bekommen?
die Basis B haben wir aus D und einer Ergänzung von (n-|D|) weiteren lin. unabh. Vektoren aus $ [mm] \IR^n [/mm] $ zusammengesetzt, d.h. in B gibt es nur (n-|D|) viele Vektoren die nicht aus D sind.
jetzt folgt aus |C|<|D| und |B'|=n-|C|, dass |B'|=n-|C| > n-|D|
(denn du ziehst ja jetzt mehr von n ab, also ist die rechte Seite kleiner!)
B' ist eine Teilmenge aus B und diese fügen wir ja zu C hinzu.
Weil wir jetzt mehr als (n-|D|) viele Vektoren aus B zu C hinzufügen muss mindestens einer davon aus D kommen (denn nur (n-|D|) kommen nicht aus D - siehe oben.)
und deshalb ist ein d aus D in B' enthalten, wobei $ B' [mm] \cup [/mm] C $ eine Basis also insbesondere lin. unabh. ist und deshalb ist es auch $ C [mm] \cup [/mm] d $
noch eine Anmerkung zum Schubfachprinzip: wenn du zwei Schubfächer hast (die die Namen tragen "ist nicht in D" und "ist in D") und du höchstens (n-|D|) viele Kugeln in "ist nicht in D" reinlegen darfst, aber mehr Kugeln auf diese Schubfächer verteilen musst, dann muss danach mindestens eine Kugel in "ist in D" sein.
> Ist dieses Bild richtig? Vielleicht
> verstehe ich es besser, wenn Du es mir an dem Bild
> erklären könntest.
Wie gesagt, Bilder kommen später - mein Magen grummelt schon...
Deine rechte Hälfte des Bildes suggestiert, dass du B' nicht als Teilmenge von B wählst, sondern irgendwie aus dem $ [mm] \IR^n [/mm] $, d.h. eigentlich musst du n-|C| Vektoren aus B nehmen und an C hinanfügen - dann folgt, dass mind. einer dieser angefügten Vektoren aus D sein muss.
Hier muss man aber jetzt der Anschaulichkeit vier Fälle unterscheiden:
1) C und D sind disjunkt und (der Rest von B) und C auch, aber hier kann man obige Überlegungen am besten einsehen:
[Dateianhang nicht öffentlich]
2) C und D sind nicht disjunkt, aber der Rest von B und C sind disjunkt, hier muss man trotzdem noch (n-|C|) Vektoren aus B finden, die nicht in C sind, deshalb hat sich zwar das mögliche D verringert, aber ein d muss immernoch in B' liegen :
[Dateianhang nicht öffentlich]
3) C und D sind disjunkt, ein paar vektoren von C sind in den (n-|D|) restlichen Vektoren von B, hier hat sich nun die Anzahl der möglichen Vektoren aus B' verringert, die nicht in D liegen, denn ein paar von denen darf man nun nicht mehr verwenden, weil sie ehh schon in C liegen:
[Dateianhang nicht öffentlich]
4)noch ne Mischung aus 2) und 3)
[Dateianhang nicht öffentlich]
sind zwar nicht so schöne Bildchen wie deine, aber ich hoffe, man kann es noch erkennen.
DaMenge
Dateianhänge:
Anhang Nr. 1 (Typ: jpg) [nicht öffentlich]
Anhang Nr. 2 (Typ: jpg) [nicht öffentlich]
Anhang Nr. 3 (Typ: jpg) [nicht öffentlich]
Anhang Nr. 4 (Typ: jpg) [nicht öffentlich]
|
|
|
| |
|
Hallo DaMenge,
Ich denke, ich habe das Argument jetzt begriffen. Wir nehmen das [mm] $D\!$, [/mm] reichern es um [mm] $n-\left|D\right|$ [/mm] Elemente an und kriegen die Basis [mm] $B\!$ [/mm] von [mm] $\IR^n$. [/mm] Jetzt tauschen wir Elemente aus [mm] $B\!$ [/mm] mit [mm] $C\!$ [/mm] (Findet dabei ein echter Austausch statt oder "überschreiben" die Elemente aus [mm] $C\!$ [/mm] quasi einige Elemente aus [mm] $B\!$? [/mm] Anschließend nehmen wir uns eine Teilmenge [mm] $B'\!$ [/mm] aus [mm] $B\!$, [/mm] welche dann entsprechend [mm] $n-\left|C\right|\!$ [/mm] Elemente haben muß und reichern [mm] $C\!$ [/mm] mit [mm] $B'\!$ [/mm] an, richtig? Wegen [mm] $n-\left|C\right| [/mm] > [mm] n-\left|D\right|$ [/mm] muß in dieser neuen Basis $C [mm] \subset [/mm] B'$ auch mindestens ein $d [mm] \in [/mm] D$ dabei sein.
Ich versuch' das jetzt mal nachzuvollziehen:
Anfang:
D: (![[kleeblatt]](/images/smileys/kleeblatt.gif "[kleeblatt]") , , , , )
C: (![[snoopysleep]](/images/smileys/snoopysleep.gif "[snoopysleep]") , , )
Schritt 1 (Anreichern von D mit n-|D| beliebigen linear unabhängigen Vektoren):
B: (, , , , ,  )
C: (, , )
Schritt 2 (Austausch mit C vornehmen):
B: (, , , , , )
C: (, , )
Schritt 3 (Menge B' bestimmen):
z.B. B': (, , )
Schritt 4 (Menge $C [mm] \cup [/mm] B'$):
$C [mm] \cup [/mm] B'$: (, , , , , )
Stimmt das so?
Viele Grüße
Karl
|
|
|
| |
|
| Status: |
(Antwort) fertig | | Datum: | 19:11 So 26.06.2005 | | Autor: | DaMenge |
Hallo lieber Karl,
du hast es verstanden !!
nur noch ne Kleinigkeit:
> Ich denke, ich habe das Argument jetzt begriffen. Wir
> nehmen uns also das D, reichern es um n-|D| Elemente an und
> kriegen die Basis B von [mm]\IR^n[/mm]. Jetzt tauschen wir Elemente
> aus B mit C (Findet dabei ein echter Austausch statt oder
> "überschreiben" die Elemente aus C quasi einige Elemente
> aus B? Anschließend nehmen wir uns eine Teilmenge B' aus B,
> welche dann entsprechend n-|C| Elemente haben muß und
> reichern C mit B' an.
Das wäre eigentlich doppelt gemoppelt !
Der Austauschsatz geht auch eigentlich nur so, wie ich ihn geschrieben habe, d.h. du ersetzt ein paar Elemente aus B mit denen aus C und hast damit deine neue Basis - fertig aus !
B' habe einfach nochmal verwendet um die Idee bei deiner Version zu illustrieren, denn man kann aus B eine Teilmenge B' mit n-|C| Vektoren finden, so dass $ [mm] C\cup [/mm] B' $ eine Basis ist (genau die, die wir eben in meiner Version auch bekommen haben)
Deine Bildchen finde ich übrigens sehr Klasse.
Schritt 4 musst du nun natürlich nicht mehr machen, denn der wurde ja schon in Schritt 2 gemacht - Schritt 3 machst du um zu argumentieren, dass ein Kleeblatt in B' enthalten sein muss.
viele grüße
DaMenge
|
|
|
| |
|
| Status: |
(Mitteilung) Reaktion unnötig  | | Datum: | 20:02 So 26.06.2005 | | Autor: | Karl_Pech |
Hallo DaMenge,
Danke für deine Hilfe!
Viele Grüße
Karl
|
|
|
|
