transitiver Abschluss < Relationen < Diskrete Mathematik < Hochschule < Mathe < Vorhilfe
|
| Status: |
(Frage) überfällig  | | Datum: | 10:55 Sa 01.09.2007 | | Autor: | setine |
Hallo Zusammen,
Wenn man eine Äquivalenz-Relation in der Matrixform(BxB) vor sich liegen hat, dann ist mir aufgefallen dass diese immer positive definite Matzizen zu sein scheinen...
Oder der transitiver Abschluss einer Relation scheint immer mind. pos. semidefinit zu sein (falls reflexiv, dann pos def)
Stimmt denn dieser Zusammenhang (oder besser, in welche Richtung gilt sie als Implikation)? Wie kann man das Begründen, evtl mit der Eigenwertzerlegung?
Danke, Setine
|
|
| |
|
| Status: |
(Mitteilung) Reaktion unnötig  | | Datum: | 15:18 Sa 01.09.2007 | | Autor: | setine |
> Wenn man eine Äquivalenz-Relation in der Matrixform(BxB)
> vor sich liegen hat, dann ist mir aufgefallen dass diese
> immer positive definite Matzizen zu sein scheinen...
Ich habe eine Äquivalenzrelation gefunden die pos semidefinit ist:
[mm] $\pmat{ 1 & 0 & 1\\ 0 & 1 & 0\\ 1 & 0 & 1}$
[/mm]
Eigenwerte sind 2,0,1 also wegen dem EW 0 pos semidefinit.
Gleichzeitig ist die Relation symmetrisch, transitiv und reflexiv.
Edit:
Meine Vermutung in destillierter Form:
Wenn A positiv semidefinit <-> Relation definiert durch A ist transitiv
|
|
|
| |
|
| Status: |
(Mitteilung) Reaktion unnötig | | Datum: | 20:50 Mo 03.09.2007 | | Autor: | nick_twisp |
Hallo sentine,
ich würde dir gern weiterhelfen. Leider versteh ich nicht ganz, was du mit Äquivalenzrelation in Matrixform meinst.
Anscheinend sagst du, durch eine Matrix ist eine Äquivalenzrelation gegeben.
Aber wie genau?
Mfg, nick
|
|
|
| |
|
| Status: |
(Mitteilung) Reaktion unnötig | | Datum: | 18:25 Di 04.09.2007 | | Autor: | setine |
Hi Nick!
Schön dass sich jemand zu wort meldet ;)
Wenn ich mir eine Relation vorstelle, dann entweder als Graphen oder als eine als Matrix, wobei diese Matrix dann eigentlich nichts anderes ist als die Adjazenzmatrix des Graphen.
Also zB eine Relation auf der Menge {a,b,c}:
Knoten sind dann a, b und c
Kanten sind zB (a,c), (b,a)
In diesem Fall sähe die Matrix so aus:
a b c
-------
a¦0 0 1
b¦1 0 0
c¦0 0 0
Gruss, Setine
|
|
|
| |
|
| Status: |
(Mitteilung) Reaktion unnötig | | Datum: | 00:17 Mi 05.09.2007 | | Autor: | nick_twisp |
Jetzt versteh ich erst, das es um die Darstellungsmatrizen von ungerichteteten Graphen ohne Mehrfachkanten geht und um die Relation des "benachbart sein" von zwei Knoten in einem Graphen. Damit diese Relation reflexiv ist, darf der Graph nicht schleifenlos sein, d.h. auf der Diagonalen der Adjazenzmatrix sind Einsen. Für Symmetrie muss die Matrix symmetrisch sein.
Aber irgendwie ist die Darstellungsmatrix
[mm] $\pmat{ 1 & 0 & 1\\ 0 & 1 & 0\\ 1 & 0 & 1 }$
[/mm]
nicht die Adjazenzmatrix eines Graphen, oder müssen bei einem Graphen nicht immer alle Knoten mit Kanten verbunden sein?
Aber damit ist ja schon automatisch klar, dass wenn die Relation "benachbart sein" eine Äquivalenzrelation sein soll, es für jeden Graphen nur eine Äquivalenzklasse gibt, da jeder Knoten mit jedem anderen über eine Kante verbunden ist. Gäbe es mehr als eine Äquivalenzklasse müsste der Graph in zwei getrennte Gebilde zerfallen, wäre dann aber automatisch kein Graph mehr. d.h. jede Adjazenzmatrix von einem ungerichteten Graphen ohne Mehrfachkanten bei dem "benachbart sein" von zwei Knoten einer Äquivalenzrelation entspricht, ist eine Matrix, wo jeder Eintrag eine Eins ist. Denke ich zumindest.. sag mir wo ich mich irre. Ob das jetzt positiv semidefinite Matrizen sind, weiss ich nicht.
Grüße, Nick
|
|
|
| |
|
| Status: |
(Mitteilung) Reaktion unnötig | | Datum: | 14:57 Mi 05.09.2007 | | Autor: | setine |
> Damit diese Relation reflexiv ist, darf der Graph
> nicht schleifenlos sein, d.h. auf der Diagonalen der
> Adjazenzmatrix sind Einsen. Für Symmetrie muss die Matrix
> symmetrisch sein.
Genau ja, also haben wir zwei einfache kriterien um die Symmetrie und die Reflexivität einer Relation zu bestimmen. Doch leider gibts bei der Transitivität kein so einfaches Kriterium (imho natürlich ;)
> Aber irgendwie ist die Darstellungsmatrix
> [mm]\pmat{ 1 & 0 & 1\\ 0 & 1 & 0\\ 1 & 0 & 1 }[/mm]
> nicht die
> Adjazenzmatrix eines Graphen, oder müssen bei einem Graphen
> nicht immer alle Knoten mit Kanten verbunden sein?
Ich denke nicht, nein. Man kann durchaus von einem Graphen mit "freien" Knoten sprechen. Dieser entspricht dann aber keiner Äquivalenzrelation, wie du schon bemerkt hast.
Ich will mich aber gar nicht nur auf Äquivalenzrelationen beschränken. Es gibt also auch Relationen welche weder symmetrisch, reflexiv noch transitiv sind (imho wieder ;). Ich spreche also von der Menge aller möglichen Graphen, oder auch der Menge aller möglichen Adjazenmatrizen welche aus Nullen und Einsen bestehen.
Also zusammenfassend:
Ich denke eine Relation (also irgendeine, nicht nur Äquivalenzrel) kann man ihre Transivität ansehen, wenn man ihre Adjazenzmatrix als "normale" Matrix auf den ganzen Zahlen interpretiert. Ist diese Matrix positiv semidefinit (alle Eigenwerte >=0), so wird die Relation transitiv sein. So lautet jedenfalls meine Behauptung ;)
Gruss, Setine
|
|
|
| |
|
| Status: |
(Mitteilung) Reaktion unnötig | | Datum: | 11:20 Mo 03.09.2007 | | Autor: | matux |
$MATUXTEXT(ueberfaellige_frage)
|
|
|
| |
|
| Status: |
(Frage) überfällig | | Datum: | 20:29 Mo 03.09.2007 | | Autor: | setine |
Hi allerseits ;)
Ich bin etwas überrascht das ich überhaupt keine Rückmeldung erhalten habe, deswegen frage ich jetzt nochmal nach. Denn eigentlich finde ichs immer wieder schön wenn man eine Brücke schlagen kann zwischen verschiedenen Teilgebieten (in meinem Fall ziemlich unterschiedlichen Fächern).
Mir persöhnlich hilft das am meisten den Stoff wirklich zu verstehen ;)
Allerdings studiere ich auch nicht Mathe, und deswegen weiss ich auch nie so recht ob ich mich, zB bei einer solchen Frage, zu sehr aufs Glatteis begebe. Vielleicht ist ja meine Vermutung absurd und ich merks nicht.. hehe
Was meint ihr denn dazu? Es muss keine konkrete "Antwort" auf die Frage sein, aber vielleicht eure Gedanken dazu? Wie würded ihr so eine Vermutung anpacken? Wie würded ihr sowas zu beweisen versuchen? Irgendwas ;)
Vielen Dank für eure Zeit und euer Rat,
Setine
PS: Die Vermutung lautet:
Gegeben eine Relation auf einer endlichen Menge in der Matrixschreibweise BxB wobei B={0,1}
Behauptung:
Die Relation ist genau dann transitiv, wenn die Matrix (interpretiert als ZxZ Matrix, also auf den natürlichen Zahlen) positiv semidefinit ist. (Meiner Def. nach also wenn die Eigenwerte grösser gleich 0 sind)
|
|
|
| |
|
| Status: |
(Mitteilung) Reaktion unnötig | | Datum: | 21:20 Mi 05.09.2007 | | Autor: | matux |
$MATUXTEXT(ueberfaellige_frage)
|
|
|
|
