Matroids Matheplanet Forum Index
Moderiert von Fabi Dune ligning
Lineare Algebra » Matrizenrechnung » Beweis zu Satz über lineare Gleichungssysteme
Druckversion
Druckversion
Autor
Universität/Hochschule J Beweis zu Satz über lineare Gleichungssysteme
X3nion
Aktiv Letzter Besuch: in der letzten Woche
Dabei seit: 17.04.2014
Mitteilungen: 766
Zum letzten BeitragZum nächsten BeitragZum vorigen BeitragZum erstem Beitrag  Themenstart: 2020-07-11


Hallo zusammen!

Ich verstehe etwas nicht beim Beweis des folgenden Satzes:

Sei (L) ein lineares Gleichungssystem in Zeilenstufenform.
Dann besitzt (L) genau dann eine Lösung, wenn (L) keine Zeile der Form $0=b^i$ mit $b^i\neq0$ enthält.
Die Lösung ist eindeutig, falls eine Lösung existiert, $N(i)=i-1$ für $1\le i\le m$ mit $N(i)$ wie in Definition der Zeilenstufenform und $n=m$ gelten.
Dabei ist \[N(i):=\max\left\{k\in\{0,1,\ldots,n+1\}\colon A^i_j=0\text{ für }1\le j\le k\right\}\] definiert und wir fordern, dass es ein $i_0\in\{0,\ldots,m-1\}$ gibt, so dass $N(i)<N(i+1)$ für alle
$1\le i\le i_0$ und $N(i)=n+1$ für $i_0<i\le m$ gelten.


Beweis:

Damit (L) eine Lösung besitzt, darf keine Zeile der Form
$0\neq0$ auftreten. Nehme dies an. Dann hat die letzte Zeile, die
nicht die Form $0=0$ hat, die Form
\[a^i_kx^k+\ldots+a^i_nx^n=b^i\] mit $a^i_k\neq0$.
Wähle $\xi^{k+1},\ldots,\xi^n$ beliebig und setze
\[\xi^k:=\frac1{a^i_k}\left(b^i-\left(a^i_{k+1}\xi^{k+1}
+\ldots+a^i_n\xi^n\right)\right).\] $(\xi^k,\ldots,\xi^n)$ löst diese letzte Gleichung. Ersetze nun $x^k,\ldots,x^n$ im restlichen Gleichungssystem durch $\xi^k,\ldots,\xi^n$.
Dieses Gleichungssystem hat nun eine Gleichung weniger als das bisher
betrachtete. Per Induktion finden wir daher eine Lösung.

- - - - - - - - - -


Wieso folgt die Behauptung per Induktion?
Kann mir jemand erklären, wieso und auf welche Weise hier induktiv bewiesen wird? Und was ist die Induktionsvoraussetzung und -behauptung?

Ich wäre euch wie immer sehr dankbar für eure Hilfe!

Viele Grüße,
X3nion



Eine Notiz zu diese Forumbeitrag schreiben Notiz   Profil  Quote  Link auf diesen Beitrag Link
Diophant
Senior Letzter Besuch: in der letzten Woche
Dabei seit: 18.01.2019
Mitteilungen: 4418
Aus: Rosenfeld, BW
Zum letzten BeitragZum nächsten BeitragZum vorigen BeitragZum erstem Beitrag  Beitrag No.1, eingetragen 2020-07-11

\(\begingroup\)\(\newcommand{\ba}{\begin{aligned}} \newcommand{\ea}{\end{aligned}} \newcommand{\bpm}{\begin{pmatrix}} \newcommand{\epm}{\end{pmatrix}} \newcommand{\bc}{\begin{cases}} \newcommand{\ec}{\end{cases}} \newcommand{\on}{\operatorname}\)
Hallo X3nion,

ich glaube, an diesem Beweis ist eigentlich eher die sperrige Notation schwierig als die Vorgehensweise. Was da gemacht wird ist doch letztendlich nichts anderes als was du beim praktischen Lösen eines LGS in Zeilenstufenform auch machst:

