On the abstract properties of linear dependence. (English) JFM 61.0073.03

Whitney, H.

Am. J. Math. 57, 509-533 (1935).

Die Arbeit enthält eine abstrakte Formulierung der bei der Untersuchung von Streckenkomplexen üblichen Untersuchungen über lineare Abhängigkeit. Man vergleiche hierzu frühere Arbeiten des Verf., insbesondere “Non-separable and planar graphs” [Trans. Am. Math. Soc. 34, 339–362 (1932; JFM 58.0608.01; Zbl 0004.13103)], deren Sätze sich hier zum Teil wiederfinden.
Ein System \(M\) von endlich vielen Elementen \(e_1\), \(e_2\), …, \(e_p\) heißt ein “Matroid”, wenn jeder Teilmenge \(N\) von \(M\) eine Zahl \(r(N)\) als ihr Rang zugeordnet ist, die folgenden Bedingungen genügt: \((R_1)\) der Rang der leeren Menge ist 0; \((R_2)\) für jedes \(e \in M\) ist \(r(N + e) = r(N) + k\), \(k=0\) oder 1; \((R_3)\) aus \(r(N + e_i) = r(N + e_j) = r(N)\), \(e_i \in M\), \(e_j \in M\), folgt \(r(N + e_i + e_j) = r(N)\). Die Nullität \(n(N)\) wird als Differenz zwischen Elementezahl und Rang von \(N\) definiert; \(n(N) = 0\) kennzeichnet die unabhängigen (d. h. aus voneinander unabhängigen Elementen bestehenden) Mengen, \(n(N) > 0\) die abhängigen. Jede maximale unabhängige Menge heißt Basis, jede minimale abhängige Menge – wegen der Bedeutung für Graphen – ein Kreis (circuit) von \(M\). Neben dem System \((R')\) stellt Verf. drei andere Systeme von Postulaten auf, in denen die unabhängigen Mengen bzw. die Basen bzw. die Kreise von \(M\) als Grundbegriffe auftreten; alle drei Systeme sind mit \((R)\) und miteinander gleichwertig. – Deutet man die \(e\) z. B. als Spalten einer Matrix, so erhält man natürlich die üblichen Begriffsbildungen. Verf. gibt jedoch ein aus 7 Elementen bestehendes Matroid (definiert durch Angabe der Basen) an, das sich nicht als Matrix deuten läßt. – Ist \(M = e_1 + \cdots + e_r + e_{r+1} + \cdots + e_p\) (das Zeichen \(+\) bedeutet hier wie schon früher nur die Bildung der Vereinigungsmenge) und dabei \(r = r(M)\) und \(e_1 + \cdots + e_r\) eine Basis von \(M\), so bilden die Kreise \(P_1\), …, \(P_{p-r}\) ein Fundamentalsystem in bezug auf \(e_{r+1}\), …, \(e_p\), wenn \(P_i\) das Element \(e_{r+i}\), aber kein Element mit größerem Index enthält, insbesondere ein eigentliches Fundamentalsystem, wenn \(P_i\) kein \(e_{r+j}\), \(j = i\), \(j > 0\), enthält. Durch Angabe eines (eigentlichen) Fundamentalsystems von Kreisen ist ein Matroid im allgemeinen noch nicht bestimmt.
In Analogie zu nicht-separablen Graphen und dualen Graphen definiert Verf: Ein Matroid heißt nicht-separabel, wenn es keine Zerspaltung \(M = M_1 + M_2\) mit \(r(M) = r(M_1) + r(M_2)\) gibt. Ist das Matroid \(M\) eineindeutig auf ein anderes Matroid \(M'\) abgebildet, so daß dabei, wenn \(N' \subset M'\) die Komplementärmenge des Bildes der Menge \(N\) von \(M\) bezeichnet, stets \(r(N') = r(M') - n(M)\) gilt, so heißt \(M'\) zu \(M\) dual; dann ist auch \(M\) zu \(M'\) dual, und es gilt \(r(M) = n(M')\), \(r(M') = n(M)\). – Die Ergebnisse über nicht-separable Matroide und die nicht-separablen Bestandteile eines Matroids entsprechen denen über Graphen (Verf., a. a. O.). Bezüglich der dualen Matroide ist hervorzuheben, daß man zu jedem Matroid \(M\) ein duales \(M'\) abstrakt konstruieren kann, während im Falle der Graphen die Existenz des dualen gleichbedeutend ist mit der Möglichkeit der Realisation als Streckenkomplex in der Ebene. Ist insbesondere \(M\) eine Matrix (deren Spalten die Elemente von \(M\) bilden), so kann man ihren Kreisen in naheliegender Weise die Zeilen einer Matrix \(M'\), der Kreismatrix, zuordnen, und \(M'\) ist, wenn man jetzt wieder die Spalten als Elemente des Matroids auffaßt, zu \(M\) dual. Das wird hier mit Hilfe einer geometrischen Deutung bewiesen, die sich aber wohl vermeiden ließe.
Ein Kriterium dafür, wann ein Matroid als Matrix aufgefaßt werden kann (deren Elemente einem Körper angehören sollen), kann Verf. nicht angeben. Für den Fall der Matrizen mit ganzzahligen Elementen mod 2 ist folgende Bedingung notwendig und hinreichend: Man schreibe die Kreise des Matroids \(M\) formal als lineare Verbindungen \(\alpha_1e_1+ \cdots + \alpha_pe_p\), \(\alpha_i = 0\) oder 1, und nenne alle daraus entstehenden linearen Verbindungen (mod 2 gerechnet) Zyklen von \(M\); dann muß sich jeder Zyklus von \(M\) als Summe von paarweise elementenfremden Kreisen darstellen lassen. Ist diese Bedingung erfüllt, so ist das Matroid schon durch Angabe eines Fundamentalsystems von Kreisen bestimmt. Daß auch die Klasse dieser Matroide größer ist als die der Graphen, zeigt wieder das schon oben erwähnte Matroid mit 7 Elementen (das übrigens auch als Beispiel einer endlichen projektiven Geometrie bekannt ist). (V 2.)

Reviewer: Pannwitz, Erika, Dr. (Berlin)

MSC:

15A03	Vector spaces, linear dependence, rank, lineability
05B35	Combinatorial aspects of matroids and geometric lattices

JFM Section:

Erster Halbband. Dritter Abschnitt. Arithmetik und Algebra. Kapitel 2. Kombinatorik. Determinanten und Matrizen.

Citations:

JFM 58.0608.01; Zbl 0004.13103