Ä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

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

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.

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.

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

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:

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

1. jede Spalte höchstens einmal Pivotspalte ist und
2. 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₁ p₂ … p_m)^⊤] P^⊤

eine normierte obere Dreiecksmatrix ist. Dann gilt:

1. die Hauptdiagonalen aller Elevatoren bestehen nur aus Einsen (entsprechend p_jj = 0),
2. für jedes j = 1,…,m gibt es einen Elevator mit mindestens j−1 Nullen in seiner signifikanten Zeile, und
3. 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:

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

1. 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.
2. Im Generalschema einer Äquivalenztransformation entstehen die Produkte in der umgekehrten Reihenfolge: R = ρ₁ρ₂…ρ_m und L = λ_nλ_n-1…λ₁.
3. Die Inverse der Matrix R kann wie folgt in einfacher Weise ermittelt werden: Eine Phantommatrix 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⁻¹ = 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₂ besitzt keine Null, z₃ eine und z₁ zwei, und
• z₁ und z₃ 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:

q1j

A11

…

A1j

…

A1l

…

A1m

A

→

B11

…

B1j

…

B1l

…

B1m

B

︙

︙

︙

︙

︙

︙

︙

︙

︙

qkj

Ak1

…

Akj

…

Akl

…

Akm

Bk1

…

Bkj

…

Bkl

…

Bkm

︙

︙

︙

︙

︙

︙

︙

︙

︙

1

Ai1

…

Aij

…

Ail

…

Aim

Bi1

…

Aij

…

Bil

…

Bim

︙

︙

︙

︙

︙

︙

︙

︙

︙

qnj

An1

…

Anj

…

Anl

…

Anm

Bn1

…

Bnj

…

Bnl

…

Bnm

pi1

…

1

…

pil

…

pim

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

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:

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:

q12	1	2	3	A	→		B11	7	B13	B
1	4	5	6				-6	5	1
	p21	1	p23

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

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

q1j

A11

…

A1j

…

A1l

…

A1m

A

→

B11

…

0

…

B1l

…

B1m

B

︙

︙

︙

︙

︙

︙

︙

︙

︙

qkj

Ak1

…

Akj

…

Akl

…

Akm

Bk1

…

0

…

Bkl

…

Bkm

︙

︙

︙

︙

︙

︙

︙

︙

︙

1

Ai1

…

Aij

…

Ail

…

Aim

0

…

Aij

…

0

…

0

︙

︙

︙

︙

︙

︙

︙

︙

︙

qnj

An1

…

Anj

…

Anl

…

Anm

Bn1

…

0

…

Bnl

…

Bnm

pi1

…

1

…

pil

…

pim

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.

Beispiel: Vorgegeben ist

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

mit Rang zwei und das erste gelb markierte Nullenkreuz

q12	1	2	3	A	→		B11	0	B13	B
1	4	5	6				0	5	0
	p21	1	p23

Man liest ab q₁₂=-²⁄₅, p₂₁=-⁴⁄₅ und p₂₃=-⁶⁄₅ 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'
q21	0	5	0				0	5	0
	1	p12	p13

das das alte unberührt lässt. Mit q₂₁ = p₁₂ = 0 und p₁₃ = 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. 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.

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   B12   B B12 0

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, 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₁₁ = 1 und den Faktoren q₂₁ = -2 + i bzw. p₁₂ = −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

In	A
O	Im

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.

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		1	2	3
	1	4	5	6
		1
			1
				1

Grundoperation 1: Spaltentausch 2 und 3 liefert

1		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		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 ⁴⁄_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

Siehe auch: 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

P	L
	S

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

${\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  ↗   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 z1 =   1  -1  -1  -1

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 z2 =   0  1  0  2

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 z3 =   0  0  1  -4

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 =   -1  1/3  1/2  -1

Endergebnis  0  1  0  0   1  0  0  0  L  0  0  1  0   -3  1  0  0  1  0  0  0   0  1  1  0  0  0  0  1   -7  -4  -3  1 P  -1  -1/3  -1/2  -1   S  0   1/3   0   -2   0  0  1/2  4  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 = ρ₁ρ₂ρ₃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

$(\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 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 -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 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  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 1  -1   -1  1 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⁻¹ sowie R = T⁻¹ 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.

Gauß-Jordan-Algorithmus

Siehe auch: 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.

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:

LAR = Π

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

L11

…

L1n

0

0

0

Π

︙

︙

︙

︙

︙

Li1

…

Lin

0

…

0

…

0

…

0

…

0

︙

︙

︙

︙

︙

Lj1

…

Ljn

0

…

0

…

0

…

0

…

0

︙

︙

︙

︙

︙

Ln1

…

Lnn

0

0

0

L

R11

…

R1α

…

R1β

…

R1γ

…

R1m

R

︙

︙

︙

︙

︙

Rm1

…

Rmα

…

Rmβ

…

Rmγ

…

Rmm

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. 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. Mit den Grundoperationen Permutation und Multiplikation mit einem Skalar kann die Pivotmatrix in die Normalform

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

Zugrunde gelegt wird der Körper K mit der Standardbasis e_1,…,n des Kⁿ 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₁ = A − D₁    mit    D₁ = A_ij q_i p_j

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

A_r = A − D₁ − D₂ … − 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₂₁ = 1/A₂₁ = -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₁ 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₂ 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}}$