- Parameter für so viele Variablen wählen, wie es der Rang der Koeffizientenmatrix erfordert (für den Fall einer eindeutigen Lösung gibt es einfach keine Parameter).
- in der untersten von Null verschiedenenn Zeile die Variable \(x^k\) durch Einsetzen mit Hilfe dieser Parameter darstellen
- sukzessive von unten nach oben mit jeder weiteren Gleichung eine weitere Unbekannte mit Hilfe der gewählten Parameter ausdrücken.

Die Induktion läuft hier als im Prinzip von der untersten von Null verschiedenen Zeile bis zur ersten Zeile.

Der Induktionsanfang ist formal gesehen die Lösung für \(x^k\), die Induktionsannahme die Lösung die aus einer beliebigen Zeile resultiert und der Induktionsschluss im Prinzip die Rechnung, die durch Einsetzen einer Lösung die nächste Lösung eine Zeile darüber liefert.

Die Verwendung des Begriffs Induktion ist hier IMO auch ziemlich oversized. Sukzessive hätte es wohl auch getan...

Wie gesagt: das ist inhaltlich total simpel, nur sehr hoplrig zu lesen.


Gruß, Diophant
\(\endgroup\)


Eine Notiz zu diese Forumbeitrag schreiben Notiz   Profil  Quote  Link auf diesen Beitrag Link
X3nion
Aktiv Letzter Besuch: in der letzten Woche
Dabei seit: 17.04.2014
Mitteilungen: 766
Zum letzten BeitragZum nächsten BeitragZum vorigen BeitragZum erstem Beitrag  Beitrag No.2, vom Themenstarter, eingetragen 2020-07-11


Hi Diophant und Danke für deinen Beitrag!

Okay, dann ist das für mich klar.

Jetzt gibt es noch ein Korollar davon:

Sei (H) ein homogenes lineares Gleichungssystem mit weniger Zeilen als Variablen. (m Zeilen, n Spalten, also m < n)
Dann besitzt (H) eine nichttriviale Lösung, d.h. eine Lösung

  $(\xi^1,\ldots,\xi^n)\neq(0,\ldots,0)$.

Beweis:

Wir bringen das Gleichungssystem in Zeilenstufenform. Wegen $m<n$ gibt es ein $i<m$ mit $N(i) +2 \le N(i+1)$ und $N(i)+2\le n$ oder es ist $N(m)\le n-2$.
Lösen wir das Gleichungssystem also wie in obigem Lemma, so ist $\xi^{N(i)+2}$ bzw. $\xi^n$ frei wählbar.

- - - - - - - - - -


Hier verstehe ich zwei Sachen nicht:

Wegen $m<n$ gibt es ein $i<m$ mit $N(i) +2 \le N(i+1)$

Wieso gilt das allgemein? Kann man das irgendwie beweisen?
Ist es so, dass aufgrund $m < n$ wegen der Zeilenstufenform mindestens eine "doppelte Stufe" vorkommen muss?



Lösen wir das Gleichungssystem also wie in obigem Lemma, so ist $\xi^{N(i)+2}$ bzw. $\xi^n$ frei wählbar.

Wieso sind gerade diese beiden Variablen dann frei wählbar?

VG X3nion



Eine Notiz zu diese Forumbeitrag schreiben Notiz   Profil  Quote  Link auf diesen Beitrag Link
Diophant
Senior Letzter Besuch: in der letzten Woche
Dabei seit: 18.01.2019
Mitteilungen: 4418
Aus: Rosenfeld, BW
Zum letzten BeitragZum nächsten BeitragZum vorigen BeitragZum erstem Beitrag  Beitrag No.3, eingetragen 2020-07-12

\(\begingroup\)\(\newcommand{\ba}{\begin{aligned}} \newcommand{\ea}{\end{aligned}} \newcommand{\bpm}{\begin{pmatrix}} \newcommand{\epm}{\end{pmatrix}} \newcommand{\bc}{\begin{cases}} \newcommand{\ec}{\end{cases}} \newcommand{\on}{\operatorname}\)
Hallo X3nion,

was ist das denn für eine Quelle?

Um ehrlich zu sein, das hier:

