Äquivalenztransformation
# Äquivalenztransformation

Die Äquivalenztransformation oder reguläre Transformation von Matrizen ist in der linearen Algebra die Transformation einer Matrix A in eine Äquivalente Matrix B durch invertierbare Matrizen L und R $vermöge^{:56}$

    LAR = B

Ist die Matrix A eine hermitesche Matrix und soll auch B es sein, sind R und L hermitesch zueinander zu wählen. Die Äquivalenztransformation geht dann über in den Spezialfall der $Kongruenz­transformation^{:56}$

    $LAL^H$ = B oder im Reellen $LAL^⊤$ = B

Eine Äquivalenztransformation kann praktisch in einer erweiterten Matrix mit drei Matrizen und bestimmten Grund- oder Elementaroperationen der Spalten- und Zeilen der Matrizen durchgeführt $werden.^{:56}^{:59}$

Von zentraler Bedeutung ist die Überführung von Matrizen in eine Pivotmatrix, die in jeder Spalte und Zeile höchstens einen von null verschiedenen Eintrag aufweist. Die Einheits-, Diagonal- und Permutationsmatrizen sind Pivotmatrizen; diese müssen jedoch weder quadratisch noch invertierbar sein. Die Anzahl der von null verschiedenen Einträge in einer Pivotmatrix entspricht ihrem $Rang.^{:75}$

Die Äquivalenztransformation ist Grundlage für das Gauß’sche Eliminationsverfahren und den Gauß-Jordan-Algorithmus und sie ist dienlich bei der Ermittlung des Ranges einer Matrix sowie der Eigenspalten und Eigenzeilen einer singulären Matrix.

Sind bei gegebenen A die Matrizen LBR = A mit einer Pivotmatrix B gesucht, dann empfiehlt sich der Algorithmus von Banachiewicz.

## Eigenschaften

Gegeben sei ein Körper K, meist ℝ oder ℂ, auf dem die n×m-Matrizen A und B, sowie die n×n-Matrix L und m×m-Matrix R – L und R invertierbar – definiert sind. Jede reguläre Transformation

    LAR = B

lässt sich multiplikativ aus drei Grundoperationen zusammensetzen, die sich entweder auf die Spalten von R und B oder die Zeilen von L und B $auswirken.^{:56ff}$ Bei manueller Durchführung im Generalschema einer Äquivalenztransformation werden die Matrizen in einer erweiterten Matrix angeordnet und die Operationen auf diese Matrix angewendet. Ausgangspunkt ist oft, dass L und R Einheitsmatrizen sind und B mit A initialisiert wird. Ziel der Operationen kann sein, die Matrix B in eine Dreiecksmatrix, eine Pivotmatrix oder eine angestrebte Normalform einer Matrix umzuwandeln.

### 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_1T_2…T_k$ bzw. L" = $T_kT_{k-1}…T_1L$

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"^{−1}$ das Produkt der Inversen in der Reihenfolge ihres Auftretens und $R'^{−1}$ 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:

    $ρ^{−1}$ = $I_m$ − $e_j$ $p_j^⊤$

