Grundoperationen

Die Grundoperationen lassen sich mit einer invertierbaren Matrix T darstellen, mit der die Transformationsgleichung LAR = B von rechts bzw. links multipliziert wird:

Spaltenoperationen:	LART = BT	→	LAR' = B'	mit	R' = RT	und	B' = BT
Zeilenoperationen:	TLAR = TB	→	L"AR = B"	mit	L" = TL	und	B" = TB

Nach k solchen Operationen ist

R' = RT₁T₂…T_k    bzw.    L" = T_kT_k-1…T₁L

was die multiplikative Zusammensetzung der regulären Transformation zeigt. Sind R und L anfänglich Einheitsmatrizen, enthält R' das Produkt der Transformationsmatrizen in der Reihenfolge ihres Auftretens und L" das Produkt in entgegengesetzter Reihenfolge. Umgekehrt verhält es sich bei ihren Inversen: Da enthält L"⁻¹ das Produkt der Inversen in der Reihenfolge ihres Auftretens und R'⁻¹ das Produkt in entgegengesetzter Reihenfolge. Diese Tatsache ist bei den absteigenden Folgen von Elevatoren bedeutsam.

Die drei Grundoperationen sind:

Umordnung der Spalten oder Zeilen

• Umordnung der Spalten: Die Reihenfolge der Spalten wird modifiziert, ohne sie selbst zu verändern. Die entsprechende Matrix T ist eine Permutationsmatrix P_R, deren Inverse ihre transponierte Matrix ist.
• Umordnung der Zeilen entsprechend einer Permutationsmatrix T = P_L.

Multiplikation der Spalten oder Zeilen mit invertierbaren Skalaren

• Multiplikation der Spalten: Alle Einträge in einer Spalte werden mit demselben Faktor (ungleich null) multipliziert. Die Matrix T ist eine Diagonalmatrix D_R mit den Skalaren auf der Hauptdiagonalen. Die Inverse dieser Diagonalmatrix ist die Diagonalmatrix mit den Kehrwerten, die nach Voraussetzung existieren.
• Multiplikation der Zeilen, was mit einer Diagonalmatrix T = D_L geschieht.

Linearkombination der Spalten oder Zeilen

• Linearkombination der Spalten: Eine Spalte, die Pivotspalte, wird mit einem Faktor multipliziert und zu einer anderen Spalte addiert oder von ihr subtrahiert. Die Matrix T ist ein sogenannter Zeilenelevator ρ, dessen Inverse sich durch Vorzeichenumkehr der Nebendiagonalglieder bildet.
• Linearkombination der Zeilen mittels eines Spaltenelevators T = λ, dessen Inverse auch durch Vorzeichenumkehr der Nebendiagonalglieder entsteht.

Die Grundoperationen können weiter in Einzelschritte mit Elementarmatrizen zerlegt werden, die ebenso leicht wie die Matrizen P_R/L, D_R/L, ρ und λ invertiert werden können. Das Produkt der Elevatoren, das bei mehreren aufeinander folgenden Linearkombinationen von Spalten oder Zeilen anfällt, kann auch leicht invertiert werden, wenn sie eine absteigende Folge eines vollständigen Systems von Elevatoren bilden.

Elevatoren

Bei einer Linearkombination von Spalten oder Zeilen einer Einheitsmatrix wird diese in einen Zeilenelevator ρ bzw. Spaltenelevator λ transformiert, der, multipliziert mit einer Matrix, dieselbe Wirkung hat wie die Linearkombination deren Spalten oder Zeilen.

Ein Zeilenelevator besteht gemäß

ρ = I_m + e_j p_j^⊤

mit Standardbasis e_1,…,m des K^m aus der Einheitsmatrix I_m ∈ K^m×m und höchstens einer signifikanten Zeile p_j ∈ K^m mit weiteren von null verschiedenen Einträgen. Das hochgestellte ⊤ zeigt die transponierte Matrix an, sodass p_j^⊤ ein Zeilenvektor ist. Tatsächlich ist mit den Spalten b_k = B e_k:

