Permutationsmatizen auffinden < Lineare Algebra < Hochschule < Mathe < Vorhilfe
|
| Status: |
(Frage) beantwortet  | | Datum: | 14:51 Mi 09.06.2004 | | Autor: | Dirk |
Hallo Zusammen!
Ich bin auf meiner Suche im I-Net auf dieses sehr interessante Forum gestoßen. Vielleicht könnt ihr mir hier weiterhelfen:
Gesucht sind die Permutationsmatrizen P und Q (P und Q sind demnach quadratisch und die Spalten- bzw. Zeilensumme ist jeweils 1) so dass die Gleichung PAQ=B erfüllt ist, wobei A und B reelwertige quadratische Matrizen sind.
Gibt es da eine Möglichkeit aus der Kenntnis von A und B die Permutationsmatrizen zu bestimmen, oder die Aussage zu bekommen, dass es keine Permutationsmatrizen gibt die die Gleichung PAQ=B erfüllen.
Vielen Dank schon im Vorraus für eure Bemühungen.
Grüße,
Dirk
P.S.: Ich weiß nicht genau wie ernst ihr die Antwortszeit nehmt. Ich wäre zwar an einer schnellen Antwort interessiert, aber eine spätere Antwort ist nicht schlimm, da mich diese Frage nicht nur gerade in diesem Augenblick interessiert.
|
|
| |
|
| Status: |
(Mitteilung) Reaktion unnötig  | | Datum: | 16:24 Mi 09.06.2004 | | Autor: | Paulus |
Hallo Dirk
ich würde mich gerne mit dieser interessanten Frage ein Bisschen beschäftigen, habe aber noch eine kleine Frage: gibt es zu den Matrizen $A$ und $B$ keine Einschränkungen? Ein erster flüchtiger Blick auf diese Aufgabe lässt mich nämlich vermuten, dass zum Beispiel in $A$ und $B$ nur die gleichen Einträge, einfach in anderer Anordnung, vorkommen dürfen.
Hast du vielleicht ein konkretes Beispiel?
Mit lieben Grüssen
|
|
|
| |
|
| Status: |
(Mitteilung) Reaktion unnötig | | Datum: | 18:21 Mi 09.06.2004 | | Autor: | Dirk |
Hallo Paulus,
in meinem vorliegenden Fall geht es darum zu überprüfen, ob zwei statistische Versuchspläne gleich sind. D.h. sie enthalten nur die Zahlen +1 und -1 und sind gleich wenn sie nur mittels Zeilen- und Spaltenvertauschungen ineinander überführbar sind. Und das machen ja gerde die gesuchten Permutationsmatrizen.
(Ganz konkret: Ist ein fraktionierter faktorieller [mm] 2^{7-4} [/mm] Versuchsplan gleich einem Plackett Burmann Design für 7 Faktoren. Ja ist es, aber ich würde das gern verallgemeinert lösen können.)
Ich hoffe damit kannst du dir ein besseres Bild machen.
Grüße,
Dirk
|
|
|
| |
|
Da es schon eine kleine Ewigkeit her ist, dass ich mich intensiver mit Linearer Algebra beschaeftigt habe, schreibe ich nur mal meine ersten Gedanken auf.
Zunaechst gilt fuer eine Permutation immer, dass sie sich als Produkt von Transpositionen schreiben laesst. Hier gilt:
[mm] \sigma [/mm] = [mm] \tau_1 \tau_2 \ldots \tau_r [/mm] = [mm] (\tau_r)^{-1} \ldots \tau_1^{-1} [/mm] = [mm] \sigma^{-1}
[/mm]
Also auch [mm] \sigma^2 [/mm] = id
Fuer A = B waren dann P = Q beliebige Permutationsmatritzen.
Damit folgt auch, dass P [mm] \neq [/mm] Q, falls A [mm] \neq [/mm] B.
Da aber PAQ=B gelten soll ist:
P=BQA
Es gilt also fuer eine Spalte [mm] A_i:
[/mm]
[mm] A_i [/mm] = [mm] B_\sigma(i) [/mm] fuer eine Permutation [mm] \sigma
[/mm]
Vergleicht man also alle Spalten von A mit denen von B findet man eine Permutation Z von A nach B, unter der Voraussetzung, das eine existiert. Ansonsten findet man eine Spalte [mm] A_t \neq B_i [/mm] fuer alle i.
Problem:
Z = PQ hat keine eindeutige Loesung.
Das bedeutet wiederum, dass man prinzipiell ueber P und Q nicht viel sagen kann.
|
|
|
| |
|
| Status: |
(Mitteilung) Reaktion unnötig | | Datum: | 17:12 Mi 09.06.2004 | | Autor: | Julius |
Hallo Ancillus!
> Da aber PAQ=B gelten soll ist:
> P=BQA
Wie kommst du darauf? Es muss doch nicht [mm] $A^2 [/mm] = id$ gelten?
Muss es nicht
[mm] $P=BQA^{-1}$ [/mm] heißen?
(Vorausgesetzt, dass $A$ invertierbar ist, was ja auch nicht klar ist.)
Oder habe ich da was falsch interpretiert?
Liebe Grüße
Julius
|
|
|
| |
|
| Status: |
(Mitteilung) Reaktion unnötig | | Datum: | 18:35 Mi 09.06.2004 | | Autor: | Dirk |
Hallo Ancillius,
vielen Dank für deine Antwort. Allerdings verstehe ich sie nicht ganz. Kann daran liegen, dass wir vielleicht was unterschiedliches meinen. Hier mal ein konkretes Beispiel:
[mm] A=\begin{pmatrix}
1 & 2 & 3 \\
4 & 5 & 6 \\
7 & 8 & 9
\end{pmatrix}
[/mm]
[mm] P=\begin{pmatrix}
0 & 0 & 1 \\
1 & 0 & 0 \\
0 & 1 & 0
\end{pmatrix}
[/mm]
[mm] Q=\begin{pmatrix}
0 & 1 & 0 \\
0 & 0 & 1 \\
1 & 0 & 0
\end{pmatrix}
[/mm]
[mm] \Rightarrow B=PAQ=\begin{pmatrix}
9 & 7 & 8 \\
3 & 1 & 2 \\
6 & 4 & 5
\end{pmatrix}
[/mm]
So, nun sind aber nur A und B bekannt P und Q allerdings nicht. Wie finde ich nun die Stellen von P und Q an denen die 1en stehen müssen um die Gleichung B=PAQ zu erfüllen?
Meintest du das?
Grüße,
Dirk
|
|
|
| |
|
| Status: |
(Mitteilung) Reaktion unnötig | | Datum: | 12:05 Fr 11.06.2004 | | Autor: | Ancillius |
Paulus Anmerkung war natuerlich richtig. Es ging mir darum, die Permutationsmatritzen an PQ an B zu schieben. A sollte nicht verschoben werden.
Es sollte also heissen:
A=PBQ
was aber natuerlich unnuetz ist. Ich hatte mich leider in Gedanken mit P und A vertan.
|
|
|
| |
|
| Status: |
(Antwort) fertig  | | Datum: | 20:57 Mi 09.06.2004 | | Autor: | Paulus |
Hallo Dirk
ich nehme das Beispiel, das du für Ancillius genommen hast, um die Lösung zu zeigen:
[mm]A=\begin{pmatrix}1&2&3\\4&5&6\\7&8&9\end{pmatrix}P=\begin{pmatrix}0&0&1\\1&0&0\\0&1&0\end{pmatrix}Q=\begin{pmatrix}0&1&0\\0&0&1\\1&0&0\end{pmatrix}\Rightarrow B=PAQ=\begin{pmatrix}9&7&8\\3&1&2\\6&4&5\end{pmatrix}[/mm]
Wie du unschwer feststellen kannst, wird es nie und nimmer möglich sein, Elemente aus einer Zeile auf unterschiedliche Zeilen zu verteilen. Die 1. Zeile bleibt zusammen, das heisst, 1,2 und 3 bleiben in einer Zeile, wenn auch nicht in der gleichen Reihenfolge.
Desgleichen mit den Spalten.
Und jetzt kannst du doch einfach für die Zeilen folgede Ueberlegung machen:
Um von $B$ nach $A$ zu kommen (beachte die Reihenfolge), muss die 1. Zeile zur 3. gehen (1->3); die 2. Zeile zur 1. (2->1); und die 3. Zeile zur 2. (3->2).
Wenn du die Werte in den Klammern anschaust, so hast du gerade die Indizes, wo in der Matrix P die 1 einzutragen sind.
Für die Matrix Q kannst du nun das Entsprechende tun, nur musst du hier von der Matrix $A$ aus gehen und $B$ als Zielmatrix betrachten:
Die 1. Spalte wandert zur 2. (1->2); ... (2->3); ... (3->1).
In der Matrix Q sind also die Elemente [mm] $q_{12}$, $q_{23}$ [/mm] und [mm] $q_{31}$ [/mm] $= 1$ zu setzen.
So, ich hoffe, nichts falsch gemacht zu haben, und dass du das auch auf mehrere Dimensionen verallgemeinern kannst.
Mit lieben Grüssen
|
|
|
| |
|
| Status: |
(Frage) beantwortet | | Datum: | 18:02 Do 10.06.2004 | | Autor: | Dirk |
Hallo Paulus,
vielen Dank, die Idee ist gut.
Allerdings scheint mir, das deine Idee nur für Matrizen klappt die mit Elementen besetzt sind, die nicht doppelt vorkommen. In meinem konkreten Fall geht es um folgende Matrizen:
A = [mm] \pmat{ +1 & -1 & -1 & +1 \\ +1 & +1 & -1 & -1 \\ +1 & -1 & +1 & -1 \\ +1 & +1 & +1 & +1}
[/mm]
P = [mm] \pmat{ 0 & 0 & 1 & 0 \\ 0 & 0 & 0 & 1 \\ 1 & 0 & 0 & 0 \\ 0 & 1 & 0 & 0}
[/mm]
Q = [mm] \pmat{ 0 & 1 & 0 & 0 \\ 0 & 0 & 0 & 1 \\ 1 & 0 & 0 & 0 \\ 0 & 0 & 1 & 0}
[/mm]
[mm] \Rightarrow [/mm] PAQ=B= [mm] \pmat{ +1 & +1 & -1 & -1 \\ +1 & +1 & +1 & +1 \\ -1 & +1 & +1 & -1 \\ -1 & +1 & -1 & +1 }
[/mm]
Ich habe dein Verfahren darauf ausprobiert und leider sind dann Zuordnungen nicht mehr eindeutig. Ich habe dann die erste noch nicht durch eine Zuordnung belegte Spalte genommen, die den Anforderungen entspricht. Beispiel: 1. Spalte von A wird eindeutig der 2. Spalte von B zugeordnet. Die 2. Spalte von A kann nun aber der 1., 3. oder 4. Spalte von B zugeordnet werden. Ich habe da die erste Möglichkeit genommen, also die 1. Spalte. Dann noch 3 -> 3 und 4 -> 4.
Die Zeilen analog.
Beim Test habe ich festgestellt, das es nicht past. Die Zeilenvertauschen sind korrekt rausgekommen, bei den Spalten hätte aber die 2. Spalte von A auf die 4. (nicht die 1.) Spalte von B und die 4. Spalte von A auf die 1. (anstatt der 4.) Spalte von B gemußt.
Ich komme so meinem Ziel schon näher, da man so zwei Matrizen schon eher ansieht ob sie durch Zeilen- und Spaltevertauschungen ineinander überführbar sind, aber ich möchte das dem Computer beibringen, und der würde das nicht sehen. Hast du, oder jemand anders, noch eine Idee ob das Auffinden von Permutationsmatrizen auch für die obigen Matrizen zu erweitern ist?
Vielen Dank!
Grüße,
Dirk
Edit: Matrix B berichtigt.
|
|
|
| |
|
| Status: |
(Antwort) noch nicht fertig  | | Datum: | 19:18 Do 10.06.2004 | | Autor: | Paulus |
Hallo Dirk
kannst du mir bitte die gegebene (also nicht die berechnete) Matrix B noch nachliefern.
Irgendetwas kann ja nicht stimmen, da deine 3. Zeile ja nur 1 Mal ein -1 hat, in Matrix A kommen aber überall 2 vor (mit ausnahme von Zeile 4, selbstverständlich)
Ich muss aber gleich weg, bin erst etwa ab Mitternacht wieder hier.
Mit lieben Grüssen
|
|
|
| |
|
| Status: |
(Mitteilung) Reaktion unnötig | | Datum: | 20:19 Do 10.06.2004 | | Autor: | Dirk |
Hallo Paulus,
ja, da scheint was falschgelaufen zu sein. Ich habe die Matrix B nur berechnet, um sicher zu sein, dass es auch eine Permutation gibt, mittels der A nach B überführt werden kann. Im Endeffekt soll das nachher auch mit einer 8x8-Matrix laufen, aber als Beispiel reichen hoffentlich 4x4-Matrizen.
Hier nun die richtige Matrix
B = [mm] \pmat{ +1 & +1 & -1 & -1 \\ +1 & +1 & +1 & +1 \\ -1 & +1 & +1 & -1 \\ -1 & +1 & -1 & +1 }
[/mm]
Viele Grüße,
Dirk
P.S.: Ich habe die Matrix B im ersten Post berichtigt.
|
|
|
| |
|
| Status: |
(Mitteilung) Reaktion unnötig | | Datum: | 00:47 Fr 11.06.2004 | | Autor: | Paulus |
Hallo Dirk
ich habe noch ein wenig geknobelt, bin aber noch nicht zu einem greifbaren Ergebnis gekommen. Auch bin ich zu müde, ich werde mich am Freitag nochmals hinter diese Aufgabe setzen!
Gute Nacht!
|
|
|
| |
|
| Status: |
(Antwort) fertig | | Datum: | 16:29 So 13.06.2004 | | Autor: | Paulus |
Hallo Dirk
ich hoffe, dein Problem sei immer noch von einigem Interesse.
Ich bleibe wieder bei deinem Beispiel, diesmal dem zweiten.
[mm]A=\begin{pmatrix}+1&-1&-1&+1\\+1&+1&-1&-1\\+1&-1&+1&-1\\+1&+1&+1&+1\end{pmatrix}\, B=\begin{pmatrix}+1&+1&-1&-1\\+1&+1&+1&+1\\-1&+1&+1&-1\\-1&+1&-1&+1\end{pmatrix}[/mm]
Hier kann man, wie du selber festgestellt hast, mit meiner Methode auf die unterschiedlichsten Arten für $P$ und $Q$ Matrizen finden. Das Problem ist nur, dass sie dann auch noch zusammenpassen müssen.
Aufgrund deines Beispiels wess man, dass P folgenden Aufbau haben muss, wobei bei den Punkten jeweils eine $0$ oder eine $1$ einzusetzen ist, mit der Einschränkung, dass pro Zeile und Spalte jeweils genau eine $1$ eingesetzt werden darf, der Rest ist mit $0$ aufzufüllen.
[mm]P=\begin{pmatrix}.&.&.&0\\0&0&0&1\\.&.&.&0\\.&.&.&0\end{pmatrix}\, Q=\begin{pmatrix}0&1&0&0\\.&0&.&.\\.&0&.&.\\.&0&.&.\end{pmatrix}[/mm]
Das führt zu folgenden Möglichkeiten für $P$:
[mm]P_{1}=\begin{pmatrix}1&0&0&0\\0&0&0&1\\0&1&0&0\\0&0&1&0\end{pmatrix}\, P_{2}=\begin{pmatrix}1&0&0&0\\0&0&0&1\\0&0&1&0\\0&1&0&0\end{pmatrix}\, P_{3}=\begin{pmatrix}0&1&0&0\\0&0&0&1\\1&0&0&0\\0&0&1&0\end{pmatrix}[/mm]
[mm]P_{4}=\begin{pmatrix}0&0&1&0\\0&0&0&1\\1&0&0&0\\0&1&0&0\end{pmatrix}\, P_{5}=\begin{pmatrix}0&1&0&0\\0&0&0&1\\0&0&1&0\\1&0&0&0\end{pmatrix}\, P_{6}=\begin{pmatrix}0&0&1&0\\0&0&0&1\\0&0&0&0\\1&0&0&0\end{pmatrix}[/mm]
Wenn wir Glück haben, dann ist für ein bestimmtes $P$ die Matrix $PA$ invertierbar, und das zugehörige $Q$ lässt sich berechnen zu [mm] $Q=(PA)^{-1}B$. [/mm] Wenn nicht, dann weiss ich nichts Besseres, als auch für Q die möglichen Varianten zu bestimmen und durch Ausmultiplizieren und Vergleichen ein richtiges zugehöriges $Q$ auszuwählen (es müssten dann auch dafür mehrere Möglichkeiten existieren).
Bei deinem jetzigen Beispiel ist das nicht der Fall, das heisst, ich kann einfach zum Beispiel [mm] $P_{1}$ [/mm] wählen, und das zugehörige $Q$ berechnen.
Ich habe aber doch mal alle Möglichkeiten für $Q$ zusammengestellt und bin auf die 6 Möglichkeiten gekommen:
[mm]Q_{1}=\begin{pmatrix}0&1&0&0\\1&0&0&0\\0&0&1&0\\0&0&0&1\end{pmatrix}\, Q_{2}=\begin{pmatrix}0&1&0&0\\1&0&0&0\\0&0&0&1\\0&0&1&0\end{pmatrix}\, Q_{3}=\begin{pmatrix}0&1&0&0\\0&0&1&0\\1&0&0&0\\0&0&0&1\end{pmatrix}[/mm]
[mm]Q_{4}=\begin{pmatrix}0&1&0&0\\0&0&0&1\\1&0&0&0\\0&0&1&0\end{pmatrix}\, Q_{5}=\begin{pmatrix}0&1&0&0\\0&0&1&0\\0&0&0&1\\1&0&0&0\end{pmatrix}\, Q_{6}=\begin{pmatrix}0&1&0&0\\0&0&0&1\\0&0&1&0\\1&0&0&0\end{pmatrix}[/mm]
Die Möglichkeiten, dass $PAQ=B$ gilt, sind die Folgenden:
[mm] $P_{1}AQ_{5}=B\, [/mm] ; [mm] P_{2}AQ_{6}=B\, [/mm] ; [mm] P_{3}AQ_{2}=B\, [/mm] ; [mm] P_{4}AQ_{4}=B\, [/mm] ; [mm] P_{5}AQ_{1}=B\, [/mm] ; [mm] P_{6}AQ_{3}=B$
[/mm]
So, ich hoffe, dass du mit diesen Angaben etwas weiter kommst mit deinem Programm
Liebe Grüsse
|
|
|
| |
|
| Status: |
(Mitteilung) Reaktion unnötig | | Datum: | 19:46 Do 17.06.2004 | | Autor: | Dirk |
Hallo Paulus,
vielen Dank für deine Antwort, sie hat mir weitergeholfen auch wenn sie nicht einfach zu implementieren sein wird.
Tut mir leid, dass ich erst so spät antworte, hatte in der letzten Zeit viel um die Ohren.
Auf jeden Fall super, dass ihr mir geholfen habt. Vielen Dank!
Grüße,
Dirk
|
|
|
|
