Lösungsraum Trick

Einstieg

Viele Probleme lassen sich in der linearen Algebra auf das Lösen lineare Gleichungssysteme zurückführen. Dieser Trick funktioniert nur für lösbare lineare Gleichungssysteme in Treppenform und erlaubt es, einen Lösungsraum schnell zu bestimmen.

Als Erstes stellen wir das Gleichungssystem in einer Koeffizientenmatrix da. Falls das Gleichungssystem mehr unbekannte als Gleichungen besitzt, fügen wir entsprechend viele Nullzeilen ein. Wir verwenden solange den Gauß-Jordan-Algorithmus, bis die Koeffizientenmatrix die Treppenform besitzt d.h :

• Das jeweils erste Element einer Zeile von $\mathcal{M}\backslash mathcal\{M\}$ ist eine $11$

• Alle Elemente über und unter der Diagonal $11$ ist $00$

Außerdem muss gefodert werden. Das die jeweils ersten Elemente einer Zeile auf der Diagonale stehen.

Versucht man diesen Trick auf eine Matrix anzuwenden, welche nicht diese Gestalt besitzt. So liefert das Verfahren falsche Ergebnisse.

Verfahren

Besitzt nun die Matrix die Gestalt von $\mathcal{M},\backslash mathcal\{M\},$ so geht man wie folgt vor:

• Jede Diagonal 0 wird mit $-1-1$ ersetzt

• Jede korrospondierende Spalte von einer ersetzen Diagonal 0, ist automatisch ein Lösungsvektor

• Der Vektor $b\in b\; \backslash in$ ${\mathbb{K}}^n\backslash mathbb\{K\}^n$ ist der Lösungsvektor

Beispiel

Betrachten wir folgendes Gleichungssystem

Wir repräsentieren das Gleichungssystem in einer Matrix. Außerdem muss die Matrix mit Nullzeilen aufgeführt werden, da es mehr Unbekannte als Gleichungen gibt. Ohne den Vektor $bb$ besitzt die Matrix nun eine Blockgestalt.

Die Matrix kann nun in Gauß Normalform gebracht werden. Durch Addieren der ersten Zeile auf die zweite und die zweite anschließend auf die erste, erhalten wie die gewünschte Gestalt.

Nun ersetzen wir alle Diagonalnullen. In unserem Beispiel ersetzen wir also die Diagonalnull in Spalte 3 und 4 Spalte mit $-1-1$.

Jetzt können wir die Lösungen ablesen. Die Spalte 3 und 4 beinhaltet unsere Lösungsvektoren und der Vektor $bb$ ist der entsprechende Lösungsvektor. Damit erhalten wir dem Lösungsraum

$\mathcal{L}=\{b+v_1\cdot t+\cdots +v_n\cdot t\mathrm{\mid }t\in \mathbb{K}\}=\{(3,2,0,0)+(14,6,0,-1)\cdot t+(5,-1,-1,0)\cdot t\mathrm{\mid }t\in \mathbb{R}\}\backslash mathcal\{L\}\; =\; \backslash \{\; b\; +\; v\_1\; \backslash cdot\; t\; +\; \backslash dots\; +\; v\_n\; \backslash cdot\; t\; |\; t\; \backslash in\; \backslash mathbb\{K\}\; \backslash \}\; \backslash \backslash \; =\; \backslash \{\; (3,\; 2,\; 0,\; 0)\; +\; (14,\; 6,\; 0,\; -1)\; \backslash cdot\; t\; +\; (5,\; -1,\; -1,\; 0)\; \backslash cdot\; t\; |\; t\; \backslash in\; \backslash mathbb\{R\}\; \backslash \}$

Bemerkung

Der Trick funktioniert auch für nicht homogene Gleichungssysteme. Der Lösungsvektor muss aber zwingend in den Lösungsraum mit einfließen.

Für homogene Gleichungssysteme lässt sich das Verfahren ganz einfach beweisen. Dazu betrachtet man den Spaltenindex $s_i\backslash \; s\_i$ der die jeweilige Spalte des ersten, zweiten und n-ten Pivotelement angibt. Im vorherigen Beispiel galt $s_i=i,s\_i=i,$ aber natürlich können die Spalten vertauscht sein. Dann kann man durch nachrechnen prüfen, dass die Fundamentallösung $F^{j}F^j$ tatsächlich eine gültige Lösung für das Gleichungssystem $Ax=0ist,Ax\backslash \; =\backslash \; 0\backslash \; ist,$ wobei $jj$ definiert ist als $j\in \left\{q_{i,\mathrm{.}\mathrm{.}\mathrm{.},q_r}\right\}\setminus \left\{s_{1,\mathrm{.}\mathrm{.}\mathrm{.},s_r}\right\}j\backslash \; \backslash \; \backslash in\backslash \; \backslash left\backslash \{q\_\{i,\backslash \; ...\backslash \; ,\backslash \; q\_r\}\backslash right\backslash \}\backslash \; \backslash setminus\backslash \; \backslash \; \backslash left\backslash \{s\_\{1,\backslash \; ...\backslash \; ,\backslash \; s\_r\}\backslash right\backslash \}$, also genau die Spalten die frei belegt werden können. Dann lässt sich die Fundamentallösung schreiben als $F^j=e_j-{\sum }_{i=1}^r{t}_{ij}{e}_{s_i}F^j\backslash \; =\backslash \; e\_\{j\backslash \; \}-\backslash sum\_\{i=1\}^rt\_\{ij\}\backslash \; e\_\{s\_i\}$. Nun muss man prüfen ob $T{F}_j=0T\backslash \; F\_j\backslash \; =\backslash \; 0$. Durch einsetzen folgt: $T\cdot F_j=T\cdot T\backslash \; \backslash cdot\backslash \; F\_\{j\backslash \; \}\backslash \; =\backslash \; T\backslash \; \backslash cdot$$e_j-e\_j\backslash \; -\backslash$${\sum }_{i=1}^r{t}_{ij}\cdot T\cdot e_{s_i}={\sum }_{k=1}^r{t}_{kj}\cdot e_j-{\sum }_{i=1}^r{t}_{ij}\cdot e_i=0\backslash sum\_\{i=1\}^rt\_\{ij\}\backslash \; \backslash \; \backslash cdot\backslash \; T\backslash \; \backslash cdot\backslash \; e\_\{s\_i\}\backslash \; =\backslash sum\_\{k=1\}^rt\_\{kj\}\backslash \; \backslash \; \backslash cdot\; e\_\{j\backslash \; \}\backslash \; -\backslash \; \backslash sum\_\{i=1\}^rt\_\{ij\}\backslash \; \backslash cdot\; e\_i\backslash \; =0\backslash \; \backslash$und somit folgt die Behauptung.