lineares Gleichungssystem - Smith-Normalform - ggT?

Question

Hallo!

Ich habe gerade Schwierigkeiten beim Lösen eines linearen diophantischen Gleichungssystems mit der Smith-Normalform. Die Berechnung der SNF ist gar kein Problem. Aber irgendwie wendet man den ggT und den euklidischen Algorithmus an. Ich verstehe aber nicht warum.

Wenn ich beispielsweise folgende Matrix A habe:

$\begin{pmatrix} 8 & 3 \\ 7 & 2 \end{pmatrix}$

Dann würde ich intuitiv folgende Eliminationsschritte durchführen:

- Tauschen von 1. und 2.Spalte:

$\begin{pmatrix} 3 & 8 \\ 2 & 7 \end{pmatrix}$

- 2. Zeile von 1. abziehen:

$\begin{pmatrix} 1 & 1 \\ 2 & 7 \end{pmatrix}$

- Zeilen: 2*II-I:

$\begin{pmatrix} 1 & 1 \\ 0 & 5 \end{pmatrix}$

- Spalten: II-I:

$\begin{pmatrix} 1 & 0 \\ 0 & 5 \end{pmatrix}$ = SNF(A), wobei 1|5

Aber ich habe nirgends den euklidischen Algorithmus oder den ggT berechnet. Zumindest nicht aktiv.

Wo kommt der zum Einsatz und wozu ist der gut?

Comments

Welches GS wolltest du den lösen?

lul

---

Welches GS wolltest du den lösen?

Ich habe kein explizites, die Matrix hier ist ausgedacht.

Sei es hier: 8x+3y=52

                 7x+2y=43 , wobei x und y beide aus ℤ sind.

Das lösen der Gleichung fällt mir wie gesagt nicht schwer. Mir gehts explizit um die Frage mit dem ggT bzw. dem eukl. Algorithmus.

Answer 1

Hm

dazu mußt Du vielleicht ein echtes linear_diophantine_eqs betrachten. Wenn Dein LGS schon eine eindeutige ganzzahlige Lösung hat ergibt eine Smith-Form nicht so richtig Sinn?

Die SNF soll ja die ganzzahligen Teiler in absteigender Reihenfolge in der Diagonalen darstellen, dazu beginnt man mit den betragmäßig kleinsten Element auf a₁₁ und wenn man nur ganzzahlige Zeilen/Spaltenoperationen anwendet bleiben die dann auch übrig.

Ich hab irgendwo eine Rechnung zur Smithnormalform über ℤ_3x3 in GeoGebra CAS.

Wenn DU das lesen kannst/willst lade ich es Dir gerne hoch, wenn ich es noch finde - gib Rückmeldung dann schaun mer mal...

Comments

Ich würde sehr gerne die Geogebra Datei sehen, das wäre bestimmt sehr hilfreich!

Die SNF ist ja eindeutig bestimmt. Ich habe ja scheinbar eine falsch (?). Wäre die Lösungmenge am Ende dann falsch?

---

So, ich habs gefunden

https://www.geogebra.org/m/ebesuket

Die App ist nicht ausgearbeitet und "kann" nur ℤ_2x3 ohne Eingriff in den Algorithmus.

Deine Aufgabe

$\small D \, := \, \left(\begin{array}{rr}1&0\\0&5\\\end{array}\right)$ Smith-Normalform

$\small P \, := \, \left(\begin{array}{rr}1&-1\\-2&3\\\end{array}\right)$

$\small Q \, := \, \left(\begin{array}{rr}0&1\\1&-1\\\end{array}\right)$

$\small {P\; A\; Q = D \to \quad A = P^{-1} D\, Q^{-1} \to \quad \textcolor{blue}{ P^{-1} D } \textcolor{red}{\, Q^{-1} x _{=y}} = \textcolor{blue}{ b}}$

$\small \textcolor{red}{Q^{-1}\, x = y \to \quad x = Q\, y} \quad ∧ \quad \textcolor{blue}{P^{-1} \cdot D\, y = b \to \quad D\; y = P\, b}$

$\small \textcolor{blue}{\left(\begin{array}{rr}1&0\\0&5\\ \end{array}\right)\cdot y =\left(\begin{array}{rr}1&-1\\-2&3\\ \end{array}\right)\cdot\left(\begin{array}{r}52\\43\\ \end{array}\right)}$

$\small{\left(\begin{array}{r}y_1 \\5\, y_2\\ \end{array}\right)}={\left(\begin{array}{r}9 \\ 25 \\ \end{array}\right)} \to \quad \left(\begin{array}{r}y_1\\y_2\\\end{array}\right)=\left(\begin{array}{r}9\\5\\\end{array}\right)$

$\small \textcolor{red}{ x = Q\, y }$

$\small x = \left(\begin{array}{rr}0&1\\1&-1\\\end{array}\right) \cdot \left(\begin{array}{r}9\\5\\\end{array}\right)$

$L_{ℤ} \, :\left\{ \left(\begin{array}{r}x\\y\\\end{array}\right)= \, \left(\begin{array}{r}5\\4\\\end{array}\right)\right\}$

Wie gesagt nicht so sinnvoll, weil

$\small RRef=\left(\begin{array}{rrr}1&0&5\\0&1&4\\\end{array}\right)$

oder es geht nur darum mit der Smith-NF zu arbeiten?

Answer 2

Hallo

ggT brauchst du von 3 und 8  er muss 52 teilen damit die Gleichung lösbar ist. Ich denke nicht dass dabei das reduzieren der Gleichung davor viel Sinn macht. um die Diophantische Gleichung zu lösen , wenigstens musst du die rechte Seite mit behandeln,

den ggT von a,b kannst du immer durch  k*a+l*b=ggT erzeugen und damit Vielfache davon , k,l aus ℤ

Gruß lul