2020-07-11 20:49 - X3nion in Beitrag No. 2 schreibt:
Wegen $m<n$ gibt es ein $i<m$ mit $N(i) +2 \le N(i+1)$

verstehe ich ebensowenig wie du und halte es schlichtweg für falsch. Vorausgesetzt, ich deute das Symbol \(N(i)\) als Anzahl der führenden Nullen der i. Zeile korrekt?


Gruß, Diophant
\(\endgroup\)


Eine Notiz zu diese Forumbeitrag schreiben Notiz   Profil  Quote  Link auf diesen Beitrag Link
zippy
Senior Letzter Besuch: in der letzten Woche
Dabei seit: 24.10.2018
Mitteilungen: 1343
Zum letzten BeitragZum nächsten BeitragZum vorigen BeitragZum erstem Beitrag  Beitrag No.4, eingetragen 2020-07-12

\(\begingroup\)\(\newcommand{\ba}{\begin{aligned}} \newcommand{\ea}{\end{aligned}} \newcommand{\bpm}{\begin{pmatrix}} \newcommand{\epm}{\end{pmatrix}} \newcommand{\bc}{\begin{cases}} \newcommand{\ec}{\end{cases}} \newcommand{\on}{\operatorname}\)
2020-07-12 10:11 - Diophant in Beitrag No. 3 schreibt:
Um ehrlich zu sein, das hier:

2020-07-11 20:49 - X3nion in Beitrag No. 2 schreibt:
Wegen $m<n$ gibt es ein $i<m$ mit $N(i) +2 \le N(i+1)$

verstehe ich ebensowenig wie du und halte es schlichtweg für falsch.

Dieses Zitat gibt nicht den vollständigen Satz wieder, der geht noch weiter:

2020-07-11 20:49 - X3nion in Beitrag No. 2 schreibt:
Wegen $m<n$ gibt es ein $i<m$ mit $N(i) +2 \le N(i+1)$ und $N(i)+2\le n$  oder  es ist $N(m)\le n-2$.

Die Aussage ist einfach, dass irgendwo eine komplette Nullspalte vorliegt, weil mindestens eine der beiden folgenden Situationen auftreten muss:
1. Es gibt eine Zeile, die mindestens 2 links stehenden Nullen mehr enthält als ihr Vorgänger.
2. In der letzten Zeile steht an Position $n$ eine $0$.

Zu beachten ist, dass die 1. Situation auch den Fall $N(1)>0$ einschließt. Man muss also mit $N(0)=-1$ arbeiten.

--zippy
\(\endgroup\)


Eine Notiz zu diese Forumbeitrag schreiben Notiz   Profil  Quote  Link auf diesen Beitrag Link
Diophant
Senior Letzter Besuch: in der letzten Woche
Dabei seit: 18.01.2019
Mitteilungen: 4418
Aus: Rosenfeld, BW
Zum letzten BeitragZum nächsten BeitragZum vorigen BeitragZum erstem Beitrag  Beitrag No.5, eingetragen 2020-07-12

\(\begingroup\)\(\newcommand{\ba}{\begin{aligned}} \newcommand{\ea}{\end{aligned}} \newcommand{\bpm}{\begin{pmatrix}} \newcommand{\epm}{\end{pmatrix}} \newcommand{\bc}{\begin{cases}} \newcommand{\ec}{\end{cases}} \newcommand{\on}{\operatorname} \newcommand{\ds}{\displaystyle}\)
Hallo zippy,

2020-07-12 11:35 - zippy in Beitrag No. 4 schreibt:
Dieses Zitat gibt nicht den vollständigen Satz wieder, der geht noch weiter:

2020-07-11 20:49 - X3nion in Beitrag No. 2 schreibt:
Wegen $m<n$ gibt es ein $i<m$ mit $N(i) +2 \le N(i+1)$ und $N(i)+2\le n$ oder es ist $N(m)\le n-2$.


Ok, das hatte ich in der Tat überlesen. Damit ist mir der Sinn dieser Aussage klar: wenn man in der untersten Zeile nur noch einen von Null verschiedenen Eintrag hat, dann muss es weiter oben Zeilen geben, bei denen die Anzahl der führenden Nullen um mehr als 1 zunimmt im Vergleich zur Zeile darüber. Oder man hat in der letzten Zeile eben noch mehr als einen von Null verschiedenen Eintrag bzw. "mehr als eine Variable übrig".