B' e_k = B ρ e_k = B (I_m + e_j p_j^⊤) e_k = b_k + b_j p_jk   mit    p_jk = p_j^⊤e_k

Das heißt, dass zu jeder Spalte b_k, wie es sein soll, das p_jk fache der Pivotspalte b_j hinzu addiert wird. Die günstigen Eigenschaften, die eine Absteigende Folge von Elevatoren hat, basieren darauf, dass die Pivotspalte bei der Linearkombination der Spalten unveränderlich ist, also p_jj = 0 ist. Die j-te Zeile von ρ,

z_j = e_j^⊤ρ = (e_j + p_j)^⊤

hat daher eine Eins auf der Hauptdiagonale, z_jj = 1, während die restringierte Zeile p_j dort eine Null aufweist.

Die Inverse Matrix der Elevatoren kann sofort angegeben werden:

ρ⁻¹ = I_m − e_j p_j^⊤

Denn wegen 0 = p_jj = p_j^⊤e_j ist

ρρ⁻¹ = (I_m + e_jp_j^⊤)(I_m − e_jp_j^⊤) = I_m + e_jp_j^⊤ − e_jp_j^⊤ − e_jp_j^⊤e_jp_j = I_m

Entsprechendes gilt für die Spaltenelevatoren

λ = I_n + q_j e_j^⊤   →    λ⁻¹ = I_n − q_j e_j^⊤

wo nun der Kⁿ zugrunde gelegt wird und die Faktoren in einer signifikanten Spalte λe_j = s_j = e_j + q_j auftreten, mit s_jj = 1 und q_jj = 0. Die Inversen der Elevatoren bilden sich jedenfalls durch Vorzeichenumkehr der Nebendiagonalglieder.

Pivotkreuz

Beim Pivotkreuz wird in einem Schritt die Matrix A gemäß LAR = B in eine Matrix B transformiert, in der eine Spalte und eine Zeile vorgegebene Einträge besitzt:

Die vorgegebene Spalte und Zeile heißt Pivotspalte bzw. -zeile (blau und gelb unterlegt) und das Matrixelement, in dem sie sich treffen ist das Pivotelement (rosa unterlegt). Es muss von null verschieden sein und ist bei diesem Vorgang unveränderlich. Durch die Vorgaben sind die Linearkombinationen mit der Pivotspalte und -zeile eindeutig festgelegt.

Zur Erzielung des vorgegebenen Elements B_kj der Pivotspalte j, muss der Faktor q_kj die Bedingung^:60

B_kj = A_kj + q_kj A_ij

erfüllen. Weil nach Voraussetzung A_ij ≠ 0, bestimmt sich der Faktor zu

q_kj = (B_kj - A_kj)/A_ij

Der Faktor p_il ermittelt sich analog aus dem Pivotelement A_ij und dem vorgegebenen Element B_il der Pivotzeile i:^:62

B_il = A_il + p_il A_ij   →   p_il = (B_il − A_il)/A_ij

Als Beispiel diene die Matrix

${\displaystyle {\mathsf {A}}={\begin{pmatrix}1&2&3\\4&5&6\end{pmatrix}}}$

mit dem Ziel des gelb unterlegten Pivotkreuzes und der fünf als Pivotelement:

Der Faktor q₁₂ berechnet sich zu

q₁₂ = (B₁₂ - A₁₂)/A₂₂ = (7 - 2)/5 = 1

Die Faktoren p₂₁ und p₂₃ ergeben sich aus

p₂₁ = (B₂₁ - A₂₁)/A₂₂ = (-6 - 4)/5 = -2

p₂₃ = (B₂₃ - A₂₃)/A₂₂ = (1 - 6)/5 = -1

Der Vektor links von A wird in die Einheitsmatrix eingetragen, was den Spaltenelevator

${\displaystyle \lambda _{1}={\begin{pmatrix}1&{\mathsf {q}}_{12}\\0&1\end{pmatrix}}={\begin{pmatrix}1&1\\0&1\end{pmatrix}}}$

