Beweisarchiv: Lineare Algebra
Endomorphismen: Satz von Cayley-Hamilton · Korrektheit des Algorithmus von Faddejew-Leverrier · Kreisesatz von Gerschgorin
Vektorräume: Jeder Vektorraum hat eine Basis
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
∈
C
n
×
n
{\displaystyle A\in \mathbb {C} ^{n\times n}}
die Koeffizienten
c
k
(
k
=
1
,
…
n
)
{\displaystyle c_{k}\;(k=1,\ldots n)}
des durch
p
(
λ
)
=
det
(
λ
I
−
A
)
{\displaystyle p(\lambda )=\det(\lambda I-A)\;}
definierten charakteristischen Polynoms
p
(
λ
)
=
c
n
λ
n
+
c
n
−
1
λ
n
−
1
+
c
n
−
2
λ
n
−
2
+
…
+
c
1
λ
+
c
0
{\displaystyle p(\lambda )=c_{n}\lambda ^{n}+c_{n-1}\lambda ^{n-1}+c_{n-2}\lambda ^{n-2}+\ldots +c_{1}\lambda +c_{0}}
ermittelt. Außerdem liefert der Algorithmus sowohl die Determinante als auch die Inverse von
A
{\displaystyle A}
.
Beschreibung des Algorithmus und der Rekursion [ Bearbeiten ]
Der Algorithmus basiert auf folgender Rekursionsvorschrift für die Matrizen
B
0
,
…
,
B
n
∈
C
n
×
n
{\displaystyle B_{0},\ldots ,B_{n}\in \mathbb {C} ^{n\times n}}
und
die Koeffizienten
c
0
,
…
,
c
n
∈
C
{\displaystyle c_{0},\ldots ,c_{n}\in \mathbb {C} }
B
0
=
0
c
n
=
1
(
k
=
0
)
B
k
=
A
B
k
−
1
+
c
n
−
k
+
1
I
c
n
−
k
=
−
1
k
t
r
(
A
B
k
)
k
=
1
,
…
,
n
{\displaystyle {\begin{aligned}B_{0}&=0&c_{n}&=1\qquad &(k=0)\\B_{k}&=AB_{k-1}+c_{n-k+1}I\qquad \qquad &c_{n-k}&=-{\frac {1}{k}}\mathrm {tr} (AB_{k})\qquad &k=1,\ldots ,n\end{aligned}}}
Hierin ist
t
r
(
M
)
:=
∑
i
=
1
n
m
i
i
{\displaystyle \mathrm {tr} (M):=\sum \limits _{i=1}^{n}m_{ii}}
die sogenannte Spur einer quadratischen
Matrix
M
∈
C
n
×
n
{\displaystyle M\in \mathbb {C} ^{n\times n}}
Der Algorithmus hat weitere interessante Eigenschaften:
c
0
=
p
(
0
)
=
det
(
−
A
)
=
(
−
1
)
n
det
A
{\displaystyle c_{0}=p(0)=\det(-A)=(-1)^{n}\;\det A}
erhält man unmittelbar den Wert der Determinanten von
A
{\displaystyle A}
.
Außerdem kann man mit Hilfe der Beziehung
B
n
+
1
=
A
B
n
+
c
0
I
=
0
{\displaystyle B_{n+1}=AB_{n}+c_{0}I=0\;}
überprüfen, ob der Algorithmus korrekt terminiert. Durch Umformen erhält man hieraus insbesondere auch
die Inverse von
A
{\displaystyle A}
:
A
−
1
=
−
1
c
0
B
n
{\displaystyle A^{-1}=-{\frac {1}{c_{0}}}B_{n}}
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
(
λ
I
−
A
)
⋅
a
d
j
(
λ
I
−
A
)
=
det
(
λ
I
−
A
)
⋅
I
=
p
A
(
λ
)
⋅
I
{\displaystyle (\lambda I-A)\cdot \mathrm {adj} (\lambda I-A)=\det(\lambda I-A)\cdot I=p_{A}(\lambda )\cdot I}
Aus der Definition der Adjunkten folgt, dass
λ
{\displaystyle \lambda \;}
in
a
d
j
(
λ
I
−
A
)
{\displaystyle \mathrm {adj} (\lambda I-A)\;}
höchstens mit Grad
n
−
1
{\displaystyle n-1\;}
auftritt. Man kann hierin nach
Potenzen von
λ
{\displaystyle \lambda \;}
sortieren und dann geeignet als Summe zerlegen.
Es ist für unsere Zwecke nützlich, das Polynom in
λ
{\displaystyle \lambda }
mit Matrix-Koeffizienten
B
k
∈
C
n
×
n
(
k
=
0
,
…
,
n
+
1
)
{\displaystyle B_{k}\in \mathbb {C} ^{n\times n}\;(k=0,\ldots ,n+1)\;}
zu schreiben ( wobei
B
0
=
0
{\displaystyle B_{0}=0\;}
und
B
n
+
1
=
0
{\displaystyle B_{n+1}=0\;}
):
a
d
j
(
λ
I
−
A
)
=
∑
k
=
0
n
+
1
B
k
λ
n
−
k
{\displaystyle \mathrm {adj} (\lambda I-A)=\sum _{k=0}^{n+1}B_{k}\lambda ^{n-k}}
Einsetzen und Umformen liefert:
(
λ
I
−
A
)
⋅
∑
k
=
0
n
+
1
B
k
λ
n
−
k
=
p
A
(
λ
)
⋅
I
∑
k
=
1
n
+
1
(
B
k
−
A
B
k
−
1
)
λ
n
−
k
+
1
=
∑
k
=
1
n
+
1
c
n
−
k
+
1
λ
n
−
k
+
1
⋅
I
(
∗
)
{\displaystyle {\begin{aligned}(\lambda I-A)\cdot \sum _{k=0}^{n+1}B_{k}\lambda ^{n-k}&=p_{A}(\lambda )\cdot I\\\sum _{k=1}^{n+1}\left(B_{k}-AB_{k-1}\right)\lambda ^{n-k+1}&=\sum _{k=1}^{n+1}c_{n-k+1}\lambda ^{n-k+1}\cdot I\qquad (*)\end{aligned}}}
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
{\displaystyle B_{k}-AB_{k-1}=c_{n-k+1}I\quad \Longleftrightarrow \quad B_{k}=AB_{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
=
−
1
c
0
B
n
{\displaystyle 0=B_{n+1}=AB_{n}+c_{0}I\quad \Longleftrightarrow \quad A^{-1}=-{\frac {1}{c_{0}}}B_{n}}
Damit ist die Rekursionsvorschrift für die Matrizen
B
k
{\displaystyle B_{k}\;}
sowie die Aussage für die
Inverse von
A
{\displaystyle A}
hergeleitet.
Bemerkung:
Aus (*) folgt direkt der Satz von Cayley-Hamilton , denn Einsetzen
von
A
{\displaystyle 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
{\displaystyle 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
)
{\displaystyle M(x)}
:
d
d
x
det
(
M
(
x
)
)
=
t
r
(
a
d
j
(
M
(
x
)
)
⋅
d
d
x
M
(
x
)
)
{\displaystyle {\frac {d}{dx}}\det(\;M(x)\;)=\mathrm {tr} \left(\;\mathrm {adj} (M(x))\cdot {\frac {d}{dx}}M(x)\;\right)}
Speziell für unsere Situation bedeutet das also:
p
′
(
λ
)
=
d
d
λ
det
(
λ
I
−
A
)
)
=
t
r
(
a
d
j
(
λ
I
−
A
)
⋅
d
d
λ
(
λ
I
−
A
)
)
=
t
r
(
a
d
j
(
λ
I
−
A
)
)
{\displaystyle p'(\lambda )={\frac {d}{d\lambda }}\det(\;\lambda I-A)\;)=\mathrm {tr} \left(\;\mathrm {adj} (\lambda I-A)\cdot {\frac {d}{d\lambda }}(\lambda I-A)\;\right)=\mathrm {tr} (\;\mathrm {adj} (\lambda I-A)\;)}
Wir rechnen nun beide Seiten weiter aus. Einerseits haben wir dann:
t
r
(
a
d
j
(
λ
I
−
A
)
)
=
t
r
(
∑
k
=
0
n
+
1
B
k
λ
n
−
k
)
=
∑
k
=
0
n
+
1
t
r
(
B
k
λ
n
−
k
)
=
∑
k
=
0
n
+
1
t
r
(
B
k
)
λ
n
−
k
{\displaystyle \mathrm {tr} (\;\mathrm {adj} (\lambda I-A)\;)=\mathrm {tr} \left(\sum _{k=0}^{n+1}B_{k}\lambda ^{n-k}\right)=\sum _{k=0}^{n+1}\mathrm {tr} (B_{k}\lambda ^{n-k})=\sum _{k=0}^{n+1}\mathrm {tr} (B_{k})\lambda ^{n-k}}
Andererseits können wir das charakteristische Polynom als
p
(
λ
)
=
∑
k
=
0
n
c
n
−
k
λ
n
−
k
{\displaystyle p(\lambda )=\sum _{k=0}^{n}c_{n-k}\lambda ^{n-k}}
schreiben und erhalten als Ableitung:
p
′
(
λ
)
=
∑
k
=
0
n
(
n
−
k
)
c
n
−
k
λ
n
−
k
−
1
{\displaystyle p'(\lambda )=\sum _{k=0}^{n}(n-k)\;c_{n-k}\;\lambda ^{n-k-1}}
schreiben. Koeffizientenvergleich in den beiden Ausdrücken für
t
r
(
a
d
j
(
λ
I
−
A
)
)
{\displaystyle \mathrm {tr} (\;\mathrm {adj} (\lambda I-A)\;)}
und
p
′
(
λ
)
{\displaystyle p'(\lambda )\;}
sowie anschließendes Einsetzen der Rekursionsvorschrift für
B
k
+
1
{\displaystyle B_{k+1}\;}
ergibt
(
n
−
k
)
c
n
−
k
=
t
r
(
B
k
+
1
)
=
t
r
(
A
B
k
+
c
n
−
k
I
)
=
t
r
(
A
B
k
)
+
c
n
−
k
t
r
(
I
)
=
t
r
(
A
B
k
)
+
n
⋅
c
n
−
k
{\displaystyle {\begin{aligned}(n-k)\;c_{n-k}&=\mathrm {tr} (B_{k+1})\\&=\mathrm {tr} \left(\;AB_{k}+c_{n-k}I\;\right)\\&=\mathrm {tr} (AB_{k})+c_{n-k}\;\mathrm {tr} (I)\\&=\mathrm {tr} (AB_{k})+n\cdot c_{n-k}\end{aligned}}}
und einige letzte Umformungen führen dann auf das behauptete Resultat:
c
n
−
k
=
−
1
k
t
r
(
A
B
k
)
{\displaystyle c_{n-k}=-{\frac {1}{k}}\;\mathrm {tr} (AB_{k})}