Problem - Matrix berechnen

[Donnerknall]

Ich hätt folgendes Problem, das eigentlich simpel aussieht, aber ich nicht damit zu Rande komme.

Gegeben 2 Matrizen: G,X
Gesucht Matrix Y

Es gilt:
Y*G = X*Y
bzw umgeformt
Y*G - X*Y = 0

(es gibt auf jeden Fall mehrere Lösungen, zB ist die Nullmatrix eine Lösung,
welche natürlich nicht gesucht ist)

Wie lös ich sowas?
Auf dem Papier alles kein Problem, man kann n^2 Gleichungen aufstellen und
das LGS dann lösen. Aber welche Sprache kann mit unbelegten Variablen
rechnen?

(ich hoffe ich bin im richtigen Forum, wusste nicht, wo ich es reinstellen
sollte.)

Ich hoff jemand kann mir helfen, so langsam verzweifel ich.

Joachim

[bischi]

Variante Nr1: Numerisch
Variante Nr2: Mit nem Mathematikprogramm (bspw. Matlab/Octave)

MfG Bischi

[Christoph]

Was suchst Du denn? Eine symbolische Lösung (geht nur von Hand oder mit kommerziellen Programmen wie Mathematica oder Maple) oder eine numerische Lösung (geht mit Scilab oder Octave).

[Donnerknall]

ok, danke, das wollte ich hören.

ich war mir ziemlich sicher, dass dies so nicht geht, wollte es aber nochmals
bestätigt haben. shit!

[foobarflu]

Y*G - X*Y = 0

Korrigier mich, aber daraus resultiert ein lineares Gleichungssystem mit n^2 unbekannten (die Koeffizienten von Y), oder?

Das kannst Du dann einfach mit den üblichen Verfahren (gauss, jacobi, cg, sor, ...) lösen (einfach auch als Matrix / Array darstellen)

[peschmae]

Ja, das hat er ja im OP auch gesagt. Genau deswegen seh ich auch das Problem nicht so ganz. Mal abgesehen davon dass sich in manchen Fällen (fies, fies) unendlich viele mögliche Lösungen anschleichen, weil für die n^2 Koeffizienten nur n Gleichungen existieren.

MfG Peschmä

[Donnerknall]

ja, von hand per LGS lösen ist ja kein problem.

aber lass das mal ein programm machen... geschrieben in C o.ä.
(ich muss ne andere müllsprahce benutzen, aber is ja dasselbe problem)

mit matlab (o.ä.) ginge es, aber das kann ich in dem prog nicht benutzen...

[mehlvogel]

LGS lösen? Wo ist denn das Problem?

[Donnerknall]

äää steh ich völlig auf dem schlauch?


dann sag mir mal wie du es in zB C lösen würdest, es tuts auch pseudocode.

[mehlvogel]

Naja um LGS zu lösen gibt es eine Vielzahl von Algorithmen, eine Liste findest du z.B. hier:
http://de.wikipedia.org/wiki/Liste_numerischer_Verfahren
Pseudocode ist dort bei einigen vorhanden.

[Donnerknall]

entweder ihr versteht nicht was ich meine, oder ich bin total blöde, aber
es macht doch nen unterschied, ob ich das lösen will:
http://www.jschittenhelm.de/pics/pic1.jpg
was kein problem ist, (gauss o.ä.)

oder ob ich dafür eine lösung suche:
http://www.jschittenhelm.de/pics/pic2.jpg
wobei man nicht nach der gesuchten Matrix auflösen kann.
(conjugation-problem / inner automorphism problem)


sorry für die paint stümperei, aber ging am schnellsten :-)

[foobarflu]

weil für die n^2 Koeffizienten nur n Gleichungen existieren.

Redest Du nur von den Spezialfällen?
In der Regel hast Du hast auch n^2 Gleichungen (vielleicht haben wir auch nur unterschiedliche Terminologie, z.B. ist Y eine 2x2 Matrix wäre n=2 bei mir)

Donnerkeil: nimm dir ein 2x2 System mit
Y = [y1 y2; y3 y4]
X = [x1 x2; x3 x4]
G = [g1 g2; g3 g4]
und schreib Dir die Matrixprodukte hin.


Y * G = [y1*g1 + y2*g2 y1*g2 + y2*g4;
y3*g1 + y4*g2 y3*g2 + y4*g4]
X * Y = [x1*y1 + x2*y3 x1*y2 + x2*y4;
x3*y1 + x4*y3 x3*y2 + x4*y4]