gibt und der Zeilenvektor unter A erbringt in die Einheitsmatrix eingetragen den Zeilenelevator

${\displaystyle \rho _{1}={\begin{pmatrix}1&0&0\\{\mathsf {p}}_{21}&1&{\mathsf {p}}_{23}\\0&0&1\end{pmatrix}}={\begin{pmatrix}1&0&0\\-2&1&-1\\0&0&1\end{pmatrix}}}$

Die Transformation

${\displaystyle \lambda _{1}{\mathsf {A}}\rho _{1}={\begin{pmatrix}1&1\\0&1\end{pmatrix}}{\begin{pmatrix}1&2&3\\4&5&6\end{pmatrix}}{\begin{pmatrix}1&0&0\\-2&1&-1\\0&0&1\end{pmatrix}}={\begin{pmatrix}-9&\color {red}7&2\\\color {red}-6&\color {red}5&\color {red}1\end{pmatrix}}}$

bestätigt den Erfolg des Vorgehens. Die Inversen der Elevatoren sind schnell aufgeschrieben durch Vorzeichenumkehr aller Elemente abseits der Hauptdiagonalen:

${\displaystyle \lambda _{1}^{-1}={\begin{pmatrix}1&-{\mathsf {q}}_{12}\\0&1\end{pmatrix}}={\begin{pmatrix}1&-1\\0&1\end{pmatrix}}}$

bzw.

${\displaystyle \rho _{1}^{-1}={\begin{pmatrix}1&0&0\\-{\mathsf {p}}_{21}&1&-{\mathsf {p}}_{23}\\0&0&1\end{pmatrix}}={\begin{pmatrix}1&0&0\\2&1&1\\0&0&1\end{pmatrix}}}$

Nullenkreuz

Das Nullenkreuz ist ein Pivotkreuz, das neben dem Pivotelement (an der Stelle i,j) nur Nullen aufweist:

Der damit Verbundene Vorgang wird Reduktion der Spalte j bzw. Reduktion der Zeile i genannt. Bei fortgeführter Reduktion mit Hilfe weiterer Pivots bleiben die bereits erzeugten Nullenkreuze erhalten. Wenn r der Rang der Matrix A ist, dann überführen höchstens r Nullenkreuze die Matrix in eine Pivotmatrix, und dabei entsteht eine vollständige Absteigende Folge von Elevatoren. Der Aufwand für die Reduktion auf eine Pivotmatrix wächst mit der dritten Potenz der Größe der Matrix.^:85

Beispiel: Vorgegeben ist

${\displaystyle {\mathsf {A}}={\begin{pmatrix}1&2&3\\4&5&6\end{pmatrix}}}$

mit Rang zwei und das erste gelb markierte Nullenkreuz

Man liest ab q₁₂=-²⁄₅, p₂₁=-⁴⁄₅ und p₂₃=-⁶⁄₅ mit den Elevatoren

${\displaystyle \lambda _{1}={\begin{pmatrix}1&{\mathsf {q}}_{12}\\0&1\end{pmatrix}}={\begin{pmatrix}1&-2/5\\0&1\end{pmatrix}}}$

${\displaystyle \rho _{1}={\begin{pmatrix}1&0&0\\{\mathsf {p}}_{21}&1&{\mathsf {p}}_{23}\\0&0&1\end{pmatrix}}={\begin{pmatrix}1&0&0\\-4/5&1&-6/5\\0&0&1\end{pmatrix}}}$

und dem Ergebnis

${\displaystyle {\mathsf {B}}=\lambda _{1}{\mathsf {A}}\rho _{1}={\begin{pmatrix}1&-2/5\\0&1\end{pmatrix}}{\begin{pmatrix}1&2&3\\4&5&6\end{pmatrix}}{\begin{pmatrix}1&0&0\\-4/5&1&-6/5\\0&0&1\end{pmatrix}}={\begin{pmatrix}-3/5&\color {red}0&3/5\\\color {red}0&\color {red}5&\color {red}0\end{pmatrix}}}$

