Matrixprodukt auf Ursprungsmatrix zurückführen (Matrix nicht invertierbar)

Neue Frage »

13.01.2011, 19:40	Martin L	Auf diesen Beitrag antworten »
Matrixprodukt auf Ursprungsmatrix zurückführen (Matrix nicht invertierbar) Moin Moin, ich dachte eigentlich, ich hätte hier eine einfache Aufgabe, aber sie ist scheinbar nicht sooo einfach. Wir haben eine Aufgabe, in der erst eine Matrix "codiert" wird, indem sie mit einer Matrix multipliziert wird. Dann sollen wir eine "decodierungsmatrix" finden, mit welcher wir die Matrix multiplizieren, um wieder zurück zu kommen auf unsere Ursprungsmatrix. Mal um die Reihenfolge klar zu machen: Sei M die Ursprungsmatrix Sei K die kodierungsmatrix Sei C die kodierte Matrix dann soll sein: K * M = C Sei jetzt D die Decodierungsmatrix dann soll D * C = M sein. Das ist ja auch kein Problem, so lange K invertierbar ist. Jetzt haben wir hier aber folgende Form: M ist eine 3x5-Matrix und K ist: $\begin{eqnarray} K = \begin{pmatrix} 1 & -2 & 3 \\ 2 & -1&0\end{pmatrix} \end{eqnarray}$ Also ist K ziemlich sicher nicht invertierbar. Die Frage ist jetzt, ob sich trotzdem so ein D finden lässt, so dass sich das Produkt aus K * M wieder decodieren lässt. Ich hab zuerst gedacht, man könnte direkt argumentieren, dass K nicht invertierbar ist aaaber ich habe ein Beispiel gefunden wo es klappt. Dabei kommt es aber (glaube ich) auf die Form von M an. Würde mich wundern wenn das allgemein klappen würde. Wenn M nur Einsen enthält: $\begin{eqnarray} M = \begin{pmatrix} 1 & 1 & 1 & 1 &1 \\ 1 & 1 & 1 & 1 & 1 \\ 1 & 1 & 1 & 1 & 1 \end{pmatrix} \end{eqnarray}$ Wenn ich jetzt KM rechne kriege ich: $\begin{eqnarray} C = \begin{pmatrix} 2 & 2 & 2 & 2 &2 \\ 1 & 1 & 1 & 1 & 1 \\\end{pmatrix} \end{eqnarray}$ Jetzt kann man durch draufschauen die Matrix D: $\begin{eqnarray} \begin{pmatrix} 1 & -1 \\ 0 & 1 \\ 0 & 1\end{pmatrix} \end{eqnarray}$ aufschreiben so dass: D C = M ist. Jetzt weiß ich nicht, wie ich zeigen kann, dass das so nur für bestimmte M möglich ist, bzw vielleicht geht das ja auch für alle M und die Matrix ist dann nur schwerer zu finden (die Matrix D). Habt ihr da noch Ideen? Gruß Martin
14.01.2011, 11:08	Reksilat	Auf diesen Beitrag antworten »
RE: Matrixprodukt auf Ursprungsmatrix zurückführen (Matrix nicht invertierbar) Hi Martin, Schau Dir mal die folgende Matrix an $\begin{eqnarray} M = \begin{pmatrix} 0&0&0&0&0 \\ -1 & -1 & -1 & -1 & -1 \\ 0&0&0&0&0 \end{pmatrix} \end{eqnarray}$ Die wird mit Deinem $\begin{eqnarray} K \end{eqnarray}$ genau ins gleiche $\begin{eqnarray} C \end{eqnarray}$ codiert und somit kann man das ganze gar nicht mehr Rückgängig machen. Es gibt allerdings gewisse Kriterien an die Abmessungen von K und den Rang, die eine Umkehrung möglich machen. Gruß, Reksilat.
14.01.2011, 13:12	Martin L	Auf diesen Beitrag antworten »
Ah stimmt, auch ein sehr guter Weg, da ran zu gehen. Ich hab es jetzt etwas komplizierter gelöst. Ich hab mir einfach zwei Spalten gewählt in meinem M (kann ich ja machen, ich such ja den Text aus, der kodiert werden soll), hab die dann mit K kodiert und mir dann angeguckt, was für die Rückrichtung in der Matrix D stehen muss. Dann bekomme ich in der ersten gewählten Spalte einen festen Eintrag aus einer Zeile in D und mit der zweiten Zeile kann ich dann zeigen, dass ich an dieser Stelle einen anderen Eintrag brauche. Damit hab ich dann gezeigt, dass das halt nur unter gewissen Umständen gilt, also dass es vielleicht auch möglichkeiten gibt, in denen man dekodieren kann, aber es darf ja nicht auf den Text ankommen, ob man ihn nun kodieren darf oder nicht und damit eignet sich die Matrix nicht. Bei deinem Beispiel wird eventuell problematisch, dass man das ja wohl rückgängig machen kann, man muss nur explizit die Dekodierungsmatrix angeben. Es ist halt dann bei gleich aussehender kodierter Matrix einmal die eine und einmal die andere. Du hast damit ja eigentlich nur gezeigt, dass es nicht "EINE" Dekodierungsmatrix gibt. wenn du nämlich mal D := (0 0) (-1 1) (0 0) wählst, dann hast du ja zu deiner Matrix K eine Decodierungsmatrix gefundne, mit der du die von dir durch K verschlüsselte Matrix M entschlüsseln kannst. Die Decodierungsmatrix ist dann halt nur nicht mehr von K sondern von M abhängig. Gruß Martin
14.01.2011, 13:31	Reksilat	Auf diesen Beitrag antworten »
Die Dekodierungsmatrix vom zu kodierenden Code abhängig zu machen ist völliger Unsinn. Ich wollte Dir mit dem Beispiel nur zeigen, dass Deine Codierung nicht mehr rückgängig gemacht werden kann, da Du bei Deiner Codierung Informationen verlierst. Das ist auch schon mit einem kurzen Blick offensichtlich. Deine Matrix M hat 15 beliebige Einträge – die wirst Du mit einer Matrix mit 10 Einträgen nicht sinnvoll codieren können. Wenn Dein K vollen Spaltenrang hat, ist es allerdings möglich. Gruß, Reksilat.
14.01.2011, 13:37	Martin L	Auf diesen Beitrag antworten »
Ja, ist völlig Unsinnig und ich denke, das hätte so sicher auch gereicht. Ich wollte nur lieber ein Beispiel haben, in dem es nicht nur sinnlos ist, sondern auch Mathematisch schlicht nicht möglich ;-). Das mit dem Spaltenrang ist aber interessant, ich hab jetzt nämlich noch eine Matrix zu prüfen, die hat 4 zeilen und 3 spalten. Die hat auf den ersten Blick vollen Spaltenrang. ich versuch mich mal daran :-)
14.01.2011, 14:24	Martin L	Auf diesen Beitrag antworten »
Mhh ich hätte da eine Idee wie ich zeigen kann, dass das nicht geht: (gaube ich) wenn ich meine 3x5-Matrix M kodiere mit meiner Matrix K von der Größe 4x3 Dann erhalte ich eine Matrix der Größe 4x5. Meine Decodiermatrix muss also die Größe 3x4 haben, damit ich sie überhaupt von links an meine kodierte Matrix multiplizieren kann und danach wieder eine Matrix erhalte die überhaupt so groß ist wie meine Matrix M. Jetzt betrachte ich nur mal die erste Zeile meiner Decodierungsmatrix $\begin{eqnarray} d_{11},d_{12},d_{13},d_{14},d_{15} \end{eqnarray}$ wenn ich die jeweils mit den Spalten meiner kodierten Matrix C (mit den Einträgen $\begin{eqnarray} c_{ij} \end{eqnarray}$ verrechne, erhalte ich ja wieder die erste Zeile meiner Matrix M. wenn ich das schon weiß, kann ich das ja als Gleichung ausdrücken: $\begin{eqnarray} d_{11}c_{11} + d_{12}c_{21} + d_{13}c_{31} + d_{14}c_{41} = m_{11}<br /> d_{11}c_{12} + d_{12}c_{22} + d_{13}c_{32} + d_{14}c_{42} = m_{12}<br /> d_{11}c_{13} + d_{12}c_{23} + d_{13}c_{33} + d_{14}c_{43} = m_{13}<br /> d_{11}c_{14} + d_{12}c_{24} + d_{13}c_{34} + d_{14}c_{44} = m_{14}<br /> d_{11}c_{15} + d_{12}c_{25} + d_{13}c_{35} + d_{14}c_{45} = m_{15}<br /> \end{eqnarray}$ Das ist ja ein lineares Gleichungssystem, welches überbestimmt ist. Ich habe vier frei wählbare variablen $\begin{eqnarray} d_{11} . . . . d_{14} \end{eqnarray}$ aber 5 Gleichungen. Jetzt werde ich doch bestimmt eine Belegung finden, so dass dieses Gleichungssystem überbestimmt ist oder? Das würde dann doch bedeuten, dass man nicht jede Matrix mit meinem K_3 codieren bzw eine decodierungsmatrix finden kann. Zum kodieren eignen die sich ja grundsätzlich alle, man kriegt den Text nur nie wieder ;-). Ich blicke einfach gerade nicht mehr so durch, ob ich vielleicht schon fertig bin, vielleicht seht ihr da auf den ersten Blick ob ich nen Denkfehler hab. Gruß Martin
Anzeige

