Relation-Matrix-Korrespondenz



  • Hallo

    Ich habe vor Kurzem mein Studium begonnen und hatte heute eine Vorlesung, in der Relationen eingeführt wurden. Wir haben Relationen sowohl mengentheoretisch, graphentheoretisch als auch vom Blickpunkt der linearen Algebra betrachtet und gewisse Konzepte in allen drei Interpretationen besprochen.
    Sei ρA×A\rho \subseteq A \times A eine Relation, dann gibt es eine Matrix MF2A×A\mathbf{M}\in\mathbb{F}_2^{\left |A \right |\times \left |A \right |}, sodass

    mij={1wenn(a_i,a_j)ρ0sonstm_{ij}=\left\{\begin{matrix} 1 & wenn \; (a\_i,a\_j)\in\rho\\ 0 & sonst \end{matrix}\right.

    , wobei mijm_{ij} die Einträge der Matrix sind. (Wenn mich nicht alles täuscht, dann müsste M\mathbf{M} stets die Adjazenzmatrix des Graphen der Relation sein?)
    Ist die Relation ρ\rho symmetrisch, sprich a,b:aρb↔bρa\forall a,b: a \rho b \leftrightarrow b \rho a, dann gilt ρ=ρ^\rho=\hat{\rho} (wir definierten ρ^:={(a_2,a_1)(a_1,a_2)ρ}\hat{\rho}:=\left \{ (a\_2,a\_1) \mid (a\_1,a\_2) \in \rho \right \}). Ferner gilt dann, dass M\mathbf{M} eine Diagonalmatrix ist. Außerdem enthält der dazugehörige gerichtete Graph auch die Invertierte jeder seiner Kanten.
    Wir haben mehrere dieser Eigenschaften in allen drei Interpretationen besprochen, außer der Transitivität:
    Ist die Relation ρ\rho transitiv, sprich a,b,c:aρbbρcaρc\forall a,b,c: a \rho b \wedge b \rho c \rightarrow a \rho c, so gilt ρρρ\rho \circ \rho \subseteq \rho (wir definierten ρϕ:={(a,c)b:aρbbϕc}\rho \circ \phi :=\left \{ (a,c) \mid \exists b: a\rho b \wedge b\phi c \right \}). Für den Graphen heißt das, dass es stets "Abkürzungen" gibt.
    Meine Frage: Wie lässt sich die Transitivität von ρ\rho mittels M\mathbf{M} ausdrücken? Gehe ich recht in der Annahme, dass die Verkettung von Relationen mit der Matrixmultiplikation korrespondiert?
    Noch spannender: Wie kann man den transitiven Abschluss für M\mathbf{M} erklären?

    LG

    PS: Wie kann ich die Definition von mijm_{ij} schöner formatieren in Latex?



  • Hi.

    Also die Adjadenzmatrix sollte für symmetrische Relationen auch symmetrisch und i.A. nicht diagonal sein. Das ist eigentlich recht anschaulich klar, da dann Spalte- und Zeilenindex in der Matrix vertauschbar sein müssen.

    Bzgl. der Transitivität:
    https://math.stackexchange.com/questions/228898/how-to-check-whether-a-relation-is-transitive-from-the-matrix-representation



  • Ups ja, eine symmetrische Matrxi, nicht Diagonalmatrix. Mein Fehler.

    Danke für den Link, hab's verstanden.


Log in to reply