Diese Matrix ist Startpunkt der zweiten und letzten Reduktion mit dem Nullenkreuz

das das alte unberührt lässt. Mit q₂₁ = p₁₂ = 0 und p₁₃ = 1 entstehen die Elevatoren

${\displaystyle \lambda _{2}={\begin{pmatrix}1&0\\0&1\end{pmatrix}},\quad \rho _{2}={\begin{pmatrix}1&0&1\\0&1&0\\0&0&1\end{pmatrix}}}$

und die Pivotmatrix

${\displaystyle {\mathsf {LAR}}={\begin{pmatrix}1&-2/5\\0&1\end{pmatrix}}{\begin{pmatrix}1&2&3\\4&5&6\end{pmatrix}}{\begin{pmatrix}1&0&1\\-4/5&1&-2\\0&0&1\end{pmatrix}}={\begin{pmatrix}-3/5&0&0\\0&5&0\end{pmatrix}}}$

wobei

${\displaystyle {\mathsf {L}}=\lambda _{2}\lambda _{1}={\begin{pmatrix}\color {red}1&0\\\color {red}0&1\end{pmatrix}}{\begin{pmatrix}1&\color {blue}-2/5\\0&\color {blue}1\end{pmatrix}}={\begin{pmatrix}1&-2/5\\0&1\end{pmatrix}}}$

und

${\displaystyle {\mathsf {R}}=\rho _{1}\rho _{2}={\begin{pmatrix}1&0&0\\\color {red}-4/5&\color {red}1&\color {red}-6/5\\0&0&1\end{pmatrix}}{\begin{pmatrix}\color {blue}1&\color {blue}0&\color {blue}1\\0&1&0\\0&0&1\end{pmatrix}}={\begin{pmatrix}1&0&1\\-4/5&1&-2\\0&0&1\end{pmatrix}}}$

ohne Weiteres nachzuprüfen ist. Die Elevatoren bilden eine Absteigende Folge von Elevatoren und daher können die Inversen ihrer Produkte durch Übertragung der signifikanten Spalten bzw. Zeilen nach Vorzeichenumkehr auf den Nebendiagonalen direkt aufgeschrieben werden:

${\displaystyle {\mathsf {L}}^{-1}=\lambda _{1}^{-1}\lambda _{2}^{-1}={\begin{pmatrix}\color {red}1&\color {blue}2/5\\\color {red}0&\color {blue}1\end{pmatrix}},\;{\mathsf {R}}^{-1}=\rho _{2}^{-1}\rho _{1}^{-1}={\begin{pmatrix}\color {blue}1&\color {blue}0&\color {blue}-1\\\color {red}4/5&\color {red}1&\color {red}6/5\\0&0&1\end{pmatrix}}}$

Pivotregulierung

Mit der Pivotregulierung wird das Pivotelement durch Spalten- oder Zeilenkombination auf einen vorgegebenen Wert, oft eins, eingestellt.^:86 Die Pivotregulierung ist bei einer Matrix mit Rang r höchstens r−1 mal durchführbar; ihr Aufwand beträgt maximal n²/2 Operationen und ist gegenüber dem mit der dritten Potenz von n gehenden Aufwand für die Reduktionen mit Nullenkreuzen vernachlässigbar. Die Pivotmatrix enthält am Ende nur Nullen und Einsen und nur genau ein von null und eins verschiedenes Element. Bei der Pivotregulierung einer hermiteschen Matrix müssen Spalten und Zeilen mit jeweils konjugiert komplexen Faktoren kombiniert werden, damit auch die regulierte Matrix hermitesch bleibt.^:87ff

Beispiel: Die hermitesche Matrix

${\displaystyle {\mathsf {A}}={\begin{pmatrix}0&2+\mathrm {i} \\2-\mathrm {i} &0\end{pmatrix}}}$

mit der imaginären Einheit i soll in Diagonalgestalt überführt werden. Weil beide Diagonalelemente null sind, ist eine Pivotregulierung unabdingbar. Gesucht ist p = a + ib, sodass