2020-07-12 11:35 - zippy in Beitrag No. 4 schreibt:
Die Aussage ist einfach, dass irgendwo eine komplette Nullspalte vorliegt, weil mindestens eine der beiden folgenden Situationen auftreten muss:
1. Es gibt eine Zeile, die mindestens 2 links stehenden Nullen mehr enthält als ihr Vorgänger.
2. In der letzten Zeile steht an Position $n$ eine $0$.

Das verstehe ich ehrlich gesagt nicht. Könntest du das noch erläutern? Also warum muss es in der Situation \(m<n\) Nullspalten oder Nullzeilen geben?

@X3nion:
Ist dir die Bedeutung des Beweisanfangs aus #2 damit dann schon klar geworden?


Gruß, Diophant
\(\endgroup\)


Eine Notiz zu diese Forumbeitrag schreiben Notiz   Profil  Quote  Link auf diesen Beitrag Link
zippy
Senior Letzter Besuch: in der letzten Woche
Dabei seit: 24.10.2018
Mitteilungen: 1343
Zum letzten BeitragZum nächsten BeitragZum vorigen BeitragZum erstem Beitrag  Beitrag No.6, eingetragen 2020-07-12

\(\begingroup\)\(\newcommand{\ba}{\begin{aligned}} \newcommand{\ea}{\end{aligned}} \newcommand{\bpm}{\begin{pmatrix}} \newcommand{\epm}{\end{pmatrix}} \newcommand{\bc}{\begin{cases}} \newcommand{\ec}{\end{cases}} \newcommand{\on}{\operatorname} \newcommand{\ba}{\begin{aligned}} \newcommand{\ea}{\end{aligned}} \newcommand{\bpm}{\begin{pmatrix}} \newcommand{\epm}{\end{pmatrix}} \newcommand{\bc}{\begin{cases}} \newcommand{\ec}{\end{cases}} \newcommand{\on}{\operatorname}\)
2020-07-12 12:03 - Diophant in Beitrag No. 5 schreibt:
Also warum muss es in der Situation \(m<n\) Nullspalten oder Nullzeilen geben?

Mit "Nullspalte" habe den falschen Begriff benutzt. Ich meine eine Spalte, in der "an der entscheidenden Stelle keine $1$ steht".
\(\endgroup\)


Eine Notiz zu diese Forumbeitrag schreiben Notiz   Profil  Quote  Link auf diesen Beitrag Link
X3nion
Aktiv Letzter Besuch: in der letzten Woche
Dabei seit: 17.04.2014
Mitteilungen: 766
Zum letzten BeitragZum nächsten BeitragZum vorigen BeitragZum erstem Beitrag  Beitrag No.7, vom Themenstarter, eingetragen 2020-07-12


Hallo zusammen!

Also ich kann mir nun allgemein das Szenario

Wir bringen das Gleichungssystem in Zeilenstufenform. Wegen $m<n$ gibt es ein $i<m$ mit $N(i) +2 \le N(i+1)$ und $N(i)+2\le n$ oder es ist $N(m)\le n-2$.

Haben wir nur ganz normale Stufen der Länge 1, so wiederholen wir diesen Schritt m-1 mal, bis wir in der m-ten Zeile sind und um m-1 Spalten nach rechts weitergerückt sind. Dann ist die erste Bedingung nicht erfüllt, die zweite aber auf jeden Fall, denn es gilt $N_{m} + 2 = m-1 + 2 = m+1 \le n$, denn aus $m < n$ folgt $m+1 \le n$.
Haben wir irgendwo mindestens eine Stufe der Länge 2, so muss die zweite Bedingung nicht mehr eintreten, wenn n nicht hinreichend groß ist, aber dafür tritt ja die erste Bedingung ein.
Also zum Beispiel wäre im Falle, dass m = n-1 ist, und wir nur eine Stufe der Länge 2 haben in einer Zeile ungleich der letzten Zeile, sonst nur Stufen der Länge 1, dann $N_{m} + 2 = m + 2 = \le n$ nicht mehr erfüllt

