5.11 Die Zeilenstufenform

Definition (Zeilenstufenform, Pivots, ausgeräumt, diagonal)

Seien K ein Körper, m, n ≥ 1 und A  ∈  K^{m × n}. Weiter seien a₁, …, a_m die Zeilen von A.

Wir sagen, dass A Zeilenstufenform ist, falls gilt:

(a)	Es gibt ein 0 ≤ r ≤ min(m, n) mit a₁, …, a_r ≠ 0 und a_r + 1 = … = a_m = 0.

(b)	Es gilt p(1) < … < p(r) für p(i) = min({ j \| A(i, j) ≠ 0 }).

Die Einträge A(1, p(1)), …, A(r, p(r)) heißen dann die Pivots von A. Sind alle Pivots gleich 1 und alle Einträge über den Pivots gleich 0, so heißt A reduziert. Gilt p(i) = i für alle i, so hat A diagonale Pivots.

Eine 6 x 12-Matrix in Zeilenstufenform mit r = 4 und Pivots 1, 4, 6, −1 an den Stellen (1, 3), (2, 5), (3, 6), (4, 9). Die Waagrechten des Linienzugs können beliebig lang sein, die Senkrechten haben dagegen stets die Länge eins. Die Matrix kann mit 0-Spalten beginnen und mit 0-Zeilen enden.

Die Pivots einer Matrix in Zeilenstufenform sitzen an den Stufen einer fallenden Treppe, unter der sich nur Nullen befinden. Aus der Treppenanordnung ergibt sich:

Rang einer Matrix in Zeilenstufenform

Hat A  ∈  K^{n × m} Zeilenstufenform mit r Pivots, so sind die r Zeilen sowie die r Spalten, die Pivots enthalten, linear unabhängig. Es gilt rang(A) = r.

Beispiele

reduziert

diagonale Pivots

reduziert mit diagonalen Pivots

Die Zeilenstufenform ist im Hinblick auf lineare Gleichungssysteme von Interesse. Liegt ein lineares Gleichungssystem Ax = b mit einer Koeffizientenmatrix A  ∈  K^{m × n} in Zeilenstufenform und beliebiger rechter Seite b  ∈  K^m vor, so können wir die Lösbarkeit des Systems direkt ablesen und die Lösungen vergleichsweise einfach bestimmen:

Lösbarkeitskriterium

b = $( \begin{matrix} \bar{b} \\ 0 \end{matrix} )$ , b  ∈  K^r

lösbare rechte Seiten

Sei A  ∈  K^{m × n} in Zeilenstufenform mit r Pivots, d. h. m − r Nullzeilen. Weiter sei b  ∈  K^m. Dann ist Ax = b genau dann lösbar, wenn

(+) b_r + 1 = … = b_m = 0.

Gilt (+), so ist der Lösungsraum L_A(b) = { x  ∈  Kⁿ | Ax = b } ein (n − r)-dimensionaler affiner Unterraum des Kⁿ (vgl. 4. 8). Die Lösungen lassen sich dann in Abhängigkeit der Qualität der Zeilenstufenform auf verschiedene Weisen bestimmen:

Form I: A ist reduziert mit diagonalen Pivots

Es gilt A = $( \begin{matrix} E_{r} & \bar{A} \\ 0 & 0 \end{matrix} )$ = $( \begin{matrix} E_{r} & {\bar{a}}_{r + 1} & … & {\bar{a}}_{n} \\ 0 & 0 \end{matrix} )$ , a_{r +1}, …, a_n  ∈  K^r, sodass

L_A(b) = { $( \begin{matrix} \bar{b} \\ 0 \end{matrix} )$ + λ₁ $( \begin{matrix} - {\bar{a}}_{r + 1} \\ e_{1} \end{matrix} )$ + … + λ_n − r $( \begin{matrix} - {\bar{a}}_{n} \\ e_{n - r} \end{matrix} )$ | λ₁, …, λ_n − r  ∈  K }.

Dabei sind e₁, …, e_n − r die kanonischen Basisvektoren des K^n − r.

Form II: A hat diagonale Pivots

Wir finden Lösungen durch „Rückwärts-Substitution“: Beliebig vorgegebene x_r + 1, …, x_n  ∈  K ergänzen wir durch

x_r = ^{b_r − a_{r, r +1}x_{r +1} − … − a_r,nx_n}_{a_r,r},

…

x₁ = ^{b₁ − a_{1, 2}x₂ − … − a_1,nx_n}_{a_1,1}

zu einer Lösung x = (x₁, …, x_n) von Ax = b.

Form III: Allgemeiner Fall

Liegen die Pivots nicht auf der Diagonale, so können wir dies durch Vertauschung der Spalten von A erreichen. Es gibt eine Permutationsmatrix P = P_π  ∈  K^{n × n} derart, dass AP diagonale Pivots besitzt. Dann gilt

L_A(b) =	{ x \| Ax = b } = { Px′ \| APx′ = b } = { Px′ \| x′  ∈  L_AP(b) } =
	{ (x′_π⁻¹(1) , …, x′_π⁻¹(n)) \| x′  ∈  L_AP(b) },

sodass wir die Lösungen von L_A(b) durch die Form I oder II erhalten können. Die rechte Seite b bleibt bei dieser „Umbenennung der Variablen“ unverändert.

Die Überführung eines beliebigen Systems Ax = b in ein äquivalentes System A′x′ = b′ mit A′ in Zeilenstufenform besprechen wir im folgenden Abschnitt.