Beweisarchiv: Lineare Algebra: Endomorphismen: Korrektheit des Algorithmus von Faddejew-Leverrier

Aus Wikibooks
Wechseln zu: Navigation, Suche

Beweisarchiv: Lineare Algebra



Der Algorithmus von Faddejew-Leverrier (benannt nach dem russischen Mathematiker Dmitri Konstantinowitsch Faddejew und dem französischen Mathematiker Urbain Jean Joseph Leverrier) ist ein Verfahren, das für beliebige quadratische Matrizen die Koeffizienten des durch definierten charakteristischen Polynoms

ermittelt. Außerdem liefert der Algorithmus sowohl die Determinante als auch die Inverse von .

Beschreibung des Algorithmus und der Rekursion[Bearbeiten]

Der Algorithmus basiert auf folgender Rekursionsvorschrift für die Matrizen und die Koeffizienten

Hierin ist die sogenannte Spur einer quadratischen Matrix

Der Algorithmus hat weitere interessante Eigenschaften:

  • Wegen

erhält man unmittelbar den Wert der Determinanten von .

  • Außerdem kann man mit Hilfe der Beziehung

überprüfen, ob der Algorithmus korrekt terminiert. Durch Umformen erhält man hieraus insbesondere auch die Inverse von  :

Beweise für die Korrektheit Algorithmus[Bearbeiten]

Direkter algebraischer Beweis[Bearbeiten]

Wir verwenden folgenden bekannten Zusammenhang zwischen Determinante und Adjunkte einer Matrix, der auch zur Matrix-Inversion verwendet werden kann. Es gilt nämlich

Aus der Definition der Adjunkten folgt, dass in höchstens mit Grad auftritt. Man kann hierin nach Potenzen von sortieren und dann geeignet als Summe zerlegen. Es ist für unsere Zwecke nützlich, das Polynom in mit Matrix-Koeffizienten zu schreiben ( wobei und ):

Einsetzen und Umformen liefert:


Durch Koeffizientenvergleich folgt:


Speziell haben wir per Definition (siehe oben):

Damit ist die Rekursionsvorschrift für die Matrizen sowie die Aussage für die Inverse von hergeleitet.


Bemerkung: Aus (*) folgt direkt der Satz von Cayley-Hamilton, denn Einsetzen von auf der linken Seite führt auf eine Teleskopsumme, in der sich alle Terme wegheben. Vergleiche dazu auch die Beweise im Beweisarchiv.


Es muss nun noch die Aussage für die Koeffizienten des charakteristischen Polynoms bewiesen werden:

Hierzu verwenden wir Jacobi's Formel zur Differentiation von Determinanten-Funktionen. Es gilt nämlich allgemein für eine Matrixfunktion :

Speziell für unsere Situation bedeutet das also:

Wir rechnen nun beide Seiten weiter aus. Einerseits haben wir dann:

Andererseits können wir das charakteristische Polynom als

schreiben und erhalten als Ableitung:

schreiben. Koeffizientenvergleich in den beiden Ausdrücken für und sowie anschließendes Einsetzen der Rekursionsvorschrift für ergibt

und einige letzte Umformungen führen dann auf das behauptete Resultat: