LGS Restklassen

02.06.2014, 15:55

Rest mit Klasse

Auf diesen Beitrag antworten »

LGS Restklassen

Wir sollen das LGS $\begin{eqnarray*} \begin{pmatrix} 1 & 2 & 1 &|0 \\ 2 & 0 & 1 &|0 \\ 3 & 1 & 1 &|0\end{pmatrix} \end{eqnarray*}$
über $\begin{eqnarray*} \mathbb Z_2 \end{eqnarray*}$ lösen. Ich tue mich allerdings ziemlich schwer damit. Ich bin nun soweit gekommen das ich die Addition für den Restklasenkörper herausbekommen habe. Also das wäre dann:

$\begin{eqnarray*} 0+0=0 \end{eqnarray*}$
$\begin{eqnarray*} 0+1=1 \end{eqnarray*}$
$\begin{eqnarray*} 1+0=0 \end{eqnarray*}$
$\begin{eqnarray*} 1+1=0 \end{eqnarray*}$

Soweit ist alles klar. Nun tauchen allerdings in dem LGS auch Zahlen auf die nicht 0 oder 1 sind. Wie gehe ich denn damit um? Ich will das Thema endlich verstehen ...

02.06.2014, 16:03

RavenOnJ

Auf diesen Beitrag antworten »

RE: LGS Restklassen
Inwiefern gehören 2 und 3 zu $\begin{eqnarray*} \mathbb Z_2 \end{eqnarray*}$ ?

02.06.2014, 16:08

Rest mit Klasse

Auf diesen Beitrag antworten »

RE: LGS Restklassen
Ja also die Addition für 2 und 3 taucht in meiner Additionstabelle ja nicht auf. Eventuell dann einfach Null? Irgendwie muss es ja definiert sein wenn man mit einer größeren oder kleineren Zahl als 0 oder 1 rechnet ... verwirrt

verwirrt

02.06.2014, 16:12

RavenOnJ

Auf diesen Beitrag antworten »

RE: LGS Restklassen
Die Koeffizienten der Matrix müssen zum selben Körper gehören. Man könnte das allerdings auch als Modulorechnung verstehen, dann wäre 2=0 und 3=1.

02.06.2014, 16:20

Rest mit Klasse

Auf diesen Beitrag antworten »

RE: LGS Restklassen
So ganz hilft mir das jetzt auch noch nicht weiter. Wenn ich jetzt zum Beispiel die erste Zeile minus der dritten Zeile rechnen möchte wäre das ja:

$\begin{eqnarray*} \begin{pmatrix} (1-3) & (2-1) & (1-1) &|0 \\ 2 & 0 & 1 &|0 \\ 3 & 1 & 1 &|0 \end{pmatrix} \end{eqnarray*}$

Dann subtrahiert: $\begin{eqnarray*} \begin{pmatrix} -2 & 1 & 0 &|0 \\ 2 & 0 & 1 &|0 \\ 3 & 1 & 1 &|0 \end{pmatrix} \end{eqnarray*}$

Die erste Zeile muss jetzt aber doch noch anders dargestellt werden da z.B. die $\begin{eqnarray*} -2 \end{eqnarray*}$ garnicht in $\begin{eqnarray*} \mathbb Z_2 \end{eqnarray*}$ liegt. Wie mache ich das denn?

02.06.2014, 16:22

RavenOnJ

Auf diesen Beitrag antworten »

RE: LGS Restklassen
Wandle doch erst mal in der Matrix 2 in 0 um und 3 in 1. Dann wird es ganz einfach.

Anzeige

02.06.2014, 16:27

Rest mit Klasse

Auf diesen Beitrag antworten »

RE: LGS Restklassen
Ok, also das ist ja das ursprüngliche LGS: $\begin{eqnarray*} \begin{pmatrix} 1 & 2 & 1 &|0 \\ 2 & 0 & 1 &|0 \\ 3 & 1 & 1 &|0\end{pmatrix} \end{eqnarray*}$

