Ein lineares Gleichungssystem (kurz LGS) ist in der linearen Algebra eine Menge linearer Gleichungen mit einer oder mehreren Unbekannten. In der Theorie der linearen Gleichungssysteme fragt man nach Lösungen eines vorgelegten linearen Gleichungssystems, also nach konkreten Werten für die Unbekannten, so dass alle Gleichungen zugleich erfüllt sind.
Ein entsprechendes System mit drei Unbekannten sieht beispielsweise wie folgt aus:
Für sind alle drei Gleichungen erfüllt, es handelt sich um eine Lösung des Systems. Diese besteht also im Unterschied zur Lösungsmenge einer einzigen Gleichung in diesem Beispiel – alle Punkte einer Ebene im dreidimensionalen Raum – aus einem n-Tupel, in diesem Fall einem Zahlentripel. Dieses wird auch als Lösungsvektor bezeichnet. Zur Anzahl der möglichen Lösungen siehe den Abschnitt Lösbarkeit.
Allgemein lässt sich ein lineares Gleichungssystem mit Gleichungen und Unbekannten immer in die folgende Form bringen:
Lineare Gleichungssysteme werden als homogen bezeichnet, wenn alle gleich 0 sind, andernfalls als inhomogen. Homogene Gleichungssysteme besitzen stets mindestens die sogenannte triviale Lösung, bei der alle Variablen gleich 0 sind. Bei inhomogenen Gleichungssystemen kann dagegen der Fall eintreten, dass überhaupt keine Lösung existiert.
„Spaltenweise“ und „zeilenweise“ geometrische Interpretation Geht man von einer vorgegebenen Basis eines -dimensionalen Vektorraumes aus, so lassen sich die reellen Zahlen in der -ten „Spalte“ des Gleichungssystems, also die Zahlen als Koeffizienten eines Vektors auffassen. Ebenso lassen sich als Koeffizienten eines Lösungsvektors interpretieren.
Damit lässt sich die Lösung eines linearen Gleichungssystems auf das Problem zurückführen, den Lösungsvektor durch eine Linearkombination der Vektoren darzustellen. Gesucht sind also Folgen reeller Zahlen , sodass .
Alternativ lässt sich jede der m Zeilen eines linearen Gleichungssystems geometrisch als Gleichung einer Hyperebene in einem n-dimensionalen Vektorraum deuten, wobei n die Anzahl der Variablen bzw. Unbekannten ist. Spezialfälle von Hyperebenen sind Geraden in der Ebene und Ebenen im Raum.
Hierbei geht man von einer vorgegebenen Basis eines -dimensionalen Vektorraumes sowie von der dualen Basis des Vektorraumes der zugehörigen Linearformen aus. Dann lassen sich die reellen Zahlen der -ten Zeile als Koeffizienten einer Linearform interpretieren. Ebenso lassen sich die als Koeffizienten eines Vektors auffassen. Die -te Gleichung des linearen Gleichungssystems ():
ist dann die Bestimmungsgleichung der affinen Hyperebene
Damit lässt sich die Lösung eines linearen Gleichungssystems auf ein Schnittproblem von Hyperebenen zurückführen: Gesucht ist die Menge der gemeinsamen Punkte aller Hyperebenen.
Keine dieser beiden Sichtweisen ist grundsätzlich der anderen vorzuziehen. Wichtig für ein umfassendes Verständnis ist vielmehr die geschickte Kombination der verschiedenen Perspektiven. Der im Abschnitt Lösbarkeitskriterien zitierte Satz von Kronecker-Capelli ergibt sich z. B. als unmittelbare Folge des „spaltenweisen“ Ansatzes. Die unten angegebenen Beispiele für die Lösung als Schnitt von zwei Geraden in der Ebene basieren hingegen auf der „zeilenweisen“ Interpretation des Gleichungssystems.
Beispiel mini|Die Graphen der Fragestellung, die sich im Punkt schneiden Lineare Gleichungssysteme entstehen vielfach als Modelle von praktischen Aufgabenstellungen. Ein typisches Beispiel aus der Schulmathematik lautet wie folgt:
Es lässt sich auch durch das folgende lineare Gleichungssystem beschreiben:
Die Variable repräsentiert hier das Alter des Vaters und die Variable das des Sohnes. Das Gleichungssystem wird in einem ersten Schritt üblicherweise in eine Standardform gebracht, bei der auf der linken Seite nur Terme mit Variablen und auf der rechten Seite reine Zahlen stehen. Im vorliegenden Beispiel wird dazu die zweite Gleichung ausmultipliziert und umgestellt.
Um dieses Gleichungssystem zu lösen, kann auf eine Vielzahl von Lösungsverfahren (siehe Lösungsverfahren) zurückgegriffen werden. Beispielhaft wird hier das Additionsverfahren verwendet. Um zunächst die Variable zu eliminieren, wird die erste Gleichung von der zweiten subtrahiert.
Die entstandene Gleichung wird nach der Variablen aufgelöst, indem beide Seiten durch geteilt werden. Das ergibt das Alter des Sohnes, der 16 Jahre alt ist. Dieser Wert für wird wieder in die erste Gleichung eingesetzt.
Durch die Auflösung der Gleichung nach der Variablen lässt sich das Alter des Vaters berechnen, der 46 Jahre alt ist.
Die Aufgabe lässt sich auch geometrisch lösen, indem die beiden Zeilen des linearen Gleichungssystems als Geradengleichungen interpretiert werden. Dabei werden die Variable als und die Variable als bezeichnet und beide Gleichungen nach aufgelöst:
Der Schnittpunkt der beiden Geraden ist der Punkt , wobei die erste Koordinate dem Alter des Vaters und die zweite dem Alter des Sohnes entspricht (siehe Grafik).
Matrixform Für die Behandlung von linearen Gleichungssystemen ist es nützlich, alle Koeffizienten zu einer Matrix , der sogenannten Koeffizientenmatrix zusammenzufassen:
Des Weiteren lassen sich auch alle Unbekannten und die rechte Seite des Gleichungssystems zu einspaltigen Matrizen (das sind Spaltenvektoren) zusammenfassen:
Damit schreibt sich ein lineares Gleichungssystem unter Benutzung der Matrix-Vektor-Multiplikation kurz
Sowohl die Koeffizienten , die Unbekannten als auch die entstammen demselben Körper . Insbesondere gilt und . Zur Festlegung eines linearen Gleichungssystems ist die Angabe der Unbekannten nicht nötig. Es genügt die Angabe der erweiterten Koeffizientenmatrix, die entsteht, wenn an die Koeffizientenmatrix eine Spalte mit der rechten Seite des Gleichungssystems angefügt wird:
Lösbarkeit mini|Lösungen von Linearen Gleichungen Ein Vektor ist eine Lösung des linearen Gleichungssystems, wenn gilt. Ob und wie viele Lösungen ein Gleichungssystem besitzt, ist unterschiedlich. Bei linearen Gleichungssystemen über einem unendlichen Körper können drei Fälle auftreten: Das lineare Gleichungssystem hat keine Lösung, d. h., die Lösungsmenge ist die leere Menge. Das lineare Gleichungssystem hat genau eine Lösung, d. h., die Lösungsmenge enthält genau ein Element. Das lineare Gleichungssystem hat unendlich viele Lösungen. Die Lösungsmenge enthält in diesem Falle unendlich viele n-Tupel, die alle Gleichungen des Systems erfüllen. Über einem endlichen Körper ist die Anzahl der Lösungen eine Potenz der Mächtigkeit von .
Lösbarkeitskriterien Ein lineares Gleichungssystem ist genau dann lösbar, wenn der Rang der Koeffizientenmatrix gleich dem Rang der erweiterten Koeffizientenmatrix ist (Satz von Kronecker-Capelli). Ist der Rang der Koeffizientenmatrix gleich dem Rang der erweiterten Koeffizientenmatrix und auch gleich der Anzahl der Unbekannten, so besitzt das Gleichungssystem genau eine Lösung.
Bei einem quadratischen Gleichungssystem, also im Fall (siehe unten), gibt die Determinante Auskunft über die Lösbarkeit. Das Gleichungssystem ist genau dann eindeutig lösbar, wenn der Wert der Determinante der Koeffizientenmatrix ungleich null ist. Ist der Wert jedoch gleich null, hängt die Lösbarkeit von den Werten der Nebendeterminanten ab. Bei diesen wird jeweils eine Spalte der Koeffizientenmatrix durch die Spalte der rechten Seite (den Vektor ) ersetzt. Nur wenn alle Nebendeterminanten den Wert null haben, kann das System unendlich viele Lösungen haben, ansonsten ist das Gleichungssystem unlösbar.
Insbesondere Gleichungssysteme mit mehr Gleichungen als Unbekannten, sogenannte überbestimmte Gleichungssysteme, besitzen häufig keine Lösung. Beispielsweise besitzt das folgende Gleichungssystem keine Lösung, da nicht beide Gleichungen erfüllen kann:
Näherungslösungen von überbestimmten Gleichungssystemen werden dann meist über die Ausgleichungsrechnung definiert und bestimmt.
Dass ein lineares Gleichungssystem unendlich viele Lösungen hat, kann nur vorkommen, wenn es weniger linear unabhängige Gleichungen als Unbekannte gibt und der zugrundeliegende Körper unendlich viele Elemente enthält. Beispielsweise besitzt das folgende (aus nur einer Gleichung bestehende) Gleichungssystem unendlich viele Lösungen, nämlich alle Vektoren mit
Lösungsmenge Die Lösungsmenge eines linearen Gleichungssystems besteht aus allen Vektoren , für die erfüllt ist:
Liegt ein homogenes lineares Gleichungssystem vor, so bildet dessen Lösungsmenge einen Untervektorraum von . Damit gilt die Superpositionseigenschaft, nach der für eine oder mehrere Lösungen auch deren Linearkombinationen (mit beliebigen ) Lösungen des Gleichungssystems sind. Die Lösungsmenge heißt daher auch Lösungsraum und ist identisch mit dem Kern der Matrix . Bezeichnet den Rang der Matrix , dann ist nach dem Rangsatz die Dimension des Lösungsraumes gleich dem Defekt der Matrix .
Ist die Lösungsmenge eines inhomogenen linearen Gleichungssystem nicht leer, dann ist sie ein affiner Unterraum von . Sie hat dann die Form , wobei der Lösungsraum des zugehörigen homogenen Gleichungssystems ist und eine beliebige Lösung des inhomogenen Gleichungssystems. Ein inhomogenes Gleichungssystem ist folglich genau dann eindeutig lösbar, wenn der Nullvektor die einzige Lösung („triviale Lösung“) des homogenen Gleichungssystems ist. Insbesondere gilt entweder oder mit .
Die Lösungsmenge eines linearen Gleichungssystems verändert sich nicht, wenn eine der drei elementaren Zeilenumformungen durchgeführt wird: Vertauschen zweier Zeilen Multiplizieren einer Zeile mit einer von null verschiedenen Zahl Addieren einer Zeile (oder des Vielfachen einer Zeile) zu einer anderen Zeile Die Lösungsmenge eines quadratischen linearen Gleichungssystems verändert sich sogar dann nicht, wenn das Gleichungssystem mit einer regulären Matrix multipliziert wird.
Bestimmung über die erweiterte Koeffizientenmatrix Die Form der Lösungsmenge lässt sich grundsätzlich mit Hilfe der erweiterten Koeffizientenmatrix bestimmen, indem diese mit Hilfe elementarer Zeilenumformungen (siehe Gauß-Verfahren) auf Stufenform gebracht wird:
Um immer genau diese Form zu erhalten, muss man manchmal auch Spaltenvertauschungen durchführen. Spaltenvertauschungen ändern die Reihenfolge der Variablen, was man am Schluss berücksichtigen muss. Außerdem wird hier auch angenommen, dass die Koeffizienten nicht null sind.
Die Anzahl der Lösungen lässt sich dann an den ablesen: Ist mindestens eines der ungleich null, so gibt es keine Lösung. Sind alle gleich null (oder ), so gilt: Ist , so ist das Gleichungssystem eindeutig lösbar. Ist , gibt es unendlich viele Lösungen. Der Lösungsraum hat die Dimension .
Durch weitere elementare Zeilenumformungen (siehe Gauß-Jordan-Verfahren) kann die Matrix in folgende Form gebracht werden:
Sofern es überhaupt eine Lösung gibt (), gilt für die Lösungsmenge :
Hierbei ist der Vektor der freien Variablen.
Formen von Gleichungssystemen Lineare Gleichungssysteme können in Formen vorliegen, in denen sie leicht gelöst werden können. Vielfach werden beliebige Gleichungssysteme mittels eines Algorithmus in eine entsprechende Gestalt gebracht, um anschließend eine Lösung zu finden.
Quadratisch Von einem quadratischen Gleichungssystem ist die Rede, wenn die Zahl der Unbekannten gleich der Zahl der Gleichungen ist. Ein Gleichungssystem dieser Form kann, wenn die Zeilen oder Spalten linear unabhängig sind, eindeutig gelöst werden (Lösungsverfahren werden weiter unten besprochen).
Stufenform, Treppenform In der Stufenform (auch Zeilenstufenform, Zeilennormalform, Stufengestalt, Staffelgestalt, Treppenform, Treppenstufenform oder Treppennormalform) verringert sich in jeder Zeile die Zahl der Unbekannten um mindestens eine, die dann auch in den darauffolgenden Zeilen nicht mehr vorkommt. Durch die Anwendung des gaußschen Eliminationsverfahrens kann jedes Gleichungssystem in diese Form gebracht werden.