Matrix invertieren mit Modulo

21.03.2018, 17:44

Orly

Matrix invertieren mit Modulo

[attach]46745[/attach]

Hallo,

es geht um die im Bild beigefügte Aufgabe. Genau genommen um den Aufgabenteil 3c) mit dem Modulo.

Zu a) und b) habe ich bestimmt, dass die Determinante = -25 ist und die Matrix somit invertierbar sein sollte, das ist richtig oder? Mich macht die Bemerkung in c) ein wenig stutzig "Zeigen Sie die Matrix ist JETZT invertierbar"

Mein Problem ist jetzt allerdings das Modulo in c). Wenn ich einfach nach Gauß II+2*I anwende bekomme ich ja in der zweiten Zeile direkt ein Problem. Ich vermute mal der Trick liegt nun darin die Zeilen irgendwie "über die 17 hinaus zu multiplizieren" damit sich durch das Modulo dieser Fehler nicht mehr ergibt. Wie man dies aber jetzt methodisch angeht weiß ich nicht.

Also ich könnte ja zum Beispiel die zweite Zeile mit 5 multiplizieren damit diese zu -10 14 1 wird und damit dann das Problem lösen, allerdings erschließt sich mir die offizielle Methode noch nicht, es muss doch einen besseren Weg geben als spontan Sachen hochzumultiplizieren und dann mal schauen wie es läuft.

Den im Hinweis erwähnten Euklidischen Algorithmus habe ich mir bereits angeschaut und auch soweit verstanden, inwiefern der mir jetzt hier hilft ist mir aber nicht klar.

Vielen Dank

21.03.2018, 18:08

Elvis

Auf diesen Beitrag antworten »

Die Matrix ist über $\begin{eqnarray*} \mathbb Q \end{eqnarray*}$ invertierbar, aber nicht über $\begin{eqnarray*} \mathbb Z \end{eqnarray*}$ . Wenn du mit rationalen Zahlen invertierst, wirst du Komponenten mit $\begin{eqnarray*} \frac x {25} \end{eqnarray*}$ bekommen. Mit dem euklidischen Algoritmus kannst du den $\begin{eqnarray*} ggT(17,25)=1=n*17+m*25 \end{eqnarray*}$ darstellen, und wegen $\begin{eqnarray*} n*17\equiv 0 \end{eqnarray*}$ ist $\begin{eqnarray*} m*25\equiv 1 \end{eqnarray*}$ also $\begin{eqnarray*} m=25^{-1} \end{eqnarray*}$ das inverse zu $\begin{eqnarray*} 25 \end{eqnarray*}$ in $\begin{eqnarray*} \mathbb Z/17\mathbb Z \end{eqnarray*}$ .

Tipp: Wegen $\begin{eqnarray*} 25\equiv 8 \end{eqnarray*}$ würde ich mir den euklidischen Algorithmus ersparen.

21.03.2018, 18:41

Orly

Auf diesen Beitrag antworten »

Danke für die Hilfe. Um deinen Kommentar zum Modulo invertieren nachvollziehen zu können brauche ich noch Zeit, aber ich würde dich gerne direkt noch was zu deinem ersten Satz fragen.

Habe ich dich richtig verstanden, dass die Matrix ohne Modulo (so wie in a)) NICHT über Z invertierbar ist?
Falls ja, dann: Als ich aber mit der Regel von Sarrus die Determinante als -25 bestimmt habe, habe ich zu keinem Zeitpunkt mit Zahlen gearbeitet die nicht in Z sind. Jetzt verstehe ich nicht, warum die Matrix nicht invertierbar ist und wenn dem doch so ist, wie kann ich das dann sehen?

Edit: Achso, die 25 nimmst du aus der Det von a) oder? Vielleicht habe ich dich dann falsch verstanden und du kannst den oberen Teil ignorieren. Aber was ist denn nun das Inverse m^-1 und wie bringt mich das weiter? Warum will ich denn den ggT(17,25)?

21.03.2018, 19:27

Elvis

Auf diesen Beitrag antworten »