Die Dinger müssen komponentenweise übereinstimmen (in diesem Fall liefert das vier Gleichungen).
Schreib es
Y*G - X*Y = 0
hin und schon hast Du ein homogenes lineares Gleichungssystem

[Donnerknall]

ja, das ist mir alles schon klar. so funzt das auf einem blatt wunderbar.
aber prog das mal.

die x_i sind bekannt, genau wie die g_i.
die y_i natürlich nicht.

so, und wie rechnest du jetzt mit den NICHTBELEGTEN variablen y_i?

x1*y1 + x2*y3 = y1*g1 + y2*g3

y_i sind unbekannt, nicht belegte variablen oder was auch immer.
x_i und g_i sind gegebene zahlen.

aber in ner normalen sprache kannst ja keine unbelegten variablen addieren,
oder multiplizieren, was du ja bei x1*y1+x2*y3... machen müsstest!

[foobarflu]

ja, das ist mir alles schon klar. so funzt das auf einem blatt wunderbar.
aber prog das mal.

Das ist deshalb kein Problem, weil es sich als lineares Gleichungssystem A*y = b darstellen lässt. Wenn Du willst kannst Du es auch umformulieren zu
A^-1 * b = y

Damit stehen auf der linken Seite nur bekannte Sachen und Du hast einen Ausdruck für die rechte Seite. Ist allerdings die schlechteste Methode, ein Gleichungssystem zu lösen.

Du brauchst nicht mit symbolischen Variablen arbeiten. Das ist dein Denkfehler. Welches y_i dazugehört ist durch die Position des Koeffizienten in der Matrix definiert.

Oder hakt es daran, dass Du übersiehst, dass die Dinger jeweils komponentenweise 0 sein müssen?
Spezifisch:
(y1*g1 + y2*g2) - (x1*y1 + x2*y3) = 0
=> (g1 - x1)*y1 + g2*y2 + x2*y3 = 0

[Donnerknall]

ok, mit dem risiko, dass ich mich jetzt als volldepp oute (sofern ich das nicht
schon getan hab), wie kannst Du die Matrix-Gleichung

YG=XY

nach Y auflösen?
geht doch nicht...sonst wär es billig und ich hätt hier nicht gefragt.

wenn Du kurz Zeit hast, dann zeig mir mal für

Y = [y11 y12; y21 y22];
G = [2 0,0 1]
X = [0 3,1 3]

wie Du das löst. (rechne mod 5, ist aber nicht relevant)

EDIT:
ne, dass sie komponentenweise gleich respektive null sein müssen hakt es nicht.

und

es geht ja um nen allgemeinen fall, nicht vordefiniert für n=2...


EDIT:
häää wieso is der post doppelt drin, hab doch ändern geklickt.... naja... kann n mod den davor löschen... sorry!

[mehlvogel]

Okay, für den Fall n = 2 (das verallgemeinern auf n sollte dann etwas denkarbeit erfordern, aber möglich sein):



Y = [y1, y2; y3, y4], G = [g1, g2; g3; g4], X = [x1, x2; x3, x4]


So daraus folgen folgende Gleichungen:



g1 * y1 + g3 * y2 = x1 * y1 + x2 * y3
g2 * y1 + g4 * y2 = x1 * y2 + x2 * y4
g1 * y3 + g3 * y4 = x3 * y1 + x4 * y3
g2 * y3 + g4 * y4 = x3 * y2 + x4 * y4

=>

(g1 - x1) * y1 + g3 * y2 - x2 * y3 = 0
g2 * y1 + (g4 - x1) * y2 - x2 * y4 = 0
-x3 * y1 + (g1 - x4) * y3 + g3 * y4 = 0
-x3 * y2 + g2 * y3 + (g4 - x4) * y4 = 0


Das entspricht folgendem LGS:



[ (g1 - x1), g3, -x2, 0 ] [ 0 ]
[ g2, (g4 - x1), 0, -x2 ] [ 0 ]
[ -x3, 0, (g1 - x4), g3 ] * y = [ 0 ]
[ 0, -x3, g2, (g4 - x4) ] [ 0 ]


Das kann man lösen, da ja alle x und g gegeben sind.
Das Problem scheint zu sein, das in eine allgemeine Form zu verwandeln, das geht aber. Mir fehlt jetzt die Zeit um die Formeln explizit anzugeben, aber versuchs mal selbst.

