Benutzer:Martin von Gagern/Orientiertes Matroid

Ein Orientiertes Matroid ist ein Matroid, dass neben Information zur linearen Abhängigkeit oder Inzidenz von Objekten auch noch zusätzlich Information zur relativen Lage unabhängiger Objekte trägt.

Motivation

Man kann orientierte Matroide als kombinatorische Essenz einer Matrix auffassen. Es sei $A\in \mathbb {R} ^{n\times r}$ eine relle Matrix, mit $n>r$. Dann kann man daraus ein orientiertes Matroid ablesen, wie im Folgenden dargestellt wird. Dabei bezeichnet $n$ die Anzahl der Elemente, $r$ hingegen den Rang des orientierten Matroids. Umgekehrt gibt es nicht zu jedem orientierten Matroid auch eine Matrix, aus der sich dieses ergibt. Orientierte Matroide, die sich aus einer Matrix ergeben können, heißen realisierbar. Eine passende Matrix nennt man dann eine Realisierung.

Vektoren

Der Spann $\operatorname {span} (A)\subset \mathbb {R} ^{n}$ der Spalten einer Matrix lässt sich auch interpretieren als Menge aller Skalarprodukte der Zeilen $v_{i}$ dieser Matrix mit einem frei wählbaren Vektor $h$:

$\operatorname {span} (A)=\{(<v_{1},h>,<v_{2},h>,\dots ,<v_{n},h>);|\;h\in \mathbb {R} ^{r}\}\in \mathbb {R} ^{n}$(1)

Wenn man für ein Element dieser Menge lediglich die Vorzeichen notiert, erhält man eine Folge von $n$ Vorzeichen aus $\{0,+,-\}$. In der Sprache der orientierten Matroide nennt man diese Vorzeichenfolge einen Vektor des Matroids. Die Vektoren des orientierten Matroids beschreiben also die möglichen Vorzeichenmuster, die sich durch Skalarprodukte mit einem beliebigen Vektor des $\mathbb {R} ^{r}$ ergeben.

Kovektoren

Man kann die linearen Abhängigkeiten zwischen den Zeilen der Matrix beschreiben als $\operatorname {ker} (A^{T})\subset \mathbb {R} ^{n}\;$, den Kern der transponierten Matrix. Wenn man für alle Elemente von $\operatorname {ker} (A^{T})$ lediglich das Vorzeichen notiert, so erhält man das, was in einem orientierten Matroid als Kovektor bezeichnet wird. Kovektoren beschreiben also die Vorzeichenmuster, die sich bei Linearkombinationen des Nullvektors aus den Zeilen der Matrix ergeben.

Circuits und Cocircuits

Die Menge aller Vektoren enthält Elemente, die maximal viele Nullen enthalten. Ein Vektor $C$ hat maximal viele Nullen genau dann, wenn es in der Menge der Vektoren keinen weiteren Vektor $D$ gibt, der mehr Nullen hat, aber in allen von Null verschiedenen Einträgen mit $C$ übereinstimmt. Ein Vektor mit maximal vielen Nullen wird Cocircuit (Kokreis) genannt. Analog wird ein Kovektor mit maximal vielen Nullen als Circuit (Kreis) bezeichnet. Die gegensätzliche Verteilung des Präfixes „Co-“ ist historisch begründet. Die Wortwahl „Kreis“ leitet sich aus dem Zusammenhang mit gerichteten Graphen ab, der weiter unten noch beschrieben wird.

Chirotop

