Inverse Matrix modulo m mit dem Chinesischen Restsatz

Question

ich muss von einer Matrix  M modulo n die Inverse M^-1 bestimmen. Wie das mit der Adjunkten geht, habe ich verstanden. Jedoch verlangt die Aufgabenstellung, dass ich die Inverse mit dem chinesichen Restsatz berechnen soll. Ich sehe da jedoch keinen Zusammenhang. Über Lösungsansätze würde ich mich freuen.

Comments

Ohne die exakte Aufgabenstellung ist es schwierig deine Frage zu beantworten.

(Du frägst im Wesentlichen: " WIe ist ... gemeint?" ohne ... zu verraten)

Vermutlich ist das n hier eine zusammengesetzte Zahl und man kann den chin. Restsatz anwenden um das Problem auf das Invertieren in einem (endlichen) Körper zu reduzieren.

---

ok danke.. damit kann ich schonmal was anfangen :)...also noch etwas konkreter: Ich muss das Inverse M^-1 einer 3x3 Matrix (irgendwelche Zahlen halt)  modulo 1111 mit dem Chinesischen Restsatz berechnen.

Answer 1

Der hinesische Restsatz induziert einen Isomorphismus

$$Gl(3,\mathbb Z/ 1111\mathbb Z ) \cong Gl(3,\mathbb Z/ 11\mathbb Z ) \times Gl(3,\mathbb Z/ 101\mathbb Z )$$

damit kann man ein Inveres modulo 1111 berechnen indem man die Inversen mod 11 und mod 101 berechnet.

Comments

ich hab ein ähnliches Problem und wollte fragen, ob Du mir vielleicht kurz erklären könntest, wie du den chinesischen Restsatz benutzt hast, so dass du mod 1111 in mod 11 und mod 101 "heruntergebrochen" hast.

---

hi, habs jetzt so gelöst, dass ich erst die Inverse  M' mod 11 und danach die Inverse M''mod 101 berechnet habe ( mit Determinante und Adjunkten) . Anschließend mim chinesischen Restsatz wieder auf 1111 "hochgerechnet" (also m'_ij mit m''_ij verrechnet). Geht eventuell noch besser, weil letztendlich könnte ich ja gleich mit Determinate und Adjunkten die Inverse mod 1111 berechnen^^....aber Aufgabenstellung verlangt halt den chinesischen Restsatz ..und die Lösung stimmt immerhin, von daher...

---

Das ist im Wesentlichen das Vorgehen mit den chin. Restsatz. Das inverse der Matrix über den chin. Restsatz zu berechnen ist nicht wirklich die schnellste Methode...

---

Und wie hast du erklärt, dass du auf die 101 und die 11 kommst? Denn das kann ja nicht vom Himmel fallen, oder? Wie man zurück rechnet, ist mir - glaube ich - klar.

P.S.: Ist das zufällig eine Kryptografie-Übung ;)

---

Ich hab noch keinen Korrektor gesehen der für eine vierstellige Zahl eine irgendwie geartete Herleitung einer banalen Primfaktorzerlegung haben will. (Und im Endeffekt fällt die PFZ vom Himmel: Man sieht 11 als PF und dividiert.).

---

Ja, Kryptographie-Ferienübung ;)

---

:D danke, das mit der PFZ ist mir gestern auch klar geworden. Hab ein bisschen auf dem Schlauch gestanden ;)

---

Also wenn ich das richtig verstanden habe, muss man zuerst M' = det(M)^-1 * adj(M) mod 11 berechnen. Und danach M'' = det(M')^-1 * adj(M') mod 101?

Wie man dann mit dem chinesischen Restsatz wieder auf 1111 hochrechnet, verstehe ich nicht so wirklich. Wenn ich z.B.

x ≡ M'' mod M' berechne, also x ≡ m_1,1'' mod m_1,1', x ≡ m_1,2'' mod m_1,2' usw. bekomme ich in der Tat eine Zahl. Aber es macht irgendwie keinen Sinn. :S

---

Ich hab det(M mod 11) mod 11 und det(M mod 101) mod 101 berechnet. Mit Hilfe des chinesischen Restsatzes kannst du dann x kongruent zu det(M mod 11) mod 11 und x kongruent zu det(M mod 101) mod 101. Das ist dann deine det(M) ;)

Die adj(M) habe ich einfach mit der dazu passenden Formel berechnet und dann beides verrechnet.

---

wie du die det(M) berechnest, habe ich verstanden. Allerdings verstehe ich das mit der adj(M) noch nicht so ganz...Also du hast die adj(M mod 11) und adj(M mod 101) berechnet, und wie "verrechnest" du diese beiden dann um auf die adj(M) zu kommen?

---

Mache dir nicht mehr Arbeit als es schon ist. Ich habe es einfach wie hier https://de.wikipedia.org/wiki/Adjunkte beschrieben, berechnet.

---

Genau, so hab' ich's auch gemacht :)

---

Achso, also bezieht sich das Anwenden des Chinesischen Restsatzes nur auf die Determinante von M und die Adjunkte von M wird ganz normal mit der Formel ausgerechnet, korrekt? Danke für eure Hilfe ! :)

---

Nein es ist wohl so gedacht, dass die Matrizen mod 11 und mod 101 invertiert werden (wie auch immer; die Adjunkte ist eine algorithmisch extrem langsame Methode.) So steht es auch hier in der Antwort und nochmal explizit im 3. Kommentar.

---

Okay, dann habe ich diese beiden matrizen invertiert, und wie komm ich dann auf die inverse von M? Da habt ihr von "adjunkte verrechnen" geredet, weiss nicht so ganz was ihr damit meint.

---

Die Kommentare hier haben teilweise nichts mehr mit der Antwort zu tun, oder auch mit der Aufgabe. Mit der in der Antwort angegebenen Isomorphie kann kann man die Matrix mod 1111 berechnen, indem man das Urbild unter dem Isomorphismus der Inversen mod 11 und mod 101 berechnet.

---

Meine Frage ist: Ich habe die beiden Inversen M' und M''  zu den Matrizen M mod 11 und M mod 101 berechnet und zwar standardmäßig mit der Adjunkten. Bedeutet die ursprüngliche Antwort

 Gl(3,Z/1111Z)≅Gl(3,Z/11Z)×Gl(3,Z/101Z)

dass ich diese beiden Inversen jetzt miteinander multiplizieren muss um auf die gesuchte Inverse mod 1111 zu kommen?

---

Nein, natürlich nicht. Der Isomorphismus ist, wie geschrieben, induziert vom chin. Restsatz, d.h. hier wendet man den chin. Restsatz komponentenweise auf die Einträge der Matrix an. Und wie in den Kommentaren geschrieben, ist die Berechnung über die Adjunkte nicht die Standardmethode zur Berechnung der Inversen, da es Algorithmen gibt, die deutlich bessere laufzeiten haben, unter anderem das Verfahren das man bereits in den ersten Wochen des ersten Semesters kennenlerent: gauß-Jorden.