Ein Basis-Test

Der Invertierungsalgorithmus lässt sich auch verwenden, um zu testen, ob Vektoren v₁, …, v_n des ℝⁿ eine Basis des ℝⁿ bilden oder nicht:

Basis-Test

Sei A = (v₁, …, v_n) (mit den Basisvektoren als Zeilen). Wir wenden den Invertierungs-Algorithmus auf A an. Erzeugen wir eine Nullzeile, so geben wir „nein" als Ergebnis aus. Können wir dagegen A in E_n überführen, so ist „ja“ das Ergebnis der Berechnung.

Die Korrektheit ergibt sich daraus, dass eine Matrix A  ∈  ℝ^{n × n} genau dann invertierbar ist, wenn ihre Zeilen eine Basis bilden.

Im Basis-Test müssen wir die B-Matrizen nicht berechnen. Es ist dennoch nützlich, dies zu tun: Finden wir im singulären Fall eine Matrix A_k, deren i-te Zeile Null ist, so liefert die i-te Zeile (λ₁, …, λ_n) von B_k die Koeffizienten einer nichttrivialen Nulldarstellung

λ₁v₁ + … + λ_nv_n = 0

der Basisvektoren v₁, …, v_n (denn es gilt λ₁v_1 j + … + λ_nv_n j = 0 für alle j = 1, …, n, da die i-te Zeile von B_k A eine Nullzeile ist).

Beispiel: Basis-Test und Berechnung einer Nulldarstellung

Für die Vektoren v₁ = (1, 2, −1), v₂ = (−1, 0, 1), v₃ = (1, 4, −1) verläuft der Basis-Test wie folgt:

A₀ = $( \begin{matrix} 1 & 2 & - 1 \\ - 1 & 0 & 1 \\ 1 & 4 & - 1 \end{matrix} )$ $( \begin{matrix} 1 & 0 & 0 \\ 0 & 1 & 0 \\ 0 & 0 & 1 \end{matrix} )$ = B₀

A₁ = $( \begin{matrix} 1 & 2 & - 1 \\ 0 & 2 & 0 \\ 1 & 4 & - 1 \end{matrix} )$ $( \begin{matrix} 1 & 0 & 0 \\ 1 & 1 & 0 \\ 0 & 0 & 1 \end{matrix} )$ = B₁

A₂ = $( \begin{matrix} 1 & 2 & - 1 \\ 0 & 2 & 0 \\ 0 & 2 & 0 \end{matrix} )$ $( \begin{matrix} 1 & 0 & 0 \\ 1 & 1 & 0 \\ - 1 & 0 & 1 \end{matrix} )$ = B₂

A₃ = $( \begin{matrix} 1 & 2 & - 1 \\ 0 & 2 & 0 \\ 0 & 0 & 0 \end{matrix} )$ $( \begin{matrix} 1 & 0 & 0 \\ 1 & 1 & 0 \\ - 2 & - 1 & 1 \end{matrix} )$ = B₃

Die Matrix A₃ besitzt eine Nullzeile und wir stoppen mit Ergebnis „nein“. Die entsprechende dritte Zeile von B₃ liefert die Koeffizienten einer nichttrivialen Nulldarstellung der Vektoren v₁, v₂ und v₃:

−2 v₁ − 1 v₂ + v₃ = −2 (1, 2, −1) − (−1, 0, 1) + (1, 4, −1) = (0, 0, 0) = 0

Wir betrachten noch einen Spezialfall:

Beispiel: Durchführung des Algorithmus bei einer Nullspalte

Für v₁ = (0, 1, 1), v₂ = (0, 1, 0), v₃ = (0, 2, 1) können wir so vorgehen:

A₀ = $( \begin{matrix} 0 & 1 & 1 \\ 0 & 1 & 0 \\ 0 & 2 & 1 \end{matrix} )$ $( \begin{matrix} 1 & 0 & 0 \\ 0 & 1 & 0 \\ 0 & 0 & 1 \end{matrix} )$ = B₀

A₁ = $( \begin{matrix} 0 & 1 & 1 \\ 0 & 0 & - 1 \\ 0 & 2 & 1 \end{matrix} )$ $( \begin{matrix} 1 & 0 & 0 \\ - 1 & 1 & 0 \\ 0 & 0 & 1 \end{matrix} )$ = B₁

A₂ = $( \begin{matrix} 0 & 1 & 1 \\ 0 & 0 & - 1 \\ 0 & 0 & - 1 \end{matrix} )$ $( \begin{matrix} 1 & 0 & 0 \\ - 1 & 1 & 0 \\ - 2 & 0 & 1 \end{matrix} )$ = B₂

A₃ = $( \begin{matrix} 0 & 1 & 1 \\ 0 & 0 & - 1 \\ 0 & 0 & 0 \end{matrix} )$ $( \begin{matrix} 1 & 0 & 0 \\ - 1 & 1 & 0 \\ - 1 & - 1 & 1 \end{matrix} )$ = B₃

Die Singularität von A = (v₁, v₂, v₃) ist von Anfang an klar, aber wir führen die Berechnung fort, bis wir eine Nullzeile erreichen. Die dritte Zeile von B₃ liefert erneut die Koeffizienten einer nichttrivialen Nulldarstellung der Vektoren v₁, v₂ und v₃:

− v₁ − v₂ + v₃ = (0, −1, −1) − (0, 1, 0) + (0, 2, 1) = (0, 0, 0) = 0