Relation-Matrix-Korrespondenz

[Fytch]

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 $\rho \subseteq A \times A$ eine Relation, dann gibt es eine Matrix $\mathbf{M}\in\mathbb{F}_2^{\left |A \right |\times \left |A \right |}$, sodass

$m_{ij}=\left\{\begin{matrix} 1 & wenn \; (a\_i,a\_j)\in\rho\\ 0 & sonst \end{matrix}\right.$

, wobei $m_{ij}$ die Einträge der Matrix sind. (Wenn mich nicht alles täuscht, dann müsste $\mathbf{M}$ stets die Adjazenzmatrix des Graphen der Relation sein?)
Ist die Relation $\rho$ symmetrisch, sprich $\forall a,b: a \rho b \leftrightarrow b \rho a$, dann gilt $\rho=\hat{\rho}$ (wir definierten $\hat{\rho}:=\left \{ (a\_2,a\_1) \mid (a\_1,a\_2) \in \rho \right \}$). Ferner gilt dann, dass $\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 $\forall a,b,c: a \rho b \wedge b \rho c \rightarrow a \rho c$, so gilt $\rho \circ \rho \subseteq \rho$ (wir definierten $\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 $\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 $\mathbf{M}$ erklären?

LG

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

[Jodocus]

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

[Fytch]

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

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