Zyklische Untermenge (Matrix)

Beschreibung

Die Zyklischen Untermengen sind nützliche Werkzeuge, um eine Irreduzible Matrix in mehrere aperiodische Matrizen zu zerlegen. Wir finden dabei effektiv alle Knoten, die durch von einem Knoten $i$ in $p$ Schritten erreichbar sind, wobei $p$ die Periode ist. Diese Knoten bilden dann einen neuen Graphen, welcher aperiodisch ist.

Definition

Sei $A$ eine reelle, nicht-negative, quadratische, Irreduzible Matrix mit Periode (Matrix) $p$. Fixiere einen Index $i$ und definiere die Zyklischen Untermengen $C_0,...,C_{p-1}$: $C_k=\{j:(A^{np+k}{)}_{ij}>0\text{ fu¨r ein }n\in \mathbb{N}\}$

Charakterisierung durch Graph

Sei $A$ eine irreduzible $\{0,1\}$ Adjazenzmatrix mit Periode (Matrix) $p$ eines Graphen $G_A$. Seien $C_1,...,C_{p-1}$ die zyklischen Untermengen der Indizes. Dann können wir die zyklischen Untermengen auch als Schritte von zyklischen Pfaden in $G_A$ beginnend bei $i$ interpretieren. D.h. nach einem Knoten aus $C_k$ folgt immer ein Knoten aus $C_{k+1}$. (mod $p$). Das $k$ gibt hierbei immer die Entfernung mod $p$ vom Knoten $i$ an.

Eigenschaften

Nicht zusammenhängende Graphen

Hängt ein Graph nicht zusammen, lässt sich nicht jeder Knoten von $i$ aus erreichen. In dem Fall ist es egal, wie oft man $A$ potenziert $(A^n{)}_{ij}$ wird nie $>0$, wenn $j$ in einer anderen Zusammenhangskomponente liegt. Die Periode des Graphen kann immer noch wohldefiniert sein. (Die zwei verschiedenen Zusammenhangskomponenten können sogar verschiedene Perioden haben.) Die $C_k$ sind ebenfalls wohldefiniert, bilden diesmal aber keine Zerlegung aller Knoten. Dieser Fall tritt aber nie ein, weil wir üblicherweise nur irreduzible Matrizen betrachten.

tchensSymbolicDynamicsOnesided2012]]