Denn wegen 0 = $p_{jj}$ = $p_j^⊤e_j$ ist

    $ρρ^{−1}$ = $(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^⊤$ → $λ^{−1}$ = $I_n$ − $q_j$ $e_j^⊤$

wo nun der $K^n$ 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.

**Vollständige Systeme von Elevatoren**

Zeilenelevatoren (der Dimension m) bilden ein vollständiges System, wenn die Matrix mit ihren signifikanten Zeilen die folgende Form $annimmt:^{:67}$

    ${\mathsf {R}}:=I_{m}+\sum _{j=1}^{m}e_{j}p_{j}^{\top }=I_{m}+{\begin{pmatrix}p_{1}^{\top }\\p_{2}^{\top }\\\vdots \\p_{m}^{\top }\end{pmatrix}}={\begin{pmatrix}1&p_{12}&p_{13}&\dots &p_{1m}\\p_{21}&1&p_{23}&\dots &p_{2m}\\p_{31}&p_{32}&1&\dots &p_{3m}\\\vdots &\vdots &\vdots &\ddots &\vdots \\p_{m1}&p_{m2}&p_{m3}&\dots &1\end{pmatrix}}$

Ein solches System fällt im Generalschema einer Äquivalenztransformation an, wenn

* jede Spalte höchstens einmal Pivotspalte ist und
* die Linearkombinationen der Spalten direkt aufeinander folgen, ohne von Spaltenmultiplikationen oder -umordnungen unterbrochen worden zu sein.

Gleiches gilt für ein vollständiges System von Spaltenelevatoren (der Dimension n):

    ${\mathsf {L}}:=I_{n}+\sum _{j=1}^{n}q_{j}e_{j}^{\top }=I_{n}+{\begin{pmatrix}q_{1}&q_{2}&\dots &q_{n}\end{pmatrix}}={\begin{pmatrix}1&q_{21}&q_{31}&\dots &q_{n1}\\q_{12}&1&q_{32}&\dots &q_{n2}\\q_{13}&q_{23}&1&\dots &q_{n3}\\\vdots &\vdots &\vdots &\ddots &\vdots \\q_{1n}&q_{2n}&q_{3n}&\dots &1\end{pmatrix}}$

Einzelne oder mehrere der $p_{j}$ oder $q_{j}$ können Nullvektoren sein, die Zeilen von R bzw. die Spalten von L also nur die Eins auf der Hauptdiagonalen und sonst nur Nullen aufweisen. Im Extremfall sind alle Nebendiagonalglieder null und R oder L gleich einer Einheitsmatrix.

**Absteigende Folge von Elevatoren**

Ein vollständiges System von Zeilenelevatoren bildet eine absteigende Folge von Zeilenelevatoren, wenn es eine Permutationsmatrix P gibt, sodass für die Matrix R des vorangegangenen Abschnitts

    P R $P^⊤$ = P $[I_m$ + $(p_1$ $p_2$ … $p_m)^⊤]$ $P^⊤$

eine normierte obere Dreiecksmatrix ist. Dann $gilt:^{:68}$

* die Hauptdiagonalen aller Elevatoren bestehen nur aus Einsen (entsprechend $p_{jj}$ = 0),
* für jedes j = 1,…,m gibt es einen Elevator mit mindestens j−1 Nullen in seiner signifikanten Zeile, und
* es gibt einen Nachfolger, der in seiner signifikanten Zeile mindestens j−1 Nullen an denselben Stellen wie sein Vorgänger hat.

Eine solche Folge von Zeilenelevatoren entsteht bei der Überführung einer Matrix in eine Pivotmatrix mittels r Nullenkreuzen, wo r immer kleiner oder gleich dem Rang der Matrix ist. Die absteigende Folge eines vollständigen Systems von Spaltenelevatoren entspricht einer normierten unteren Dreiecksmatrix und weist analog verteilte Nullen in ihren Spalten auf.

Das Produkt eines vollständigen Systems absteigender Elevatoren braucht nicht durch Matrizenmultiplikation berechnet zu werden, sondern ergibt sich durch Übertrag der signifikanten Zeilen bzw. Spalten in eine Matrix, was formal mittels der Standardbasis $e_{1,…,m/n}$ erfolgen $kann:^{:68}$

    ${\mathsf {R}}=\prod _{k=m}^{1}\rho _{k}=\prod _{k=m}^{1}({\mathsf {I}}_{m}+e_{i_{k}}p_{i_{k}}^{\top })={\mathsf {I}}_{m}+\sum _{k=m}^{1}e_{i_{k}}p_{i_{k}}^{\top }={\mathsf {I}}_{m}+\sum _{k=1}^{m}e_{k}p_{k}^{\top }$ bzw. ${\mathsf {L}}=\prod _{k=1}^{n}\lambda _{k}=\prod _{k=1}^{n}({\mathsf {I}}_{n}+q_{j_{k}}e_{j_{k}}^{\top })={\mathsf {I}}_{n}+\sum _{k=1}^{n}q_{j_{k}}e_{j_{k}}^{\top }={\mathsf {I}}_{n}+\sum _{k=1}^{n}q_{k}e_{k}^{\top }$

wo $\{i_{1},\dots ,i_{m}\}$ eine Permutation von $\{1,\dots ,m\}$ und $\{j_{1},\dots ,j_{n}\}$ eine solche von $\{1,\dots ,n\}$ ist. Hierbei ist zu beachten:

* Die Reihenfolge der Zeilenelevatoren $\rho _{k}$ im Produkt ist umgekehrt als bei den Spaltenelevatoren $λ_k.$ Grund hierfür ist, dass obige Gleichungen durch Transponierung und Austausch von n und m in einander übergehen.
* Im Generalschema einer Äquivalenztransformation entstehen die Produkte in der umgekehrten Reihenfolge: R = $ρ_1ρ_2…ρ_m$ und L = $λ_nλ_{n-1}…λ_1.$
* Die Inverse der Matrix R kann wie folgt in einfacher Weise ermittelt werden: Eine $Phantommatrix^{:78}$ M wird mit der Nullmatrix initialisiert, die signifikanten Zeilen $p_j^⊤$ mit umgekehrtem Vorzeichen in die j-te Zeile von M eingetragen und die Hauptdiagonale von M mit Einsen belegt. Dann enthält M am Schluss die Inverse: $R^{−1}$ = M. Entsprechend kann die Inverse von L sofort angegeben werden, wenn die signifikanten Spalten $q_k$ mit umgekehrtem Vorzeichen in den Spalten der Phantommatrix notiert werden und die Hauptdiagonale von M ebenso mit Einsen belegt wird.

**Beispiel**

Die Zeilenelevatoren

    $\rho _{1}={\begin{pmatrix}1&0&0\\\color {green}3&\color {green}1&\color {green}9\\0&0&1\end{pmatrix}},\;\rho _{2}={\begin{pmatrix}1&0&0\\0&1&0\\\color {red}6&\color {red}0&\color {red}1\end{pmatrix}},\;\rho _{3}={\begin{pmatrix}\color {blue}1&\color {blue}0&\color {blue}0\\0&1&0\\0&0&1\end{pmatrix}}$

bilden eine vollständige absteigende Folge, denn

* ihre farbig markierten signifikanten Zeilen $z_{1,2,3},$ mit einer 1 in den Spalten eins, zwei bzw. drei, lassen sich in einer quadratischen Matrix ${\mathsf {R}}=\textstyle {\begin{pmatrix}\color {blue}{z_{1}}\\\color {green}{z_{2}}\\\color {red}{z_{3}}\end{pmatrix}}$ anordnen, die nur Einsen auf der Hauptdiagonalen hat,
* $z_2$ besitzt keine Null, $z_3$ eine und $z_1$ zwei, und
* $z_1$ und $z_3$ haben eine Null an derselben Stelle (in Spalte 2)

Die Permutationsmatrix ${\mathsf {P}}=\textstyle {\begin{pmatrix}0&1&0\\0&0&1\\1&0&0\end{pmatrix}}$ transformiert R vermöge $PRP^⊤$ in eine normierte obere Dreiecksmatrix. Der Unterschied zwischen den Zeilen $z_j$ und $p_j$ ist, dass $z_{jj}$ = 1 und $p_{jj}$ = 0 ist, daher auch die unterschiedliche Bezeichnung. Das Produkt der Elevatoren in umgekehrter Reihenfolge lautet

    $\rho _{3}\rho _{2}\rho _{1}=(I_{3}+e_{1}p_{1}^{\top })(I_{3}+e_{3}p_{3}^{\top })(I_{3}+e_{2}p_{2}^{\top })=I_{3}+\sum _{k=1}^{3}e_{k}p_{k}^{\top }={\mathsf {R}}={\begin{pmatrix}\color {blue}1&\color {blue}0&\color {blue}0\\\color {green}3&\color {green}1&\color {green}9\\\color {red}6&\color {red}0&\color {red}1\end{pmatrix}}$

Die Inverse des ersten Elevators ist beispielsweise

    $\rho _{1}^{-1}=(I_{3}+e_{2}p_{2}^{\top })^{-1}=I_{3}-e_{2}p_{2}^{\top }={\begin{pmatrix}1&&\\&1&\\&&1\end{pmatrix}}-{\begin{pmatrix}0\\1\\0\end{pmatrix}}{\begin{pmatrix}3&0&9\end{pmatrix}}={\begin{pmatrix}1&0&0\\-3&1&-9\\0&0&1\end{pmatrix}}$

und die Inverse des Produkts der Elevatoren lautet:

    $(\rho _{1}\rho _{2}\rho _{3})^{-1}=\rho _{3}^{-1}\rho _{2}^{-1}\rho _{1}^{-1}={\begin{pmatrix}\color {blue}1&\color {blue}0&\color {blue}0\\\color {green}-3&\color {green}1&\color {green}-9\\\color {red}-6&\color {red}0&\color {red}1\end{pmatrix}}$

Die Spaltenelevatoren

    $\lambda _{1}={\begin{pmatrix}1&\color {green}3&0\\0&\color {green}1&0\\0&\color {green}9&1\end{pmatrix}},\;\lambda _{2}={\begin{pmatrix}1&0&\color {red}6\\0&1&\color {red}0\\0&0&\color {red}1\end{pmatrix}},\;\lambda _{3}={\begin{pmatrix}\color {blue}1&0&0\\\color {blue}0&1&0\\\color {blue}0&0&1\end{pmatrix}}$

haben vergleichbare Eigenschaften, denn sie bilden wegen $q_{1,2,3}=p_{1,2,3}$ ebenso eine vollständige absteigende Folge wie die Zeilenelevatoren oben. Das Produkt der Spaltenelevatoren lautet

    $\lambda _{1}\lambda _{2}\lambda _{3}=(I_{3}+q_{2}e_{2}^{\top })(I_{3}+q_{3}e_{3}^{\top })(I_{3}+q_{1}e_{1}^{\top })=I_{3}+\sum _{k=1}^{3}q_{k}e_{k}^{\top }={\begin{pmatrix}\color {blue}1&\color {green}3&\color {red}6\\\color {blue}0&\color {green}1&\color {red}0\\\color {blue}0&\color {green}9&\color {red}1\end{pmatrix}}$

und die Inverse des umgekehrten Produkts entsteht auch hier durch Vorzeichenumkehr der Nebendiagonalglieder:

    $(\lambda _{3}\lambda _{2}\lambda _{1})^{-1}=\lambda _{1}^{-1}\lambda _{2}^{-1}\lambda _{3}^{-1}={\begin{pmatrix}\color {blue}1&\color {green}-3&\color {red}-6\\\color {blue}0&\color {green}1&\color {red}0\\\color {blue}0&\color {green}-9&\color {red}1\end{pmatrix}}$

Diese Tatsachen können insbesondere im Gauß-Jordan-Algorithmus ausgenutzt werden. Die Matrizen in den für die Spaltenelevatoren aufgeschriebenen Gleichungen gehen durch Transposition (sowie Namenstausch $λ^⊤,q$ ↔ ρ,p) aus denen für die Zeilenelevatoren hervor und umgekehrt.

## Wichtige Konfigurationen

### 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:

| $q_{1j}$ | $A_{11}$ | … | $A_{1j}$ | … | $A_{1l}$ | … | $A_{1m}$ | A | → | $B_{11}$ | … | $B_{1j}$ | … | $B_{1l}$ | … | $B_{1m}$ | B |
| - | - | - | - | - | - | - | - | - | - | - | - | - | - | - | - | - | - |
| ︙ | ︙ | | ︙ | | ︙ | | ︙ | A | → | ︙ | | ︙ | | ︙ | | ︙ | B |
| $q_{kj}$ | $A_{k1}$ | … | $A_{kj}$ | … | $A_{kl}$ | … | $A_{km}$ | A | → | $B_{k1}$ | … | $B_{kj}$ | … | $B_{kl}$ | … | $B_{km}$ | B |
| ︙ | ︙ | | ︙ | | ︙ | | ︙ | A | → | ︙ | | ︙ | | ︙ | | ︙ | B |
| 1 | $A_{i1}$ | … | $A_{ij}$ | … | $A_{il}$ | … | $A_{im}$ | A | → | $B_{i1}$ | … | $A_{ij}$ | … | $B_{il}$ | … | $B_{im}$ | B |
| ︙ | ︙ | | ︙ | | ︙ | | ︙ | A | → | ︙ | | ︙ | | ︙ | | ︙ | B |
| $q_{nj}$ | $A_{n1}$ | … | $A_{nj}$ | … | $A_{nl}$ | … | $A_{nm}$ | A | → | $B_{n1}$ | … | $B_{nj}$ | … | $B_{nl}$ | … | $B_{nm}$ | B |
| | $p_{i1}$ | … | 1 | … | $p_{il}$ | … | $p_{im}$ | | → | | | | | | | |

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

    ${\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:

| $q_{12}$ | 1 | 2 | 3 | A | → | $B_{11}$ | 7 | $B_{13}$ | B |
| - | - | - | - | - | - | - | - | - | - |
| 1 | 4 | 5 | 6 | A | → | -6 | 5 | 1 | B |
| | $p_{21}$ | 1 | $p_{23}$ | | → | | | |

Der Faktor $q_{12}$ berechnet sich zu

    $q_{12}$ = $(B_{12}$ - $A_{12})/A_{22}$ = (7 - 2)/5 = 1

Die Faktoren $p_{21}$ und $p_{23}$ ergeben sich aus

    $p_{21}$ = $(B_{21}$ - $A_{21})/A_{22}$ = (-6 - 4)/5 = -2
    $p_{23}$ = $(B_{23}$ - $A_{23})/A_{22}$ = (1 - 6)/5 = -1

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

    $\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

    $\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

    $\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:

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

bzw.

    $\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:

| $q_{1j}$ | $A_{11}$ | … | $A_{1j}$ | … | $A_{1l}$ | … | $A_{1m}$ | A | → | $B_{11}$ | … | 0 | … | $B_{1l}$ | … | $B_{1m}$ | B |
| - | - | - | - | - | - | - | - | - | - | - | - | - | - | - | - | - | - |
| ︙ | ︙ | | ︙ | | ︙ | | ︙ | A | → | ︙ | | ︙ | | ︙ | | ︙ | B |
| $q_{kj}$ | $A_{k1}$ | … | $A_{kj}$ | … | $A_{kl}$ | … | $A_{km}$ | A | → | $B_{k1}$ | … | 0 | … | $B_{kl}$ | … | $B_{km}$ | B |
| ︙ | ︙ | | ︙ | | ︙ | | ︙ | A | → | ︙ | | ︙ | | ︙ | | ︙ | B |
| 1 | $A_{i1}$ | … | $A_{ij}$ | … | $A_{il}$ | … | $A_{im}$ | A | → | 0 | … | $A_{ij}$ | … | 0 | … | 0 | B |
| ︙ | ︙ | | ︙ | | ︙ | | ︙ | A | → | ︙ | | ︙ | | ︙ | | ︙ | B |
| $q_{nj}$ | $A_{n1}$ | … | $A_{nj}$ | … | $A_{nl}$ | … | $A_{nm}$ | A | → | $B_{n1}$ | … | 0 | … | $B_{nl}$ | … | $B_{nm}$ | B |
| | $p_{i1}$ | … | 1 | … | $p_{il}$ | … | $p_{im}$ | | → | | | | | | | |

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

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

mit Rang zwei und das erste gelb markierte Nullenkreuz

| $q_{12}$ | 1 | 2 | 3 | A | → | $B_{11}$ | 0 | $B_{13}$ | B |
| - | - | - | - | - | - | - | - | - | - |
| 1 | 4 | 5 | 6 | A | → | 0 | 5 | 0 | B |
| | $p_{21}$ | 1 | $p_{23}$ | | → | | | |

Man liest ab $q_{12}=-^2⁄_5,$ $p_{21}=-^4⁄_5$ und $p_{23}=-^6⁄_5$ mit den Elevatoren

    $\lambda _{1}={\begin{pmatrix}1&{\mathsf {q}}_{12}\\0&1\end{pmatrix}}={\begin{pmatrix}1&-2/5\\0&1\end{pmatrix}}$
    $\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

    ${\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

| 1 | $^{-3}⁄_5$ | 0 | $^3⁄_5$ | B | → | $^{-3}⁄_5$ | 0 | 0 | B' |
| - | - | - | - | - | - | - | - | - | - |
| $q_{21}$ | 0 | 5 | 0 | B | → | 0 | 5 | 0 | B' |
| | 1 | $p_{12}$ | $p_{13}$ | | → | | | |

das das alte unberührt lässt. Mit $q_{21}$ = $p_{12}$ = 0 und $p_{13}$ = 1 entstehen die Elevatoren

    $\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

    ${\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

    ${\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

    ${\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:

    ${\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/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

    ${\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

| p  0  2+i   A 1   2−i  0 1 p | → | 1   $B_{12}$   B $B_{12}$ 0 |
| - | - | - |

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

    $B_{11}$ = 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

    ${\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_{11}$ = 1 und den Faktoren $q_{21}$ = -2 + i bzw. $p_{12}$ = −2 − i und dem Endergebnis

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

### Generalschema einer Äquivalenztransformation

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

| $I_n$ | A |
| - | - |
| O | $I_m$ |

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

| L | B |
| - | - |
| | R |

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

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

Diese wird mit den Einheitsmatrizen in die erweiterte Matrix eingetragen:

| | 1 | 2 | 3 |
| - | - | - | - |
| 1 | 4 | 5 | 6 |
| | 1 | | |
| | | 1 | |
| | | | 1 |

Grundoperation 1: Spaltentausch 2 und 3 liefert

| | 1 | 3 | 2 |
| - | - | - | - |
| 1 | 4 | 6 | 5 |
| | 1 | | |
| | | | 1 |
| | | 1 | |

Man prüft nach:

    ${\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

| | a | 3a | 2a |
| - | - | - | - |
| 1 | 4 | 6 | 5 |
| | 1 | | |
| | | | 1 |
| | | 1 | |

und wieder ist

    ${\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 $^4⁄_a$ multiplizierten ersten Zeile von der zweiten ergibt

| a | | a | 3a | 2a |
| - | - | - | - | - |
| -4 | 1 | 0 | -6 | -3 |
| | | 1 | | |
| | | | | 1 |
| | | | 1 | |

entsprechend

    ${\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}}$

## Anwendungen

### 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^{−1}.$ Die erweiterte Matrix im Generalschema soll entsprechend

| P | L |
| - | - |
| | S |

werden. Diese Struktur wird erreicht, indem

* die Permutationen sich auf Zeilenoperationen beschränken,
* die Überführung in Dreiecksform mit Linearkombinationen ausschließlich der Spalten geschieht, und
* 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

    ${\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):

| | Reduktion Zeile 2, Zeilentausch 1↔2 | Reduktion Zeile 2, Zeilentausch 1↔2 | Reduktion Zeile 2, Zeilentausch 1↔2 | Reduktion Zeile 2, Zeilentausch 1↔2 | Reduktion Zeile 2, Zeilentausch 1↔2 | Reduktion Zeile 2, Zeilentausch 1↔2 | Reduktion Zeile 2, Zeilentausch 1↔2 | Reduktion Zeile 2, Zeilentausch 1↔2 |
| - | - | - | - | - | - | - | - | - |
| ↗ | 1 | 0 | 0 | 0 | 0 | 3 | 2 | 2 |
| → | 0 | 1 | 0 | 0 | -1 | -1 | -1 | -1 |
| | 0 | 0 | 1 | 0 | 3 | 6 | 3 | -3 |
| | 0 | 0 | 0 | 1 | 7 | -5 | 1 | 6 |
| | | | | | 1 | 0 | 0 | 0 |
| | | | | | 0 | 1 | 0 | 0 |
| | | | | | 0 | 0 | 1 | 0 |
| | | | | | 0 | 0 | 0 | 1 |
| | $z_1$ = | $z_1$ = | $z_1$ = | $z_1$ = | 1 | -1 | -1 | -1 |
| | Reduktion Zeile 3, Zeilentausch 2↔3 | Reduktion Zeile 3, Zeilentausch 2↔3 | Reduktion Zeile 3, Zeilentausch 2↔3 | Reduktion Zeile 3, Zeilentausch 2↔3 | Reduktion Zeile 3, Zeilentausch 2↔3 | Reduktion Zeile 3, Zeilentausch 2↔3 | Reduktion Zeile 3, Zeilentausch 2↔3 | Reduktion Zeile 3, Zeilentausch 2↔3 |
| | 0 | 1 | 0 | 0 | -1 | 0 | 0 | 0 |
| ↗ | 1 | 0 | 0 | 0 | 0 | 3 | 2 | 2 |
| → | 0 | 0 | 1 | 0 | 3 | 3 | 0 | -6 |
| | 0 | 0 | 0 | 1 | 7 | -12 | -6 | -1 |
| | | | | | 1 | -1 | -1 | -1 |
| | | | | | 0 | 1 | 0 | 0 |
| | | | | | 0 | 0 | 1 | 0 |
| | | | | | 0 | 0 | 0 | 1 |
| | $z_2$ = | $z_2$ = | $z_2$ = | $z_2$ = | 0 | 1 | 0 | 2 |
| | Reduktion Zeile 3 | Reduktion Zeile 3 | Reduktion Zeile 3 | Reduktion Zeile 3 | Reduktion Zeile 3 | Reduktion Zeile 3 | Reduktion Zeile 3 | Reduktion Zeile 3 |
| | 0 | 1 | 0 | 0 | -1 | 0 | 0 | 0 |
| | 0 | 0 | 1 | 0 | 3 | 3 | 0 | 0 |
| → | 1 | 0 | 0 | 0 | 0 | 3 | 2 | 8 |
| | 0 | 0 | 0 | 1 | 7 | -12 | -6 | -25 |
| | | | | | 1 | -1 | -1 | -3 |
| | | | | | 0 | 1 | 0 | 2 |
| | | | | | 0 | 0 | 1 | 0 |
| | | | | | 0 | 0 | 0 | 1 |
| | $z_3$ = | $z_3$ = | $z_3$ = | $z_3$ = | 0 | 0 | 1 | -4 |
| Normierung | Normierung | Normierung | Normierung | Normierung | Normierung | Normierung | Normierung |
| 0 | 1 | 0 | 0 | -1 | 0 | 0 | 0 |
| 0 | 0 | 1 | 0 | 3 | 3 | 0 | 0 |
| 1 | 0 | 0 | 0 | 0 | 3 | 2 | 0 |
| 0 | 0 | 0 | 1 | 7 | -12 | -6 | -1 |
| | | | | 1 | -1 | -1 | 1 |
| | | | | 0 | 1 | 0 | 2 |
| | | | | 0 | 0 | 1 | -4 |
| | | | | 0 | 0 | 0 | 1 |
| d = | d = | d = | d = | -1 | 1/3 | 1/2 | -1 |
| | Endergebnis | Endergebnis | Endergebnis | Endergebnis | Endergebnis | Endergebnis | Endergebnis | Endergebnis |
| 0 | 1 | 0 | 0 | 1 | 0 | 0 | 0 | L |
| 0 | 0 | 1 | 0 | -3 | 1 | 0 | 0 | L |
| 1 | 0 | 0 | 0 | 0 | 1 | 1 | 0 | L |
| 0 | 0 | 0 | 1 | -7 | -4 | -3 | 1 | L |
| P | P | P | P | -1 | -1/3 | -1/2 | -1 |
| | | | S | 0 | 1/3 | 0 | -2 |
| | | | S | 0 | 0 | 1/2 | 4 |
| | | | S | 0 | 0 | 0 | -1 |

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 = $ρ_1ρ_2ρ_3D$ → $S^{−1}$ = R = $D^{−1}(ρ_1ρ_2ρ_3)^{−1}$

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

    $(\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

    ${\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:

    $\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:

| | Reduktion Zeile 2 und Spalte 1 | Reduktion Zeile 2 und Spalte 1 | Reduktion Zeile 2 und Spalte 1 | Reduktion Zeile 2 und Spalte 1 | Reduktion Zeile 2 und Spalte 1 | Reduktion Zeile 2 und Spalte 1 | Reduktion Zeile 2 und Spalte 1 | Reduktion Zeile 2 und Spalte 1 |
| - | - | - | - | - | - | - | - | - |
| 0 | 1 | 0 | 0 | 0 | 0 | 3 | 2 | 2 |
| 1 | 0 | 1 | 0 | 0 | -1 | -1 | -1 | -1 |
| 3 | 0 | 0 | 1 | 0 | 3 | 6 | 3 | -3 |
| 7 | 0 | 0 | 0 | 1 | 7 | -5 | 1 | 6 |
| | | | | | 1 | 0 | 0 | 0 |
| | | | | | 0 | 1 | 0 | 0 |
| | | | | | 0 | 0 | 1 | 0 |
| | | | | | 0 | 0 | 0 | 1 |
| | | | | | 1 | -1 | -1 | -1 |
| | Reduktion Zeile 3 und Spalte 2 | Reduktion Zeile 3 und Spalte 2 | Reduktion Zeile 3 und Spalte 2 | Reduktion Zeile 3 und Spalte 2 | Reduktion Zeile 3 und Spalte 2 | Reduktion Zeile 3 und Spalte 2 | Reduktion Zeile 3 und Spalte 2 | Reduktion Zeile 3 und Spalte 2 |
| -1 | 1 | 0 | 0 | 0 | 0 | 3 | 2 | 2 |
| 0 | 0 | 1 | 0 | 0 | -1 | 0 | 0 | 0 |
| 1 | 0 | 3 | 1 | 0 | 0 | 3 | 0 | -6 |
| 4 | 0 | 7 | 0 | 1 | 0 | -12 | -6 | -1 |
| | | | | | 1 | -1 | -1 | -1 |
| | | | | | 0 | 1 | 0 | 0 |
| | | | | | 0 | 0 | 1 | 0 |
| | | | | | 0 | 0 | 0 | 1 |
| | | | | | 0 | 1 | 0 | 2 |
| | Reduktion Zeile 1 und Spalte 3 | Reduktion Zeile 1 und Spalte 3 | Reduktion Zeile 1 und Spalte 3 | Reduktion Zeile 1 und Spalte 3 | Reduktion Zeile 1 und Spalte 3 | Reduktion Zeile 1 und Spalte 3 | Reduktion Zeile 1 und Spalte 3 | Reduktion Zeile 1 und Spalte 3 |
| 1 | 1 | -3 | -1 | 0 | 0 | 0 | 2 | 8 |
| 0 | 0 | 1 | 0 | 0 | -1 | 0 | 0 | 0 |
| 0 | 0 | 3 | 1 | 0 | 0 | 3 | 0 | 0 |
| 3 | 0 | 19 | 4 | 1 | 0 | 0 | -6 | -25 |
| | | | | | 1 | -1 | -1 | -3 |
| | | | | | 0 | 1 | 0 | 2 |
| | | | | | 0 | 0 | 1 | 0 |
| | | | | | 0 | 0 | 0 | 1 |
| | | | | | 0 | 0 | 1 | -4 |
| Endergebnis | Endergebnis | Endergebnis | Endergebnis | Endergebnis | Endergebnis | Endergebnis | Endergebnis |
| 1 | -3 | -1 | 0 | 0 | 0 | 2 | 0 | Π |
| 0 | 1 | 0 | 0 | -1 | 0 | 0 | 0 | Π |
| 0 | 3 | 1 | 0 | 0 | 3 | 0 | 0 | Π |
| 3 | 10 | 1 | 1 | 0 | 0 | 0 | -1 | Π |
| S | S | S | S | 1 | -1 | -1 | 1 |
| T | T | T | T | 0 | 1 | 0 | 2 |
| | | | | 0 | 0 | 1 | -4 |
| | | | | 0 | 0 | 0 | 1 |

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^{−1}$ sowie R = $T^{−1}$ entsteht

    SAT = Π → A = LΠR

oder ausgeschrieben

    ${\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

| L | B |
| - | - |
| | R |

nur zwei Felder benutzt,

| entweder | L   B | oder | B  R |
| - | - | - | - |

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 Π:

| $L_{11}$ | … | $L_{1n}$ | | | 0 | | 0 | | 0 | | | Π |
| - | - | - | - | - | - | - | - | - | - | - | - | - |
| ︙ | | ︙ | | | ︙ | | ︙ | | ︙ | | | Π |
| $L_{i1}$ | … | $L_{in}$ | 0 | … | 0 | … | 0 | … | 0 | … | 0 | Π |
| ︙ | | ︙ | | | ︙ | | ︙ | | ︙ | | | Π |
| $L_{j1}$ | … | $L_{jn}$ | 0 | … | 0 | … | 0 | … | 0 | … | 0 | Π |
| ︙ | | ︙ | | | ︙ | | ︙ | | ︙ | | | Π |
| $L_{n1}$ | … | $L_{nn}$ | | | 0 | | 0 | | 0 | | | Π |
| L | L | L | $R_{11}$ | … | $R_{1α}$ | … | $R_{1β}$ | … | $R_{1γ}$ | … | $R_{1m}$ |
| R | R | R | ︙ | | ︙ | | ︙ | | ︙ | | ︙ |
| | | | $R_{m1}$ | … | $R_{mα}$ | … | $R_{mβ}$ | … | $R_{mγ}$ | … | $R_{mm}$ |

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^{−1}$ 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^{−1}$ 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

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

Sie wird mit einem Nullenkreuz zur Pivotmatrix:

| Reduktion Zeile 2 und Spalte 3  6   1  0  0   48  -24  -6  1   0  1  0   -8  4  1  -18   0  0  1   -144  72  18    1  0  0  0   1   0   0  0  1    8  -4  1 | → | Endergebnis  1  6  0   0  0  0  Π  0  1  0   0  0  1  0  -18  1   0  0  0 L  1  0  0 R   0   1   0     8  -4  1 |
| - | - | - |

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

| $I_r$ | 0 |
| - | - |
| 0 | 0 |

ü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.

## Algorithmus von Banachiewicz

Der Algorithmus von Banachiewicz erzeugt die Nullenkreuze in einer Matrix A, indem bestimmte Dyaden von A subtrahiert werden. Die Zerlegung A = LΠR mit einer Pivotmatrix Π entsteht dabei direkt und mit weniger Schreibarbeit als beim Gauß’schen Eliminationsverfahren. Der Algorithmus kann mit Vorteil bei der Invertierung einer Summe zweier Matrizen eingesetzt $werden^{:452}.$ Die Zerlegung findet sich für symmetrische Matrizen zuerst bei Doolittle, später in etwas abgewandelter Form bei Cholesky und für nichtsymmetrische Matrizen erstmals bei $Banachiewicz.^{:82}$

Zugrunde gelegt wird der Körper K mit der Standardbasis $e_{1,…,n}$ des $K^n$ und $ε_{1,…,m}$ des $K^m.$ Bei einer beliebigen n×m-Matrix A mit inversem Pivotelement $Z_{ij}$ = $1/A_{ij},$ dem 1×m-Zeilenvektor $p_j$ = $Z_{ij}$ $e_i^⊤A$ und n×1-Spaltenvektor $q_i$ = $Z_{ij}$ A $ε_j$ ist in der Matrix

    $A_1$ = A − $D_1$ mit $D_1$ = $A_{ij}$ $q_i$ $p_j$

die Pivotzeile i und Pivotspalte j mit Nullen belegt. Das Verfahren wird mit $A_1$ wiederholt, sodass $A_2$ = $A_1$ − $D_2$ ein weiteres Nullenkreuz enthält, und so fort, bis nach spätestens r Schritten

    $A_r$ = A − $D_1$ − $D_2$ … − $D_r$ = O

zur Nullmatrix O geworden ist und das Verfahren endet. Die Summe der Dyaden kann

    $∑_k$ $D_k$ = LΠR mit L = $∑q_i$ $e_i^⊤,$ Π = $∑A_{ij}$ $e_i$ $ε_j^⊤$ und R = $∑ε_j$ $p_j$

geschrieben werden, wo die Indizes in den Summen ∑ jeweils die in den Reduktionsschritten vorkommenden Werte durchlaufen. Zum Schluss ist nach Konstruktion

    A = LΠR

Beispiel: Die Zerlegung der Matrix

    ${\mathsf {A}}={\begin{pmatrix}0&3&2&2\\-1&-1&-1&-1\\3&6&3&-3\\7&-5&1&6\end{pmatrix}}$

aus dem Beispiel im Abschnitt Gauß’sches Eliminationsverfahren läuft wie folgt. Mit dem ersten Pivot an der Stelle 21 mit $Z_{21}$ = $1/A_{21}$ = -1 bekommt man

    ${\mathsf {A}}_{1}={\mathsf {A}}-(-1){\begin{pmatrix}0\\1\\-3\\-7\end{pmatrix}}{\begin{pmatrix}1&1&1&1\end{pmatrix}}={\mathsf {A}}+{\begin{pmatrix}0&0&0&0\\1&1&1&1\\-3&-3&-3&-3\\-7&-7&-7&-7\end{pmatrix}}={\begin{pmatrix}0&3&2&2\\0&0&0&0\\0&3&0&-6\\0&-12&-6&-1\end{pmatrix}}$

Das Pivot 3 an der Stelle 32 von $A_1$ liefert

    ${\mathsf {A}}_{2}={\mathsf {A}}_{1}-3{\begin{pmatrix}1\\0\\1\\-4\end{pmatrix}}{\begin{pmatrix}0&1&0&-2\end{pmatrix}}={\mathsf {A}}_{1}-{\begin{pmatrix}0&3&0&-6\\0&0&0&0\\0&3&0&-6\\0&-12&0&24\end{pmatrix}}={\begin{pmatrix}0&0&2&8\\0&0&0&0\\0&0&0&0\\0&0&-6&-25\end{pmatrix}}$

und das Pivot 2 an der Stelle 13 von $A_2$ ergibt

    ${\mathsf {A}}_{3}={\mathsf {A}}_{2}-2{\begin{pmatrix}1\\0\\0\\-3\end{pmatrix}}{\begin{pmatrix}0&0&1&4\end{pmatrix}}={\mathsf {A}}_{2}-{\begin{pmatrix}0&0&2&8\\0&0&0&0\\0&0&0&0\\0&0&-6&-24\end{pmatrix}}={\begin{pmatrix}0&0&0&0\\0&0&0&0\\0&0&0&0\\0&0&0&-1\end{pmatrix}}$

Die vierte Reduktion hinterlässt die Nullmatrix:

    ${\mathsf {A}}_{4}={\mathsf {A}}_{3}-(-1){\begin{pmatrix}0\\0\\0\\1\end{pmatrix}}{\begin{pmatrix}0&0&0&1\end{pmatrix}}={\begin{pmatrix}0&0&0&0\\0&0&0&0\\0&0&0&0\\0&0&0&0\end{pmatrix}}$

Die Matrizen

    ${\begin{aligned}{\mathsf {L}}=&{\begin{pmatrix}0\\1\\-3\\-7\end{pmatrix}}{\mathsf {e}}_{2}^{\top }+{\begin{pmatrix}1\\0\\1\\-4\end{pmatrix}}{\mathsf {e}}_{3}^{\top }+{\begin{pmatrix}1\\0\\0\\-3\end{pmatrix}}{\mathsf {e}}_{1}^{\top }+{\begin{pmatrix}0\\0\\0\\1\end{pmatrix}}{\mathsf {e}}_{4}^{\top }={\begin{pmatrix}1&0&1&0\\0&1&0&0\\0&-3&1&0\\-3&-7&-4&1\end{pmatrix}}\\{\mathsf {\Pi }}=&-{\mathsf {e}}_{2}{\mathsf {e}}_{1}^{\top }+3{\mathsf {e}}_{3}{\mathsf {e}}_{2}^{\top }+2{\mathsf {e}}_{1}{\mathsf {e}}_{3}^{\top }-{\mathsf {e}}_{4}{\mathsf {e}}_{4}^{\top }={\begin{pmatrix}0&0&2&0\\-1&0&0&0\\0&3&0&0\\0&0&0&-1\end{pmatrix}}\\{\mathsf {R}}=&{\mathsf {e}}_{1}{\begin{pmatrix}1\\1\\1\\1\end{pmatrix}}^{\top }+{\mathsf {e}}_{2}{\begin{pmatrix}0\\1\\0\\-2\end{pmatrix}}^{\top }+{\mathsf {e}}_{3}{\begin{pmatrix}0\\0\\1\\4\end{pmatrix}}^{\top }+{\mathsf {e}}_{4}{\begin{pmatrix}0\\0\\0\\1\end{pmatrix}}^{\top }={\begin{pmatrix}1&1&1&1\\0&1&0&-2\\0&0&1&4\\0&0&0&1\end{pmatrix}}\end{aligned}}$

können parallel zur schrittweisen Reduktion in Phantommatrizen aufgebaut werden. Wie gefordert ist A = LΠR oder ausgeschrieben:

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