[Donnerknall]

ja, die allgemeine Form ist das Problem.

Wenn es immer matrizengröße n=2 wäre, dann klar, dann kann ich die
Lösung ja mehr oder weniger vordefinieren.

[foobarflu]

Mh... dein Problem ist bedeutsamer als es aussieht, oder?

Die Lösung für dein Beispiel ist die Nullmatrix, oder? E.g. dass G und X nicht ähnlich sind.

Mit
G = [ 1 0; 1 0]
X = [ 0 2; 0 1]
ist z.B. Y = [1 1; 1 0]

[Donnerknall]

ja, ich find jedenfalls keine lösung, wüsste auch nicht wie es lösbar wäre.

ich dacht ich steh total auf dem schlauch, da ihr alle sagtet, dass es kein prob wäre.

es geht um das innere automorphismus problem (=konjugation) in gl(n,q).
die gleichung YG=XY (bzw. YGY^(-1) = X) hat q lösungen, wobei eine (nicht
sinnvolle lösung) die nullmatrix ist, aber die will ich ja nicht.

[foobarflu]

ich dacht ich steh total auf dem schlauch, da ihr alle sagtet, dass es kein prob wäre.

Da haben glaub ich alle dein Problem mißverstanden. Dein Problem ist es, eine "Formel" für die linke Seite des Gleichungssystems zu finden, oder?

Das Problem dabei ist, dass man da ziemlich heftig der Matrizenmultiplikation rumspielen muss um in einem beliebigdimensionalen Raum zu lösen.
Das ist deshalb ein Problem, weil Du heftigst mit Summenregeln hantieren musst.
Für 2d und 3d kann man das noch ausschreiben, darüber wird's schon richtig eklig. Da kann ein Computer in der Regel auch nichts machen sondern man muss ihm die Koeffizienten vorgeben (es sei denn, man verwendet ein computeralgebrasystem, das mit symbolischen Variablen rechnen kann - ich bezweifle aber, dass das dieses Problem aus der Handgelenk lösen kann)

[Donnerknall]

also ich hab's gelöst, es geht, Mehlvogel hatte recht!

man kann die Koeffizientenmatrix in einer allgemeinen Form angeben, die
ziemlich einfach aussieht, hätt ich anfangs nicht gedacht.

Falls es jemand interessiert kann ich diese kurz "aufmalen" :-)

Danke jedenfalls nochmal!

[mehlvogel]

Das würde mich in der Tat interessieren - ich habe es mal versucht, hatte aber nicht die Zeit das ganz bis zum Ende durchzuziehen. :)

[Donnerknall]

YG-XY=0

G,X,Y sind n x n Matrizen.

man kann dies umformen zu

H*Y = 0
wobei H eine n² x n² Matrix ist und Y ein n² Vektor, der später zur Matrix
Y zurückgewandelt wird.

H*Y = (G' - X')Y = 0
man kann H durch 2 Matrizen ersetzen. In G' fliessen die Koeffizienten von G
und in X' fliessen die Koeffizienten von X ein.

Form von G'
die n² x n² Matrix kann man in n x n Blöcke aufteilen, das heisst also n Blöcke
hoch, n Blöcke breit. In den n Diagonalblöcken steht jeweils G^T (also die
zu G transponierte Matrix), alle anderen Blöcke sind n x n Nullmatrizen.

Form von X'
die n² x n² Matrix kann man ebenfalls in n x n Blöcke aufteilen wie G'.
Jeder der Blöcke ist eine Diagonalmatrix der Größe n x n.
Block[Zeile = 1][Spalte = 1] hat als Diagonaleinträge je den Wert X[1][1]
Block[1][2] hat als Diagonaleinträge je den Wert X[1][2]
...
Block[n][n] hat als Diagonaleinträge je den Wert X[n][n]


also alles sehr einfach.

[peschmae]

Redest Du nur von den Spezialfällen?

Nein, ich redete Blödsinn. Kommt davon wenn man meint das Zeugs nicht aufschreiben zu müssen :D

Mann muss sich halt hinsetzen und das Zeugs aufschreiben und mit Geduld und Bleistiftminen bewerfen bis es in die Ecke gedrängt ist. Gut gemacht Donnerknall ;)

MfG Peschmä