Ein Chirotop sind die Vorzeichen aller Fehler beim Parsen (MathML mit SVG- oder PNG-Rückgriff (empfohlen für moderne Browser und Barrierefreiheitswerkzeuge): Ungültige Antwort („Math extension cannot connect to Restbase.“) von Server „https://wikimedia.org/api/rest_v1/“:): {\displaystyle r\times r} -Unterdeterminanten, die sich durch Auswahl von Fehler beim Parsen (MathML mit SVG- oder PNG-Rückgriff (empfohlen für moderne Browser und Barrierefreiheitswerkzeuge): Ungültige Antwort („Math extension cannot connect to Restbase.“) von Server „https://wikimedia.org/api/rest_v1/“:): {\displaystyle r} der Fehler beim Parsen (MathML mit SVG- oder PNG-Rückgriff (empfohlen für moderne Browser und Barrierefreiheitswerkzeuge): Ungültige Antwort („Math extension cannot connect to Restbase.“) von Server „https://wikimedia.org/api/rest_v1/“:): {\displaystyle n} Zeilen der Matrix errechnen lassen. Ein Chirotop ist nicht direkt ein orientiertes Matroid: abhängig vom Rang kann es zu einem einzigen orientierten Matroid zwei Chirotope geben. Dennoch hängen die Konzepte stark genug zusammen, um sie hier gesammelt zu diskutieren.

Begriffe und Definitionen

• Ein orientiertes Matroid ist eine Struktur, die eine Menge von Elementen beschreibt. Die Menge aller Elemente wird mit Fehler beim Parsen (MathML mit SVG- oder PNG-Rückgriff (empfohlen für moderne Browser und Barrierefreiheitswerkzeuge): Ungültige Antwort („Math extension cannot connect to Restbase.“) von Server „https://wikimedia.org/api/rest_v1/“:): {\displaystyle E} bezeichnet.
• Ein Vektor ist eine Abbildung, die jedem Element ein Vorzeichen zuordnet.

  Fehler beim Parsen (MathML mit SVG- oder PNG-Rückgriff (empfohlen für moderne Browser und Barrierefreiheitswerkzeuge): Ungültige Antwort („Math extension cannot connect to Restbase.“) von Server „https://wikimedia.org/api/rest_v1/“:): {\displaystyle V: E\to\{-,0,+\}}

• Ein Kovektor, ein Circuit und ein Cocircuit sind ebenfalls Abbildungen dieser Gestalt.
• Es sei Fehler beim Parsen (MathML mit SVG- oder PNG-Rückgriff (empfohlen für moderne Browser und Barrierefreiheitswerkzeuge): Ungültige Antwort („Math extension cannot connect to Restbase.“) von Server „https://wikimedia.org/api/rest_v1/“:): {\displaystyle V} ein Vektor, Kovektor, Circuit oder Cocircuit. Dann bezeichnet Fehler beim Parsen (MathML mit SVG- oder PNG-Rückgriff (empfohlen für moderne Browser und Barrierefreiheitswerkzeuge): Ungültige Antwort („Math extension cannot connect to Restbase.“) von Server „https://wikimedia.org/api/rest_v1/“:): {\displaystyle V^+\subseteq E} die Menge aller Elemente, deren Eintrag positiv ist, und Fehler beim Parsen (MathML mit SVG- oder PNG-Rückgriff (empfohlen für moderne Browser und Barrierefreiheitswerkzeuge): Ungültige Antwort („Math extension cannot connect to Restbase.“) von Server „https://wikimedia.org/api/rest_v1/“:): {\displaystyle V^0,V^-} analog.

  Fehler beim Parsen (MathML mit SVG- oder PNG-Rückgriff (empfohlen für moderne Browser und Barrierefreiheitswerkzeuge): Ungültige Antwort („Math extension cannot connect to Restbase.“) von Server „https://wikimedia.org/api/rest_v1/“:): {\displaystyle \begin{align}V^+&:=\{e\in E\;|\;V(e)=+\}\\V^0&:=\{e\in E\;|\;V(e)=0\}\\V^-&:=\{e\in E\;|\;V(e)=-\}\end{align}}

• Ein orientiertes Matroid kann vollständig beschrieben werden entweder durch die Menge all seiner Vektoren, oder die Menge all seiner Kovektoren, oder die Menge all seiner Circuits oder die Menge all seiner Cocircuits. Diese Beschreibungen sind Äquivalent.
• Ein Chirotop ordnet jedem Fehler beim Parsen (MathML mit SVG- oder PNG-Rückgriff (empfohlen für moderne Browser und Barrierefreiheitswerkzeuge): Ungültige Antwort („Math extension cannot connect to Restbase.“) von Server „https://wikimedia.org/api/rest_v1/“:): {\displaystyle r} -Tupel von Elementen ein Vorzeichen zu:

  Fehler beim Parsen (MathML mit SVG- oder PNG-Rückgriff (empfohlen für moderne Browser und Barrierefreiheitswerkzeuge): Ungültige Antwort („Math extension cannot connect to Restbase.“) von Server „https://wikimedia.org/api/rest_v1/“:): {\displaystyle \Chi:E^r\to\{-,0,+\}}

• Ein orientiertes Matroid kann auch vollständig beschrieben werden durch ein Chirotop, umgekehrt ist jedoch das Chirotop durch ein orientiertes Matroid noch nicht zwingend eindeutig beschrieben.

Modelle

Es gibt verschiedene Strukturen, aus denen sich orientierte Matroide ableiten lassen. Dabei erfahren die Begriffe des orientierten Matroids jeweils unterschiedliche Interpretationen.

Vektorkonfigurationen

Man kann wie eingangs beschrieben ein orientiertes Matroid aus einer Matrix mit reellen Einträgen erhalten. Dabei stellt jede Zeile der Matrix ein Element dar, nämlich einen Vektor in Fehler beim Parsen (MathML mit SVG- oder PNG-Rückgriff (empfohlen für moderne Browser und Barrierefreiheitswerkzeuge): Ungültige Antwort („Math extension cannot connect to Restbase.“) von Server „https://wikimedia.org/api/rest_v1/“:): {\displaystyle \mathbb R^r} . Jedes realisierbare orientierte Matroid entspricht einer nicht leeren Äquivalenzklasse von Vektorkonfigurationen.

Der bei der Definition von Vektoren (im Sinne orientierter Matroide) in Gleichung (1) verwendete Vektor Fehler beim Parsen (MathML mit SVG- oder PNG-Rückgriff (empfohlen für moderne Browser und Barrierefreiheitswerkzeuge): Ungültige Antwort („Math extension cannot connect to Restbase.“) von Server „https://wikimedia.org/api/rest_v1/“:): {\displaystyle h\in\mathbb R^r} kann als Normalenvektor einer (orientierten) Hyperebene aufgefasst werden. Durch diese wird der Fehler beim Parsen (MathML mit SVG- oder PNG-Rückgriff (empfohlen für moderne Browser und Barrierefreiheitswerkzeuge): Ungültige Antwort („Math extension cannot connect to Restbase.“) von Server „https://wikimedia.org/api/rest_v1/“:): {\displaystyle \mathbb R^r} zerlegt in einen positiven und einen negativen offenen Halbraum zerlegt sowie die Hyperebene selbst, die dem Vorzeichen 0 entspricht. Einem Element des orientierten Matroids wird also ein Vorzeichen zugeordnet je nachdem, in welchem dieser drei Bereiche er sich befindet. Das ist genau das Vorzeichen, dass sich aus dem Skalarprodukt mit dem Normalenvektor ergibt. Die Menge aller Vektoren des orientierten Matroids erhält man, indem man alle möglichen Normalenvektoren Fehler beim Parsen (MathML mit SVG- oder PNG-Rückgriff (empfohlen für moderne Browser und Barrierefreiheitswerkzeuge): Ungültige Antwort („Math extension cannot connect to Restbase.“) von Server „https://wikimedia.org/api/rest_v1/“:): {\displaystyle h} betrachtet.

Die Cocircuits sind diejenigen Vektoren des orientierten Matroids mit maximaler Anzahl von Nullen, also mit maximaler Anzahl von Elementen des Matroids, die mit der Hyperebene selbst inzident sind. Das ist genau dann der Fall, wenn die durch Fehler beim Parsen (MathML mit SVG- oder PNG-Rückgriff (empfohlen für moderne Browser und Barrierefreiheitswerkzeuge): Ungültige Antwort („Math extension cannot connect to Restbase.“) von Server „https://wikimedia.org/api/rest_v1/“:): {\displaystyle h} definierte Hyperebene eine Basis hat, die lediglich aus Elementen des orientierten Matroids besteht.

Punktkonfigurationen

Man kann die Vektoren einer Vektorkonfiguration auch als homogene Koordinaten modulo positiver skalarer Vielfacher betrachten. Dadurch reduziert sich die Dimension auf Fehler beim Parsen (MathML mit SVG- oder PNG-Rückgriff (empfohlen für moderne Browser und Barrierefreiheitswerkzeuge): Ungültige Antwort („Math extension cannot connect to Restbase.“) von Server „https://wikimedia.org/api/rest_v1/“:): {\displaystyle d=r-1} . Dann lässt sich jedes Element als einen Punkt auf der Sphäre Fehler beim Parsen (MathML mit SVG- oder PNG-Rückgriff (empfohlen für moderne Browser und Barrierefreiheitswerkzeuge): Ungültige Antwort („Math extension cannot connect to Restbase.“) von Server „https://wikimedia.org/api/rest_v1/“:): {\displaystyle S^d} auffassen.

Alternativ kann man die Elemente auch als Punkte in dem reellen projektiven Raum Fehler beim Parsen (MathML mit SVG- oder PNG-Rückgriff (empfohlen für moderne Browser und Barrierefreiheitswerkzeuge): Ungültige Antwort („Math extension cannot connect to Restbase.“) von Server „https://wikimedia.org/api/rest_v1/“:): {\displaystyle \mathbb R\mathrm P^d} interpretieren, und dann in die Ebene Fehler beim Parsen (MathML mit SVG- oder PNG-Rückgriff (empfohlen für moderne Browser und Barrierefreiheitswerkzeuge): Ungültige Antwort („Math extension cannot connect to Restbase.“) von Server „https://wikimedia.org/api/rest_v1/“:): {\displaystyle \mathbb R^d} einzeichnen. Dabei sind jedoch Fernpunkte zu vermeiden (etwa durch geeignete Koordinatenwahl), und außerdem wird jeder Punkt mit einem Vorzeichen annotiert, das bei Berechnungen miteinbezogen werden muss. Die eine Hälfte der Sphäre wird so zu positiven Punkten, die andere Hälfte zu negativen, und die Grenzlinie dazwischen entspricht der Ferngeraden, auf der keine Elemente des orientierten Matroids liegen dürfen.

Die Vektoren des orientierten Matroids entsprechen bei der Interpretation als Punktkonfiguration der Lage dieser Punkte relativ zu einem Hypergroßkreis (im Falle Fehler beim Parsen (MathML mit SVG- oder PNG-Rückgriff (empfohlen für moderne Browser und Barrierefreiheitswerkzeuge): Ungültige Antwort („Math extension cannot connect to Restbase.“) von Server „https://wikimedia.org/api/rest_v1/“:): {\displaystyle S^d} ) oder einer Hyperebene (im Falle Fehler beim Parsen (MathML mit SVG- oder PNG-Rückgriff (empfohlen für moderne Browser und Barrierefreiheitswerkzeuge): Ungültige Antwort („Math extension cannot connect to Restbase.“) von Server „https://wikimedia.org/api/rest_v1/“:): {\displaystyle \mathbb R\mathrm P^d} ), wobei in letzterem Bild das Vorzeichen des Punktes mit dem durch die Lage bestimmten Vorzeichen multipliziert werden muss.

Die Cocircuits sind entsprechend diejenigen Vektoren des orientierten Matroids, die sich aus Hypergroßkreisen bzw. Hyperebenen ergeben, die von maximal vielen Punkten der Punktkonfiguration aufgespannt werden, also eine affine Basis aus solchen Punkten besitzen.

Hyperebenenarrangements

Durch projektive Dualität kann man die Rollen von Punkten und Hyperebenen vertauschen. Man erhält eine Interpretation, in der die Elemente des orientierten Matroids orientierten Hyperebenen des Fehler beim Parsen (MathML mit SVG- oder PNG-Rückgriff (empfohlen für moderne Browser und Barrierefreiheitswerkzeuge): Ungültige Antwort („Math extension cannot connect to Restbase.“) von Server „https://wikimedia.org/api/rest_v1/“:): {\displaystyle \mathbb R^d=\mathbb R^{r-1}} entsprechen.

Jeder vorzeichenbehaftete Punkt dieses Raumes führt zu einem Vorzeichenmuster, das ein Vektor des orientierten Matroids ist. Jeder vorzeichenbehaftete Punkt, der Schnittpunkt von maximal vielen Elementen ist, führt zu einem Vorzeichenmuster, der ein Cocircuit des orientierten Matroids ist.

Pseudohyperebenenarrangements

Man kann die Forderung, dass die Hyperebenen im eben beschrieben Modell tatsächlich flach sind, aufweichen und statt dessen lediglich fordern, dass die Kombinatorik gewissen Bedingungen genügt. Dadurch erhält man ein Modell, das in der Lage ist, jedes orientierte Matroid darzustellen, auch die nicht realisierbaren. Die Objekte, mit denen man es hier zu tun hat, werden dann Pseudohyperebenen genannt. Im Falle von Fehler beim Parsen (MathML mit SVG- oder PNG-Rückgriff (empfohlen für moderne Browser und Barrierefreiheitswerkzeuge): Ungültige Antwort („Math extension cannot connect to Restbase.“) von Server „https://wikimedia.org/api/rest_v1/“:): {\displaystyle r=3} und somit Fehler beim Parsen (MathML mit SVG- oder PNG-Rückgriff (empfohlen für moderne Browser und Barrierefreiheitswerkzeuge): Ungültige Antwort („Math extension cannot connect to Restbase.“) von Server „https://wikimedia.org/api/rest_v1/“:): {\displaystyle d=2} , also der Darstellung in der Ebene, spricht man konsequent von Pseudogeraden und Pseudogeradenarrangements.

Graphen

Gerichtete Graphen können ebenfalls zur Definition eines orientierten Matroids dienen. Nicht jedes orientierte Matroid lässt sich aus einem Graphen ableiten. Solche, bei denen dies möglich ist, werden als graphisch bezeichnet. Dabei ist die Eigenschaft, graphisch zu sein, unabhängig von der Eigenschaft, realisierbar zu sein.

Jeder mögliche Kreis im zugruneliegenden ungerichteten Graphen entspricht einem Circuit des orientierten Matroids. Dabei sind einfache Kreise solche, die keinen Knoten doppelt enthalten. Der Kreis wird orientiert betrachtet, so dass er jede Kante des Graphen entweder in oder gegen ihre Richtung traversiert. Dies wird durch das Vorzeichen im zugehörigen Circuit des orientierten Matroids wiedergegeben. Kanten, die nicht im Kreis enthallten sind, werden mit 0 notiert.

Cocircuits hingegen entsprechen minimalen Schnitten. Jede mögliche Zerlegung des Graphen in zwei Zusammenhangskomponenten (oder genauer gesagt in eine Zusammenhangskomponente mehr als der ursprüngliche Graph ungerichtet hatte) entspricht einem Cocircuit. Die Kanten innerhalb der Teile werden mit 0 beschrieben, die zwischen den Teilen mit einem Vorzeichen entsprechend der Richtung, in der sie verlaufen. Dabei gibt es zwei Möglichkeiten, welche Richtung als positiv betrachtet wird, was zwei verschiedenen und zueinander inversen Cocircuits entspricht.

Axiomensysteme

Es gibt viele verschiedene Arten, wie orientierte Matroide durch Axiome charakterisiert werden können. Die einzelnen Systeme sind dabei äquivalent, so dass sich eines aus dem anderen ableiten lässt.

Kreisaxiome

1. Es gibt keinen leeren Kreis: Fehler beim Parsen (MathML mit SVG- oder PNG-Rückgriff (empfohlen für moderne Browser und Barrierefreiheitswerkzeuge): Ungültige Antwort („Math extension cannot connect to Restbase.“) von Server „https://wikimedia.org/api/rest_v1/“:): {\displaystyle \forall X\in C\;\exists e\in E: X_e\neq 0}
2. Wenn Fehler beim Parsen (MathML mit SVG- oder PNG-Rückgriff (empfohlen für moderne Browser und Barrierefreiheitswerkzeuge): Ungültige Antwort („Math extension cannot connect to Restbase.“) von Server „https://wikimedia.org/api/rest_v1/“:): {\displaystyle X} ein Kreis ist, dann ist auch Fehler beim Parsen (MathML mit SVG- oder PNG-Rückgriff (empfohlen für moderne Browser und Barrierefreiheitswerkzeuge): Ungültige Antwort („Math extension cannot connect to Restbase.“) von Server „https://wikimedia.org/api/rest_v1/“:): {\displaystyle -X} ein Kreis: Fehler beim Parsen (MathML mit SVG- oder PNG-Rückgriff (empfohlen für moderne Browser und Barrierefreiheitswerkzeuge): Ungültige Antwort („Math extension cannot connect to Restbase.“) von Server „https://wikimedia.org/api/rest_v1/“:): {\displaystyle \forall X\in C\;\exists -X\in C\;\forall e\in E:X_e = -(-X)_e}
3. Kein Kreis ist ungerichtet eine echte Teilmenge eines anderen: Fehler beim Parsen (MathML mit SVG- oder PNG-Rückgriff (empfohlen für moderne Browser und Barrierefreiheitswerkzeuge): Ungültige Antwort („Math extension cannot connect to Restbase.“) von Server „https://wikimedia.org/api/rest_v1/“:): {\displaystyle \not\exists X,Y\in C:\{e\vert X_e\neq 0\}\subsetneqq\{e\vert Y_e\neq 0\}}
4. Hier fehlt noch eines.

Anwendungen

Orientierte Matroide treten in vielen Formen in unterschiedlichsten wissenschaftlichen Disziplinen auf.

Literatur

• Anders Björner, Michael Las Vergnas, Bernd Sturmfels, Neil White, Günter M. Ziegler: Oriented Matroids. 1. Auflage. Cambridge University Press, 1993, ISBN 0-521-41836-4. 
• Jürgen Richter-Gebert and Günter M. Ziegler: Oriented Matroids. (tum.de [PDF]). 

Einzelnachweise

Kategorie:Algebraische Geometrie