wird. Der Überstrich bedeutet komplexe Konjugation. Die Bedingung entspricht

B₁₁ = 1 = (a + ib)(2 + i) + (a − ib)(2 − i) oder b = 2a − 1/2

Zweckmäßig ist hier a = 1/4 zu wählen^:88, sodass p reell wird. Das Ergebnis ist dann

${\displaystyle {\mathsf {B}}={\begin{pmatrix}1&2+\mathrm {i} \\2-\mathrm {i} &0\end{pmatrix}}}$

und nach wie vor hermitesch.

Weil der Rang der Matrix zwei beträgt, ist nur diese eine Pivotregulierung möglich. Die Überführung in Diagonalgestalt erfolgt mit einem Nullenkreuz mit dem Pivotelement B₁₁ = 1 und den Faktoren q₂₁ = -2 + i bzw. p₁₂ = −2 − i und dem Endergebnis

${\displaystyle {\mathsf {B}}'={\begin{pmatrix}1&0\\0&-5\end{pmatrix}}}$

Generalschema einer Äquivalenztransformation

Die manuelle Durchführung einer Äquivalenztransformation kann in einer erweiterten Matrix

geschehen, wo O die Nullmatrix ist und im Folgenden nicht mehr aufgeführt wird. Die Matrizen I_m bzw. I_n sind die Einheitsmatrizen, mit denen die n×m-Matrix A multipliziert werden kann, sodass I_n A I_m = A. Durch die Grundoperationen, die beliebig oft wiederholt werden können, geht die erweiterte Matrix über in

wo B die Identität B = LAR erfüllt.^:63

Die Grundoperationen werden in der erweiterten Matrix durchgeführt, d. h.

• die Zeilenoperationen werden simultan in L und B (anfangs I_n bzw. A) und
• die Spaltenoperationen simultan in B und R (anfangs A bzw. I_m) angewendet.

Beispiel: Vorgelegt ist die Matrix

${\displaystyle {\mathsf {A}}={\begin{pmatrix}1&2&3\\4&5&6\end{pmatrix}}}$.

Diese wird mit den Einheitsmatrizen in die erweiterte Matrix eingetragen:

Grundoperation 1: Spaltentausch 2 und 3 liefert

Man prüft nach:

${\displaystyle {\begin{pmatrix}1&0\\0&1\end{pmatrix}}{\begin{pmatrix}1&2&3\\4&5&6\end{pmatrix}}{\begin{pmatrix}1&0&0\\0&0&1\\0&1&0\end{pmatrix}}={\begin{pmatrix}1&3&2\\4&6&5\end{pmatrix}}}$

Grundoperation 2: Multiplikation der ersten Zeile mit Skalar a ergibt

und wieder ist

${\displaystyle {\begin{pmatrix}{\mathsf {a}}&0\\0&1\end{pmatrix}}{\begin{pmatrix}1&2&3\\4&5&6\end{pmatrix}}{\begin{pmatrix}1&0&0\\0&0&1\\0&1&0\end{pmatrix}}={\begin{pmatrix}{\mathsf {a}}&3{\mathsf {a}}&2{\mathsf {a}}\\4&6&5\end{pmatrix}}}$

Grundoperation 3: Subtraktion der mit ⁴⁄_a multiplizierten ersten Zeile von der zweiten ergibt

entsprechend

${\displaystyle {\begin{pmatrix}{\mathsf {a}}&0\\-4&1\end{pmatrix}}{\begin{pmatrix}1&2&3\\4&5&6\end{pmatrix}}{\begin{pmatrix}1&0&0\\0&0&1\\0&1&0\end{pmatrix}}={\begin{pmatrix}{\mathsf {a}}&3{\mathsf {a}}&2{\mathsf {a}}\\0&-6&-3\end{pmatrix}}}$

Gauß’sches Eliminationsverfahren

Das Ziel der Äquivalenztransformation einer Matrix A ist beim Gauß’schen Eliminationsverfahren die Identität

PA = LR

mit Permutationsmatrix P, normierter unterer Dreiecksmatrix L und oberer Dreiecksmatrix R. Für das Generalschema einer Äquivalenztransformation wird das umgeformt in

PAS = L

mit der oberen Dreiecksmatrix S = R⁻¹. Die erweiterte Matrix im Generalschema soll entsprechend

werden. Diese Struktur wird erreicht, indem

1. die Permutationen sich auf Zeilenoperationen beschränken,
2. die Überführung in Dreiecksform mit Linearkombinationen ausschließlich der Spalten geschieht, und
3. die Normierung der unteren Dreiecksmatrix L am Schluss durch Multiplikation der Spalten erfolgt.

Im zweiten Schritt entsteht eine Absteigende Folge von Elevatoren mit ihren günstigen Eigenschaften nur dann, wenn die Linearkombinationen der Spalten ohne Unterbrechung durch Spaltentausch oder Spaltenmultiplikation durchgeführt werden.

Beispiel:

Die Gleichung

${\displaystyle {\begin{pmatrix}0&3&2&2\\-1&-1&-1&-1\\3&6&3&-3\\7&-5&1&6\end{pmatrix}}{\begin{pmatrix}x_{1}\\x_{2}\\x_{3}\\x_{4}\end{pmatrix}}={\begin{pmatrix}20\\-10\\12\\24\end{pmatrix}}={\mathsf {b}}}$

ist zu lösen. Das Generalschema führt in fünf Schritten auf die gewünschte Form (Pivots kursiv hervorgehoben):

Die Zeilen z_1,2,3 entsprechen drei Zeilenelevatoren ρ_1,2,3 und die Normierung mit den Einträgen in d entspricht in ihrer Wirkung einer Diagonalmatrix D = diag(d). Die Matrix S ergibt sich aus deren Produkt:

S = ρ₁ρ₂ρ₃D    →   S⁻¹ = R = D⁻¹(ρ₁ρ₂ρ₃)⁻¹

Die Inverse des Klammerausdrucks, der eine Absteigende Folge von Elevatoren enthält, kann sofort aufgeschrieben werden: Die Zeilen z_1,2,3 werden mit umgekehrtem Vorzeichen in eine 4×4-Nullmatrix übertragen, sodass die kursiv hervor gehobenen Pivots auf deren Hauptdiagonale liegen, und die Hauptdiagonale mit Einsen belegt. Es entsteht die Inverse des Klammerausdrucks

${\displaystyle (\rho _{1}\rho _{2}\rho _{3})^{-1}={\begin{pmatrix}1&1&1&1\\&1&0&-2\\&&1&4\\&&&1\end{pmatrix}}}$

Mit ihr und der Diagonalmatrix mit den Kehrwerten aus d, die die Zeilen dieser Inversen skalieren, berechnet sich

${\displaystyle {\mathsf {S}}^{-1}={\mathsf {R}}={\begin{pmatrix}-1&&&\\&3&&\\&&2&\\&&&-1\end{pmatrix}}{\begin{pmatrix}1&1&1&1\\&1&0&-2\\&&1&4\\&&&1\end{pmatrix}}={\begin{pmatrix}-1&-1&-1&-1\\&3&0&-6\\&&2&8\\&&&-1\end{pmatrix}}}$

Damit lautet das Gauß’sche Eliminationsverfahren in Matrixform:

${\displaystyle \underbrace {\begin{pmatrix}0&1&&\\&0&1&\\1&&0&\\&&&1\end{pmatrix}} _{\mathsf {P}}\underbrace {\begin{pmatrix}0&3&2&2\\-1&-1&-1&-1\\3&6&3&-3\\7&-5&1&6\end{pmatrix}} _{\mathsf {A}}=\underbrace {\begin{pmatrix}1&&&\\-3&1&&\\0&1&1&\\-7&-4&-3&1\end{pmatrix}} _{\mathsf {L}}\underbrace {\begin{pmatrix}-1&-1&-1&-1\\&3&0&-6\\&&2&8\\&&&-1\end{pmatrix}} _{\mathsf {R}}}$

Das vorliegende Problem Ax = b wird mit P multipliziert, resultierend in PAx = Pb, und PA = LR eingesetzt: LRx = Pb. Aus Ly = Pb = (-10 12 20 24)^⊤ ergibt sich y = (-10 -18 38 -4)^⊤ durch Vorwärtseinsetzen und Rx = y liefert durch Rückwärtseinsetzen die Lösung x = (1 2 3 4)^⊤.

Die Lösung kann abgekürzt werden, indem auf die geordnete Dreiecksstruktur von R und L verzichtet wird und A in eine Pivotmatrix transformiert wird, was in drei Schritten gelingt:

Die links der erweiterten Matrix stehenden Spalten und die unter der erweiterten Matrix stehenden Zeilen bilden je eine Absteigende Folge von Elevatoren, sodass die Produkte der Elevatoren S bzw. T einfach zu invertieren sind. Nämlich durch Eintrag dieser Spalten bzw. Zeilen mit umgekehrtem Vorzeichen in eine Nullmatrix, sodass die kursiv geschriebenen Pivots auf der Hauptdiagonale zu liegen kommen, und abschließende Belegung der Hauptdiagonalen mit Einsen. Mit L = S⁻¹ sowie R = T⁻¹ entsteht

SAT = Π → A = LΠR

oder ausgeschrieben

${\displaystyle {\mathsf {A}}=\underbrace {\begin{pmatrix}1&0&1&0\\0&1&0&0\\0&-3&1&0\\-3&-7&-4&1\end{pmatrix}} _{\mathsf {L}}\underbrace {\begin{pmatrix}0&0&2&0\\-1&0&0&0\\0&3&0&0\\0&0&0&-1\end{pmatrix}} _{\mathsf {\Pi }}\underbrace {\begin{pmatrix}1&1&1&1\\0&1&0&-2\\0&0&1&4\\0&0&0&1\end{pmatrix}} _{\mathsf {R}}}$

Vorwärtseinsetzen in Lz = b in der Reihenfolge 2,1,3,4 ergibt den Vektor z = (38 -10 -18 -4)^⊤, Πy = z liefert y = (10 -6 19 4)^⊤ und Rx = y schließlich durch Rückwärtseinsetzen die Lösung x = (1 2 3 4)^⊤.

Die Form A = LΠR kann bei manueller Rechnung leichter mit dem Algorithmus von Banachiewicz berechnet werden, der vor der Erfindung der Computer dem hier gezeigten Algorithmus überlegen war.^:82

Gauß-Jordan-Algorithmus

Beim Gauß-Jordan-Algorithmus werden in der erweiterten Matrix im Generalschema einer Äquivalenztransformation

nur zwei Felder benutzt,

Im ersten Fall müssen die Spalten von L, im zweiten die Zeilen von R linear unabhängig sein, damit eine Transformation in eine Pivotmatrix gelingen kann. Der Algorithmus ist mit einem Risiko behaftet und muss ergebnislos abgebrochen oder irgendwie anders weitergeführt werden, wenn die lineare Unabhängigkeit nicht gegeben ist und infolge dessen während der Rechnung eine Nullspalte bzw. Nullzeile auftritt.

Anders als im Gauß’schen Eliminationsverfahren sind die signifikanten Spalten bzw. Zeilen der Elevatoren im Allgemeinen voll besetzt.^:83

Eigenspalten und Eigenzeilen einer singulären Matrix

Eine singuläre Matrix hat den Eigenwert null und alle Vektoren, die von der Matrix auf den Nullvektor abgebildet werden, erzeugen den Eigenraum zum Eigenwert null. Eine Vektorraumbasis zu diesem Eigenraum kann mit dem Generalschema einer Äquivalenztransformation ermittelt werden. Dieses eignet sich allgemeiner zur Berechnung aller Vektoren, die von einer beliebigen, auch nicht-quadratischen Matrix auf einen Nullvektor abgebildet werden.

Die n×m-Matrix A wird dazu mit Nullenkreuzen in eine Pivotmatrix Π überführt:^:107

LAR = Π

Eine Nullzeile von Π ist eine Zeile, die nur aus Nullen besteht, und eine Nullspalte eine nur aus Nullen bestehende Spalte von Π:

In der erweiterten Matrix oben ist ein Beispiel mit zwei Nullzeilen und drei Nullspalten aufgeführt, die gelb unterlegt sind. In den grau unterlegten Feldern von Π ist in jeder Zeile und Spalte genau ein Element ungleich null vorhanden. Ist wie oben die i-te Zeile Nullzeile, dann ist Π_ik = 0 für k = 1,…,m. Der Vektor e_i der Standardbasis wird dann in den Nullvektor o überführt:

e_i^⊤Π = e_i^⊤LAR = o^⊤

Multiplikation von rechts mit R⁻¹ liefert mit l_i := e_i^⊤L:

e_i^⊤LA = l_i A = o^⊤

Das heißt, dass die i-te Zeile l_i von L Linkseigenvektor von A zum Eigenwert null ist. Rechtsmultiplikation von LAR = Π mit dem Vektor e_α der Standardbasis und Linksmultiplikation mit L⁻¹ liefert analog

ARe_α =: Ar_α = o

wenn die α-te Spalte von Π, wie im obigen Beispiel, eine Nullspalte ist. Der Vektor r_α ist die α-te Spalte von R und Rechtseigenvektor von A zum Eigenwert null. Wenn r der Rang von A ist, dann besitzt die n×m-Matrix A zum Eigenwert null n−r Linkseigenvektoren und m−r Rechtseigenvektoren. Diese werden Eigenzeilen bzw. Eigenspalten von A genannt und sind jeweils unter sich linear unabhängig, weil die Einheitsvektoren der Standardbasen es sind. Die Gesamtheit der Eigenzeilen spannt einen Links­eigenraum (auch Linksnullraum oder Zeilen­kern) der Dimension n−r und die Gesamtheit der Eigenspalten einen Rechtseigenraum (auch Rechtsnullraum oder Spaltenkern) der Dimension m−r auf.^:107 Diese Räume enthalten alle Vektoren, die von A in Nullvektoren transformiert werden.

Beispiel:

Vorgelegt ist die Matrix

${\displaystyle {\mathsf {A}}={\begin{pmatrix}48&-24&-6\\-8&4&1\\-144&72&18\end{pmatrix}}}$

Sie wird mit einem Nullenkreuz zur Pivotmatrix:

In der Pivotmatrix Π sind die Zeilen eins und drei Nullzeilen und die Spalten eins und zwei Nullspalten. Die Identitäten

(1 6 0)A	= (0 -18 1)A	= (0 0 0)
A(1 0 8)⊤	= A(0 1 -4)⊤	= (0 0 0)⊤

sind unschwer nachzuprüfen. Alle Vektoren u und v, die von A vermöge

uA = (0 0 0)   bzw.    Av = (0 0 0)^⊤

in Nullvektoren abgebildet werden, besitzen die Form

u = α(1 6 0) + β(0 -18 1)   und    v = α(1 0 8)^⊤ + β(0 1 -4)^⊤

mit irgendwelchem α, β ∈ ℝ.

Ermittlung des Ranges einer Matrix

Eine n×m-Matrix A kann durch Nullenkreuze in eine Pivotmatrix Π überführt werden:

LAR = Π

Die Anzahl der von null verschiedenen Einträge in Π ist gleich dem Rang r der Matrix und die Transformation in die Pivotmatrix benötigt höchstens r Nullenkreuze.^:75f Mit den Grundoperationen Permutation und Multiplikation mit einem Skalar kann die Pivotmatrix in die Normalform

überführt werden, die in der oberen linken Ecke die Einheitsmatrix I_r vom Rang r und sonst nur Nullen enthält.^:66 Ein Beispiel zur Berechnung der Pivotmatrix findet sich hier im Abschnitt Eigenspalten und Eigenzeilen einer singulären Matrix und bei Rang einer Matrix / Normalform.