Was ich nun noch nicht verstehe: Wieso ist $\xi^{N(i)+2}$ bzw. $\xi^n$ frei wählbar, wenn man das Gleichungssystem wie in obigem Lemma löst?

VG X3nion



Eine Notiz zu diese Forumbeitrag schreiben Notiz   Profil  Quote  Link auf diesen Beitrag Link
Diophant
Senior Letzter Besuch: in der letzten Woche
Dabei seit: 18.01.2019
Mitteilungen: 4418
Aus: Rosenfeld, BW
Zum letzten BeitragZum nächsten BeitragZum vorigen BeitragZum erstem Beitrag  Beitrag No.8, eingetragen 2020-07-12

\(\begingroup\)\(\newcommand{\ba}{\begin{aligned}} \newcommand{\ea}{\end{aligned}} \newcommand{\bpm}{\begin{pmatrix}} \newcommand{\epm}{\end{pmatrix}} \newcommand{\bc}{\begin{cases}} \newcommand{\ec}{\end{cases}} \newcommand{\on}{\operatorname} \newcommand{\ds}{\displaystyle}\)
Hallo X3nion,

auch hier solltest du dich abseits der ganzen Formalismen an dem orientieren, was die inhaltliche Bedeutung des ganzen ist.

Wenn \(N(m)\le m-2\) gilt, dann heißt das auf deutsch: in der letzten Zeile steht noch mehr als eine Variable. In einer linearen Gleichung mit mehreren Variablen kann man immer alle Variablen bis auf eine frei wählen. Insbesondere also etwa \(x^n=\xi^n\).

Wenn andererseits für ein i die Bedingung \(N(i)+2\le N(i+1)\) gilt, dann kommt von der i. zur i+1. Zeile mehr als eine Null hinzu. Heißt: in der Gleichung, für die die i. Zeile steht, kann man etwa die Belegung der Variablen \(x^{N(i)+2}\) mit \(x^{N(i)+2}=\xi^{N(i)+2}\) frei wählen.

Wichtig ist doch nur die Tatsache, dass man in beiden Fällen eine Variable frei wählen kann. Damit ist das Korollar gezeigt, nämlich dass ein solches homogenes LGS mit \(m<n\) Zeilen nichttriviale Lösungen besitzt.

Und wie wir wissen sind das unendlich viele Lösungen*. Aber so genau möchte man es eben an dieser Stelle noch gar nicht wissen (um mal ein kleines Wortspiel rauszuhauen).

* EDIT: natürlich nur über einem unendlichen Körper.


Gruß, Diophant
\(\endgroup\)


Eine Notiz zu diese Forumbeitrag schreiben Notiz   Profil  Quote  Link auf diesen Beitrag Link
zippy
Senior Letzter Besuch: in der letzten Woche
Dabei seit: 24.10.2018
Mitteilungen: 1343
Zum letzten BeitragZum nächsten BeitragZum vorigen BeitragZum erstem Beitrag  Beitrag No.9, eingetragen 2020-07-12


2020-07-12 14:49 - Diophant in Beitrag No. 8 schreibt:
Und wie wir wissen sind das unendlich viele Lösungen.

Nicht notwendigerweise. Du scheinst nur an unendliche Körper zu denken.

(Das Skript behandelt aber den allgemeinen Fall.)



Eine Notiz zu diese Forumbeitrag schreiben Notiz   Profil  Quote  Link auf diesen Beitrag Link
Diophant
Senior Letzter Besuch: in der letzten Woche
Dabei seit: 18.01.2019
Mitteilungen: 4418
Aus: Rosenfeld, BW
Zum letzten BeitragZum nächsten BeitragZum vorigen BeitragZum erstem Beitrag  Beitrag No.10, eingetragen 2020-07-12

