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 adjungiert zueinander zu wählen. Die Äquivalenztransformation geht dann über in den Spezialfall der Kongruenztransformation
LALH = 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 |style="text-align:center;"|→ |L"AR = B" |style="text-align:center;"|mit |L" = TL |style="text-align:center;"|und |B" = TB
Nach k solchen Operationen ist
R' = RT1T2…Tk bzw. L" = TkTk-1…T1L
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 PR, deren Inverse ihre transponierte Matrix ist. Umordnung der Zeilen entsprechend einer Permutationsmatrix T = PL. 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 DR 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 = DL 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 PR/L, DR/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äß
ρ = Im + ej pj⊤
mit Standardbasis e1,…,m des Km aus der Einheitsmatrix Im ∈ Km×m und höchstens einer signifikanten Zeile pj ∈ Km mit weiteren von null verschiedenen Einträgen. Das hochgestellte ⊤ zeigt die transponierte Matrix an, sodass pj⊤ ein Zeilenvektor ist. Tatsächlich ist mit den Spalten bk = B ek:
B' ek = B ρ ek = B (Im + ej pj⊤) ek = bk + bj pjk mit pjk = pj⊤ek
Das heißt, dass zu jeder Spalte bk, wie es sein soll, das pjk fache der Pivotspalte bj 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 pjj = 0 ist. Die j-te Zeile von ρ,
zj = ej⊤ρ = (ej + pj)⊤
hat daher eine Eins auf der Hauptdiagonale, zjj = 1, während die restringierte Zeile pj dort eine Null aufweist.
Die Inverse Matrix der Elevatoren kann sofort angegeben werden:
ρ−1 = Im − ej pj⊤
Denn wegen 0 = pjj = pj⊤ej ist
ρρ−1 = (Im + ejpj⊤)(Im − ejpj⊤) = Im + ejpj⊤ − ejpj⊤ − ejpj⊤ejpj = Im
Entsprechendes gilt für die Spaltenelevatoren
λ = In + qj ej⊤ → λ−1 = In − qj ej⊤
wo nun der Kn zugrunde gelegt wird und die Faktoren in einer signifikanten Spalte λej = sj = ej + qj auftreten, mit sjj = 1 und qjj = 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:
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):
Einzelne oder mehrere der oder 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 [Im + (p1 p2 … pm)⊤] P⊤
eine normierte obere Dreiecksmatrix ist. Dann gilt: die Hauptdiagonalen aller Elevatoren bestehen nur aus Einsen (entsprechend pjj = 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 e1,…,m/n erfolgen kann:
bzw.
wo eine Permutation von und eine solche von ist. Hierbei ist zu beachten: Die Reihenfolge der Zeilenelevatoren 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 M wird mit der Nullmatrix initialisiert, die signifikanten Zeilen pj⊤ 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 qk mit umgekehrtem Vorzeichen in den Spalten der Phantommatrix notiert werden und die Hauptdiagonale von M ebenso mit Einsen belegt wird.
Beispiel
Die Zeilenelevatoren
bilden eine vollständige absteigende Folge, denn ihre farbig markierten signifikanten Zeilen z1,2,3, mit einer 1 in den Spalten eins, zwei bzw. drei, lassen sich in einer quadratischen Matrix anordnen, die nur Einsen auf der Hauptdiagonalen hat, z2 besitzt keine Null, z3 eine und z1 zwei, und z1 und z3 haben eine Null an derselben Stelle (in Spalte 2) Die Permutationsmatrix transformiert R vermöge PRP⊤ in eine normierte obere Dreiecksmatrix. Der Unterschied zwischen den Zeilen zj und pj ist, dass zjj = 1 und pjj = 0 ist, daher auch die unterschiedliche Bezeichnung. Das Produkt der Elevatoren in umgekehrter Reihenfolge lautet
Die Inverse des ersten Elevators ist beispielsweise
und die Inverse des Produkts der Elevatoren lautet:
Die Spaltenelevatoren
haben vergleichbare Eigenschaften, denn sie bilden wegen ebenso eine vollständige absteigende Folge wie die Zeilenelevatoren oben. Das Produkt der Spaltenelevatoren lautet
und die Inverse des umgekehrten Produkts entsteht auch hier durch Vorzeichenumkehr der Nebendiagonalglieder:
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…AkmBk1…Bkj…Bkl…Bkm︙ ︙︙︙︙︙︙︙︙1 Ai1…Aij…Ail…AimBi1…Aij…Bil…Bim︙ ︙︙︙︙︙︙︙︙ qnj An1…Anj…Anl…AnmBn1…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 Bkj der Pivotspalte j, muss der Faktor qkj die Bedingung
Bkj = Akj + qkj Aij
erfüllen. Weil nach Voraussetzung Aij ≠ 0, bestimmt sich der Faktor zu
qkj = (Bkj - Akj)/Aij