×

On the abstract properties of linear dependence. (English) Zbl 0012.00404

Die folgenden Wege, eine endliche Menge zu einem ,,Matroid” zu machen, werden als gleichwertig erwiesen:
1. Weg: Axiomatischer Grundbegriff: Rang \(r(N)\) der Teilmenge \(N\) von \(M\); Axiome: der Rang der leeren Menge ist 0; ist \(N\leq M\), \(x\) ein Element aus \(M\), so ist \(r(N)\leq r(N+x)\leq r(N)+1\); ist \(N\leq M\) and sind \(x\) und \(y\) zwei nicht in \(N\) enthaltene Elemente aus \(M\), so folgt aus \(r(N+x)=r(N+y) = r(N)\) auch \(r(N+x+y) = r(N)\). Abgeleitete Begriffe: Verschwindungsgrad \(n(N)\) der Teilmenge \(N\) von \(M\) ist Elementezahl von \(N\), vermindert um den Rang von \(N\); Teilmengen \(N\) mit \(n(N) = 0\) sind unabhängig, die anderen abhängig; Basis ist eine maximale unabhängige Menge and Circuit eine abha\"ngige Teilmenge von \(M\) ohne echte abhüangige Teilmengen.
2. Weg: axiomatischer Grundbegriff: unabhängige Teilmenge. Axiome: jede Teilmenge einer unabhängigen Menge ist unabhängig; sind die \(k\)-elementige Menge \(N\) and die \((k+1)\)-elementige Menge \(N'\) beide unabhängig, so gibt es ein nicht zu \(N\) gehöriges Element \(x\) in \(N'\), so daß \(N+x\) unabhängig ist. Abgeleiteter Begriff: Rang der Teilmenge \(N\) von \(M\) ist die Elementezahl einer größten unabhängigen Teilmenge von \(N\).
3. Weg: Axiomatischer Grundbegriff: Basis. Axiome: keine echte Teilmenge einer Basis ist eine Basis; sind \(B\) und \(B'\) Basen, \(x\) in \(B\), so gibt es ein \(x'\) in \(B'\), so daß \(B-x+x'\) eine Basis ist. Abgeleiteter Begriff: unabhängig ist jede Teilmenge einer Basis.
4. Weg: Axiomatischer Grundbegriff: Circuit. Axiome: keine echte Teilmenge eines Circuit ist ein Circuit; haben die Circuits \(C\) und \(D\) das Element \(x\) gemein, so ist \(C+D-x\) Vereinigung einer Menge von Circuits. Abgeleiteter Begriff: Rang der leeren Menge ist Null; Rang von \(N+x\) ist = Rang von \(N\), wenn es einen \(x\) enthaltenden Circuit in \(N+x\) gibt, sonst \(=1 +\) Rang von \(N\).
Das Matroid \(M\) heißt separabel, wenn es zwei nicht leere, elementfremde Teilmengen \(M'\) und \(M''\) von \(M\) gibt, so daß \(M = M' +M''\) und \(r(M) = r(M')+r(M'')\) ist, sonst nichtseparabel. Jedes Matroid läßt sich auf eine and nur eine Weise in größte nichtseparable Teile, die Komponenten des Matroids, zerlegen. Ein Matroid ist dann and nur dann ein Circuit, wenn es nichtseparabel ist and den Verschwindungsgrad 1 hat. Zwei Elemente gehören dann and nur dann zu derselben Komponente des Matroids, wenn es einen beide enthaltenden Circuit gibt.
Die Matroide \(M\) und \(M'\) heißen dual, wenn es eine eineindeutige Abbildung \(f\) der Elemente von \(M\) auf die von \(M'\) gibt, so daß \(r(M' - f(N))= r(M') - n(N)\) für jede Teilmenge \(N\) von \(M\) gilt. Zu jedem Matroid gibt es ein und im wesentlichen nur ein duales. Zwei Matroide sind dann and nur dann dual, wenn es eine eineindeutige Abbildung des einen auf das andere gibt, bei der Basen in die Komplemente von Basen übergehen. Matroide sind dann and nur dann dual, wenn ihre Komponenten es sind.
Die Reihen einer Matrix stellen ein Matroid dar; aber nicht jedes Matroid kann in dieser Weise gewonnen werden. Es wird eine Charakterisierung der Matroide gegeben, die aus Matrizen mit Koeffizienten aus dem Primkorper der Charakteristik 2 gewonnen werden können.
Die Begriffsbildungen finden Anwendungen in (und stammen aus) der Graphentheorie. [Vgl. Verf., Trans. Am. Math. Soc. 34, 339–362 (1932; Zbl 0004.13103).]
[Vgl. auch das Referat im JFM 61.0073.03.]

MSC:

15A03 Vector spaces, linear dependence, rank, lineability
05B35 Combinatorial aspects of matroids and geometric lattices
PDFBibTeX XMLCite
Full Text: DOI