Invertiere die Matrix mit dem Gauß-Algorithmus, und du siehst, dass die Inverse nicht nur ganze Zahlen sondern auch rationale Zahlen enthält. Also ist sie über $\begin{eqnarray*} \mathbb Z \end{eqnarray*}$ nicht invertierbar, aber über $\begin{eqnarray*} \mathbb Q \end{eqnarray*}$ .
Um modulo $\begin{eqnarray*} 17 \end{eqnarray*}$ zu rechnen musst du nur in der rationalen Inversen alle Einträge modulo $\begin{eqnarray*} 17 \end{eqnarray*}$ rechnen. Bei ganzen Zahlen sind das die kleinsten nichtnegativen Reste $\begin{eqnarray*} 0,1,...,16 \end{eqnarray*}$ . Bei rationalen Zahlen brauchst du die inversen mod $\begin{eqnarray*} 17 \end{eqnarray*}$ , in diesem Beispiel brauchst du speziell $\begin{eqnarray*} \frac 1{25} \end{eqnarray*}$ mod $\begin{eqnarray*} 17 \end{eqnarray*}$ , und ich habe dir gezeigt, wie man das berechnet. Du brauchst nicht $\begin{eqnarray*} m^{-1} \end{eqnarray*}$ , sondern $\begin{eqnarray*} m=25^{-1} \end{eqnarray*}$ aus der Gleichung $\begin{eqnarray*} 1=n*17+m*25\equiv n*17+m*8 \end{eqnarray*}$ . Wenn man die ganzen Zahlen $\begin{eqnarray*} m \end{eqnarray*}$ und $\begin{eqnarray*} n \end{eqnarray*}$ nicht (wie hier) erraten kann, berechnet man sie mit Euklid: $\begin{eqnarray*} ggT(17,25)=1=n*17+m*25 \end{eqnarray*}$ . Du kannst ebenso gut das inverse von $\begin{eqnarray*} 5 \end{eqnarray*}$ mod $\begin{eqnarray*} 17 \end{eqnarray*}$ berechnen und mit sich selbst multiplizieren. Man sieht: modulo ist alles viel einfacher als mit ganzen Zahlen (deswegen hat Gauß die Kongruenzrechnung erfunden, sie erleichtert uns das Leben).

22.03.2018, 13:05

Orly

Auf diesen Beitrag antworten »

Danke für die ausführliche Erklärung, jetzt habe ich das verstanden.

Eine kleine Frage hätte ich jetzt noch:

Da die Matrix über Z nicht invertierbar ist aber über Q und in der Aufgabenstellung steht die Matrix ist aus M(Z) bedeutet das doch, dass die Matrix in Aufgabenteil a) nicht invertierbar ist, richtig?

Das bedeutet, wenn ich zu Aufgabe a) lediglich die Determinante als ungleich Null bestimmt habe und daraus schließe, dass die Matrix invertierbar ist, dann liege ich damit ja falsch. Gibt es einen effektiven Weg direkt herauszufinden ob die Matrix über Z invertierbar ist, oder muss ich bei einer solchen Fragestellung immer versuchen die inverse Matrix aufzustellen (bis zu dem Punkt an dem ich merke, dass ich mit rationalen Zahlen arbeiten muss)?

22.03.2018, 13:12

HAL 9000

Auf diesen Beitrag antworten »

Zitat:

Original von Orly
Gibt es einen effektiven Weg direkt herauszufinden ob die Matrix über Z invertierbar ist

Genau dann wenn Bedingung $\begin{eqnarray*} |\det(A)| = 1 \end{eqnarray*}$ erfüllt ist.

22.03.2018, 13:57

Orly

Auf diesen Beitrag antworten »

Ach so einfach ist das, ja dann wäre jetzt alles geklärt. Danke smile

22.03.2018, 14:09

Elvis

Auf diesen Beitrag antworten »

Stimmt, das erkennt man daran, dass man die inverse Matrix mit der Adjunkten als $\begin{eqnarray*} A^{-1}=\frac 1{det A}adj(A) \end{eqnarray*}$ darstellen kann.

22.03.2018, 14:26

HAL 9000

Auf diesen Beitrag antworten »

Wobei das genau genommen nur sagt, dass $\begin{eqnarray*} |\det(A)|=1 \end{eqnarray*}$ hinreichend ist.

Die Notwendigkeit ergibt sich aber auch rasch aus Bedingung $\begin{eqnarray*} 1 = \det(A)\cdot \det(A^{-1}) \end{eqnarray*}$ .

Neue Frage »

Antworten »

Matrix invertieren mit Modulo

Verwandte Themen