14.01.2011, 14:30	Reksilat	Auf diesen Beitrag antworten »
Du hast $\begin{eqnarray} K\cdot M=C \end{eqnarray}$ . Suche nach einer Matrix $\begin{eqnarray} D \end{eqnarray}$ mit $\begin{eqnarray} DK=E \end{eqnarray}$ . Dann ist doch $\begin{eqnarray} M=E\cdot M=D\cdot K\cdot M=D\cdot C \end{eqnarray}$
14.01.2011, 14:42	Martin L	Auf diesen Beitrag antworten »
Ahhh, auf die Idee, das einfach mal hin und her umzuformen bin ich noch nicht gekommen. Das müsste ja sogar eigentlich gehen. Also diese Matrix zu finden. Aber wo ist dann mein Denkfehler mit dem Gleichungssystem? Gruß Martin
14.01.2011, 15:09	Reksilat	Auf diesen Beitrag antworten »
Die Idee hinter Deinem LGS ist nicht richtig, da D ja nicht von M oder C abhängen soll. Es wird sich kein Widerspruch ergeben und unter gewissen Umständen lässt sich auch D rekonstruieren, nur ist die essentielle Information hier eben K. Ein Codeknacker, der K nicht kennt, würde vielleicht so vorgehen. Wenn Du nur die Nullmatrix codierst, wird es aber nichts bringen.
14.01.2011, 15:39	Martin L	Auf diesen Beitrag antworten »
Ach so, stimmt eigentlich. Aber trotzdem muss D nachher doch das lineare Gleichungssystem erfüllen. Wenn ich also wie bei K_1 zeigen kann, dass es ein Lineares Gleichungssystem gibt, welches auf keinen Fall von D erfüllt wird, dann kann ich ja auch keine Decodierungsmatrix finden, die würde das ja eben erfüllen. Gruß Martin
14.01.2011, 15:43	Reksilat	Auf diesen Beitrag antworten »
Wenn Du zeigen willst, dass es keine solche Dekodierung geben kann, dann ist dieses LGS mit konkreten Werten dafür geeignet.
14.01.2011, 15:50	Martin L	Auf diesen Beitrag antworten »
Gut, dann kann ich das nehmen, um zu zeigen, dass es mit K_1 nicht geht, und deine Umformungsidee mit der Einheitsmatrix um zu zeigen, dass es mit K_3 geht Danke sehr, Gruß Martin

Neue Frage »

Antworten »

Matrixprodukt auf Ursprungsmatrix zurückführen (Matrix nicht invertierbar)

Verwandte Themen