Wenn ich nun 2 in 0 und 3 in 1 umwandle erhalte ich: $\begin{eqnarray*} \begin{pmatrix} 1 & 0 & 1 &|0 \\ 0 & 0 & 1 &|0 \\ 1 & 1 & 1 &|0\end{pmatrix} \end{eqnarray*}$

Kannst du mir denn noch erklären wie du darauf kommst die 2 in 0 und die 3 in 1 umzuwandeln? Wie lautet denn da die Regel? Schließlich sind doch nur die $\begin{eqnarray*} 0,1 \end{eqnarray*}$ in $\begin{eqnarray*} \mathbb Z_2 \end{eqnarray*}$ enthalten.

02.06.2014, 16:32

RavenOnJ

Auf diesen Beitrag antworten »

RE: LGS Restklassen
Der Körper $\begin{eqnarray*} \mathbb Z_2 \end{eqnarray*}$ hat Charakteristik 2, d.h. 2*1 := 1+1=0. Also wird 3*1 := 1+1+1 = 0+1 = 1, wenn man denn unbedingt Multiplikationen mit Zahlen nicht aus {0,1} zulassen will. Alles andere würde keinen Sinn machen.

02.06.2014, 16:42

Rest mit Klasse

Auf diesen Beitrag antworten »

RE: LGS Restklassen
Ah, interessant. Langsam tut sich ja eine Regel auf. Also dann wäre z.B. $\begin{eqnarray*} 4 \end{eqnarray*}$ in $\begin{eqnarray*} \mathbb Z_2 \end{eqnarray*}$ eben $\begin{eqnarray*} 4=(1+1)+(1+1)=0+0=0 \end{eqnarray*}$ für 5 dann analog $\begin{eqnarray*} 5=(1+1)+(1+1)+1=0+0+1=1 \end{eqnarray*}$ So richtig?

Wie würde es sich denn bei negativen Zahlen verhalten? Also z.b. $\begin{eqnarray*} -3 \end{eqnarray*}$ ? Das wäre dann ja $\begin{eqnarray*} -3=-((1+1)+1)=-((0)+1)=-(1)=-1 \end{eqnarray*}$ oder wie? smile

smile

02.06.2014, 16:45

RavenOnJ

Auf diesen Beitrag antworten »

RE: LGS Restklassen
-3 = 1-4 = 1-(1+1+1+1) = 1-0 = 1
Eine -1 gibt es nicht in {0,1}.

02.06.2014, 16:51

Rest mit Klasse

Auf diesen Beitrag antworten »

RE: LGS Restklassen
Sehr geil! Du bist ein Gott! Gott

Gott

Bevor ich jetzt das LGS löse habe ich noch eine Frage. Muss ich nach jeder Zeilenumformung das LGS anpassen (wegen $\begin{eqnarray*} \mathbb Z_2 \end{eqnarray*}$ ) oder kann ich das LGS auch ganz normal lösen als ob ich in $\begin{eqnarray*} \mathbb R \end{eqnarray*}$ rechnen würde und mein Ergebnis anschließend nur in $\begin{eqnarray*} \mathbb Z_2 \end{eqnarray*}$ umrechnen? Das wäre zumindest einfacher ...

02.06.2014, 18:14

Rest mit Klasse

Auf diesen Beitrag antworten »

RE: LGS Restklassen
Ich habe das LGS jetzt ganz gelöst. Nun habe ich allerdings noch eine Aufgabe. Ich soll die Inverse Matrix der Matrix $\begin{eqnarray*} A=\begin{pmatrix} 1 & 2 & 1 \\ 2 & 0 & 1 \\ 3 & 1 & 1\end{pmatrix} \end{eqnarray*}$ über $\begin{eqnarray*} \mathbb Z_3 \end{eqnarray*}$ bestimmen.

Dazu habe ich erst einmal geschaut ob die Matrix über $\begin{eqnarray*} \mathbb Z_3 \end{eqnarray*}$ überhaupt invertierbar ist.

Dazu habe ich geschaut ob die Spaltenvektoren linear unabhängig sind. Dann muss man ja folgendes LGS lösen.