\(\begingroup\)\(\newcommand{\ba}{\begin{aligned}} \newcommand{\ea}{\end{aligned}} \newcommand{\bpm}{\begin{pmatrix}} \newcommand{\epm}{\end{pmatrix}} \newcommand{\bc}{\begin{cases}} \newcommand{\ec}{\end{cases}} \newcommand{\on}{\operatorname}\)
@zippy:
2020-07-12 15:26 - zippy in Beitrag No. 9 schreibt:
2020-07-12 14:49 - Diophant in Beitrag No. 8 schreibt:
Und wie wir wissen sind das unendlich viele Lösungen.
Nicht notwendigerweise. Du scheinst nur an unendliche Körper zu denken.

(Das Skript behandelt aber den allgemeinen Fall.)

Ah, ok, danke für den Verweis auf das Skript. Ich hatte jetzt in der Tat nur an \(\IR\) bzw. \(\IC\) gedacht.


Gruß, Diophant
\(\endgroup\)


Eine Notiz zu diese Forumbeitrag schreiben Notiz   Profil  Quote  Link auf diesen Beitrag Link
X3nion
Aktiv Letzter Besuch: in der letzten Woche
Dabei seit: 17.04.2014
Mitteilungen: 766
Zum letzten BeitragZum nächsten BeitragZum vorigen BeitragZum erstem Beitrag  Beitrag No.11, vom Themenstarter, eingetragen 2020-07-13


Hallo zusammen,

mir ist es nun klar geworden!


Nicht notwendigerweise. Du scheinst nur an unendliche Körper zu denken.

(Das Skript behandelt aber den allgemeinen Fall.)

Wie bist du auf das Skript gestoßen, zippy? 😁

VG X3nion



Eine Notiz zu diese Forumbeitrag schreiben Notiz   Profil  Quote  Link auf diesen Beitrag Link
zippy
Senior Letzter Besuch: in der letzten Woche
Dabei seit: 24.10.2018
Mitteilungen: 1343
Zum letzten BeitragZum nächsten BeitragZum vorigen BeitragZum erstem Beitrag  Beitrag No.12, eingetragen 2020-07-13


2020-07-13 17:29 - X3nion in Beitrag No. 11 schreibt:
Wie bist du auf das Skript gestoßen, zippy? 😁

Ein Textfragment von unter 10 Worten genügt im Regelfall, um ein Dokument per Google zu identifizieren. In diesem Fall war es das Fragment "Die Lösung ist eindeutig, falls eine Lösung existiert".



Eine Notiz zu diese Forumbeitrag schreiben Notiz   Profil  Quote  Link auf diesen Beitrag Link
X3nion
Aktiv Letzter Besuch: in der letzten Woche
Dabei seit: 17.04.2014
Mitteilungen: 766
Zum letzten BeitragZum nächsten BeitragZum vorigen BeitragZum erstem Beitrag  Beitrag No.13, vom Themenstarter, eingetragen 2020-07-13



Ein Textfragment von unter 10 Worten genügt im Regelfall, um ein Dokument per Google zu identifizieren. In diesem Fall war es das Fragment "Die Lösung ist eindeutig, falls eine Lösung existiert".

Hehehe sehr gut! Das setzt aber voraus, dass der Fragesteller den Text eins zu eins abtippt 😄

Vielen Dank euch beiden für eure Hilfe!

VG X3nion



Eine Notiz zu diese Forumbeitrag schreiben Notiz   Profil  Quote  Link auf diesen Beitrag Link
X3nion hat die Antworten auf ihre/seine Frage gesehen.
Das Thema wurde von einem Senior oder Moderator abgehakt.
Neues Thema [Neues Thema]  Druckversion [Druckversion]

 


Wechsel in ein anderes Forum:
 Suchen    
 
All logos and trademarks in this site are property of their respective owner. The comments are property of their posters, all the rest © 2001-2020 by Matroids Matheplanet
This web site was originally made with PHP-Nuke, a former web portal system written in PHP that seems no longer to be maintained nor supported. PHP-Nuke is Free Software released under the GNU/GPL license.
Ich distanziere mich von rechtswidrigen oder anstößigen Inhalten, die sich trotz aufmerksamer Prüfung hinter hier verwendeten Links verbergen mögen.
Lesen Sie die Nutzungsbedingungen, die Distanzierung, die Datenschutzerklärung und das Impressum.
[Seitenanfang]