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

---

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 $A\in {ℂ}^{n\times n}$ die Koeffizienten $c_k(k=1,\dots n)$ des durch $p(\lambda )=det(\lambda I-A)$ definierten charakteristischen Polynoms

$p(\lambda )=c_n{\lambda }^n+c_{n-1}{\lambda }^{n-1}+c_{n-2}{\lambda }^{n-2}+\dots +c_1\lambda +c_0$

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

Beschreibung des Algorithmus und der Rekursion

Der Algorithmus basiert auf folgender Rekursionsvorschrift für die Matrizen $B_0,\dots ,B_n\in {ℂ}^{n\times n}$ und die Koeffizienten $c_0,\dots ,c_n\in ℂ$

$\begin{array}{ccccc}{B}_0& =0& c_n& =1& (k=0)\\ B_k& =A{B}_{k-1}+c_{n-k+1}I& c_{n-k}& =-\frac{1}{k}\mathrm{t}\mathrm{r}(A{B}_k)& k=1,\dots ,n\end{array}$

Hierin ist $\mathrm{t}\mathrm{r}(M):=\sum _{i=1}^n{m}_{ii}$ die sogenannte Spur einer quadratischen Matrix $M\in {ℂ}^{n\times n}$

Der Algorithmus hat weitere interessante Eigenschaften:

• Wegen

$c_0=p(0)=det(-A)=(-1{)}^{n}detA$

erhält man unmittelbar den Wert der Determinanten von $A$.

• Außerdem kann man mit Hilfe der Beziehung

$B_{n+1}=A{B}_n+c_{0}I=0$

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

$A^{-1}=-\frac{1}{c_0}{B}_n$

Beweise für die Korrektheit Algorithmus

Direkter algebraischer Beweis

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

$(\lambda I-A)\cdot \mathrm{a}\mathrm{d}\mathrm{j}(\lambda I-A)=det(\lambda I-A)\cdot I=p_A(\lambda )\cdot I$

Aus der Definition der Adjunkten folgt, dass $\lambda$ in $\mathrm{a}\mathrm{d}\mathrm{j}(\lambda I-A)$ höchstens mit Grad $n-1$ auftritt. Man kann hierin nach Potenzen von $\lambda$ sortieren und dann geeignet als Summe zerlegen. Es ist für unsere Zwecke nützlich, das Polynom in $\lambda$ mit Matrix-Koeffizienten $B_k\in {ℂ}^{n\times n}(k=0,\dots ,n+1)$ zu schreiben ( wobei $B_0=0$ und $B_{n+1}=0$):

$\mathrm{a}\mathrm{d}\mathrm{j}(\lambda I-A)=\sum _{k=0}^{n+1}{B}_k{\lambda }^{n-k}$

Einsetzen und Umformen liefert:

$\begin{array}{cc}(\lambda I-A)\cdot \sum _{k=0}^{n+1}{B}_k{\lambda }^{n-k}& =p_A(\lambda )\cdot I\\ \sum _{k=1}^{n+1}(B_k-A{B}_{k-1}){\lambda }^{n-k+1}& =\sum _{k=1}^{n+1}{c}_{n-k+1}{\lambda }^{n-k+1}\cdot I(\ast )\end{array}$

Durch Koeffizientenvergleich folgt:

$B_k-A{B}_{k-1}=c_{n-k+1}I⟺B_k=A{B}_{k-1}+c_{n-k+1}I$

Speziell haben wir per Definition (siehe oben):

$0=B_{n+1}=A{B}_n+c_{0}I⟺A^{-1}=-\frac{1}{c_0}{B}_n$

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

---

Bemerkung: Aus (*) folgt direkt der Satz von Cayley-Hamilton, denn Einsetzen von $A$ 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 $c_k$ 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 $M(x)$:

$\frac{d}{dx}det(M(x))=\mathrm{t}\mathrm{r}(\mathrm{a}\mathrm{d}\mathrm{j}(M(x))\cdot \frac{d}{dx}M(x))$

Speziell für unsere Situation bedeutet das also:

$p^{\prime }(\lambda )=\frac{d}{d\lambda }det(\lambda I-A))=\mathrm{t}\mathrm{r}(\mathrm{a}\mathrm{d}\mathrm{j}(\lambda I-A)\cdot \frac{d}{d\lambda }(\lambda I-A))=\mathrm{t}\mathrm{r}(\mathrm{a}\mathrm{d}\mathrm{j}(\lambda I-A))$

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

$\mathrm{t}\mathrm{r}(\mathrm{a}\mathrm{d}\mathrm{j}(\lambda I-A))=\mathrm{t}\mathrm{r}\left(\sum _{k=0}^{n+1}{B}_k{\lambda }^{n-k}\right)=\sum _{k=0}^{n+1}\mathrm{t}\mathrm{r}(B_k{\lambda }^{n-k})=\sum _{k=0}^{n+1}\mathrm{t}\mathrm{r}(B_k){\lambda }^{n-k}$

Andererseits können wir das charakteristische Polynom als

$p(\lambda )=\sum _{k=0}^n{c}_{n-k}{\lambda }^{n-k}$

schreiben und erhalten als Ableitung:

$p^{\prime }(\lambda )=\sum _{k=0}^n(n-k)c_{n-k}{\lambda }^{n-k-1}$

schreiben. Koeffizientenvergleich in den beiden Ausdrücken für $\mathrm{t}\mathrm{r}(\mathrm{a}\mathrm{d}\mathrm{j}(\lambda I-A))$ und $p^{\prime }(\lambda )$ sowie anschließendes Einsetzen der Rekursionsvorschrift für $B_{k+1}$ ergibt

$\begin{array}{cc}(n-k)c_{n-k}& =\mathrm{t}\mathrm{r}(B_{k+1})\\ & =\mathrm{t}\mathrm{r}(A{B}_k+c_{n-k}I)\\ & =\mathrm{t}\mathrm{r}(A{B}_k)+c_{n-k}\mathrm{t}\mathrm{r}(I)\\ & =\mathrm{t}\mathrm{r}(A{B}_k)+n\cdot c_{n-k}\end{array}$

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

$c_{n-k}=-\frac{1}{k}\mathrm{t}\mathrm{r}(A{B}_k)$