$\begin{eqnarray*} \begin{pmatrix} 1 & 2 & 1 &|0 \\ 2 & 0 & 1 &|0 \\ 3 & 1 & 1 &|0\end{pmatrix} \end{eqnarray*}$

Nach nur wenigen Umformungen bin ich auf das LGS $\begin{eqnarray*} \begin{pmatrix} 1 & 2 & 0 &|0 \\ 0 & 1 & 1 &|0 \\ 0 & 0 & 0 &|0\end{pmatrix} \end{eqnarray*}$ gestoßen. Darauß kann man ja folgern dass das LGS unendlich viele Lösungen besitzt da der $\begin{eqnarray*} Rang(A)=2=Rang(A|b) \end{eqnarray*}$ erst einmal gilt und $\begin{eqnarray*} Rang(A)<Spalten(A) \end{eqnarray*}$ demnach unendlich viele Lösungen.

Nun muss ja für lineare unabhängigkeit gelten das es nur die triviale Lösung gibt. Wie verarbeite ich das denn jetzt?

02.06.2014, 19:05

RavenOnJ

Auf diesen Beitrag antworten »

RE: LGS Restklassen

Zitat:

Original von Rest mit Klasse
Bevor ich jetzt das LGS löse habe ich noch eine Frage. Muss ich nach jeder Zeilenumformung das LGS anpassen (wegen $\begin{eqnarray*} \mathbb Z_2 \end{eqnarray*}$ ) oder kann ich das LGS auch ganz normal lösen als ob ich in $\begin{eqnarray*} \mathbb R \end{eqnarray*}$ rechnen würde und mein Ergebnis anschließend nur in $\begin{eqnarray*} \mathbb Z_2 \end{eqnarray*}$ umrechnen? Das wäre zumindest einfacher ...

Das Problem ist, dass das Gleichungssystem über $\begin{eqnarray*} \mathbb R \end{eqnarray*}$ eine Lösung haben kann, über $\begin{eqnarray*} \mathbb Z_3 \end{eqnarray*}$ aber nicht. Beispielsweise

$\begin{align*} 2x&+y=1\\x&+2y=0 \end{align*}$

hat über $\begin{eqnarray*} \mathbb R \end{eqnarray*}$ die Lösung $\begin{eqnarray*} x=2/3,y=-1/3 \end{eqnarray*}$ über $\begin{eqnarray*} \mathbb Z_3 \end{eqnarray*}$ aber keine Lösung. Über $\begin{eqnarray*} \mathbb Z_2 \end{eqnarray*}$ hat es die Lösung $\begin{eqnarray*} x=0,y=1 \end{eqnarray*}$ .

02.06.2014, 19:12

RavenOnJ

Auf diesen Beitrag antworten »

RE: LGS Restklassen

Zitat:

Original von Rest mit Klasse
Ich habe das LGS jetzt ganz gelöst. Nun habe ich allerdings noch eine Aufgabe. Ich soll die Inverse Matrix der Matrix $\begin{eqnarray*} A=\begin{pmatrix} 1 & 2 & 1 \\ 2 & 0 & 1 \\ 3 & 1 & 1\end{pmatrix} \end{eqnarray*}$ über $\begin{eqnarray*} \mathbb Z_3 \end{eqnarray*}$ bestimmen.

Dazu habe ich erst einmal geschaut ob die Matrix über $\begin{eqnarray*} \mathbb Z_3 \end{eqnarray*}$ überhaupt invertierbar ist.

Dazu habe ich geschaut ob die Spaltenvektoren linear unabhängig sind. Dann muss man ja folgendes LGS lösen.

$\begin{eqnarray*} \begin{pmatrix} 1 & 2 & 1 &|0 \\ 2 & 0 & 1 &|0 \\ 3 & 1 & 1 &|0\end{pmatrix} \end{eqnarray*}$

Nach nur wenigen Umformungen bin ich auf das LGS $\begin{eqnarray*} \begin{pmatrix} 1 & 2 & 0 &|0 \\ 0 & 1 & 1 &|0 \\ 0 & 0 & 0 &|0\end{pmatrix} \end{eqnarray*}$ gestoßen. Darauß kann man ja folgern dass das LGS unendlich viele Lösungen besitzt da der $\begin{eqnarray*} Rang(A)=2=Rang(A|b) \end{eqnarray*}$ erst einmal gilt und $\begin{eqnarray*} Rang(A)<Spalten(A) \end{eqnarray*}$ demnach unendlich viele Lösungen.

Nun muss ja für lineare unabhängigkeit gelten das es nur die triviale Lösung gibt. Wie verarbeite ich das denn jetzt?

Die Koeffizientenmatrix hat nicht den vollen Rang, also ist sie nicht invertierbar. Wäre sie invertierbar, müsste sie Rang=3 haben.

02.06.2014, 19:51

Rest mit Klasse

Auf diesen Beitrag antworten »

RE: LGS Restklassen
Ich dachte wenn $\begin{eqnarray*} Rang(A)=Rang(A|b) \end{eqnarray*}$ gilt ist das LGS lösbar. Wenn $\begin{eqnarray*} Rang(A)<Spalten(A) \end{eqnarray*}$ gilt besitzt das LGS unendlich viele Lösungen? Oder bezieht es sich lediglich auf die Invertierbarkeit das ein LGS mit unendlich vielen Lösungen nicht invertierbar ist da es mehr Lösungen als die triviale besitzt?

02.06.2014, 20:21

RavenOnJ

Auf diesen Beitrag antworten »

RE: LGS Restklassen

Zitat:

Original von Rest mit Klasse
Ich dachte wenn $\begin{eqnarray*} Rang(A)=Rang(A|b) \end{eqnarray*}$ gilt ist das LGS lösbar. Wenn $\begin{eqnarray*} Rang(A)<Spalten(A) \end{eqnarray*}$ gilt besitzt das LGS unendlich viele Lösungen? Oder bezieht es sich lediglich auf die Invertierbarkeit das ein LGS mit unendlich vielen Lösungen nicht invertierbar ist da es mehr Lösungen als die triviale besitzt?

Du wirfst da zwei Sachen durcheinander. Wenn es um die Lösbarkeit eines linearen Gleichungssystems geht, hast du recht mit dem von dir angegebenen Kriterium: der Rang der Koeffizientenmatrix muss gleich dem Rang der erweiterten Koeffizientenmatrix sein. In deiner Aufgabe ging es aber um die Invertierbarkeit der Matrix A. Hierzu ist notwendig, dass die Matrix A vollen Rang hat bzw. der Kern der durch die Matrix vermittelten Abbildung trivial ist.

Dies ist relativ einfach einzusehen: Wenn es Vektoren ungleich 0 gibt, die durch die Matrix auf die 0 abgebildet werden, dann können diese Vektoren nicht zum Bildraum der inversen Abbildung gehören (falls sie existiert). Formal:
Wenn gilt

$\begin{eqnarray*} Ax=0\text{ mit } x \not=0, x\in V \end{eqnarray*}$

dann würde es wegen der Linearität der Abbildung einen Vektor y geben mit

$\begin{eqnarray*} Ay=A(y+x) = z\text{ mit } x,y,z\in V \end{eqnarray*}$

Die inverse Abbildung von $\begin{eqnarray*} z \end{eqnarray*}$ könnte also nicht eindeutig sein, d.h.

$\begin{eqnarray*} \nexists B = A^{-1}: Bz=y \land Bz=y+x \end{eqnarray*}$

02.06.2014, 20:37

Rest mit Klasse

Auf diesen Beitrag antworten »

RE: LGS Restklassen
Ich bedanke mich vielmals, endlich habe ich das Rechnen mit Restklassen verstanden. Ich kann dir nicht sagen wie sehr mich das belastet hat obwohl es doch so einfach ist - wenn man es einmal erklärt bekommt.

Bis Bald! smile

smile

1

Verwandte Themen

Die Beliebtesten »

Die Größten »

Die Neuesten »