Lineare Algebra: lineare Abhängigkeit von Vektoren bestimmen

[Cruz]

Hallo Leute,

jetzt wirds n'bissl mathematisch. Betrachten wir 3 dimensionale Vektoren. Habe ich genau 3 Stück davon, ist es ist kein allzu großer Aufwand festzustellen, ob sie eine Basis bilden, sprich linear unabhängig sind. Ich kann sie in eine Matrix packen und z.B. die Determinante der Matrix berechnen oder eine obere Dreiecksmatrix mit Gauß erzeugen. Habe ich allerdings 4 (oder mehr) 3D Vektoren und will rausfinden, ob eine Basis darin existiert, dann habe ich plötzlich 4 (oder mehr) Matrizen zu prüfen. Der Aufwand wächst kombinatorisch.

Weiss jemand eine generische Lösung, wie ich für eine Menge von Vektoren in _einer_ (von mir aus größeren) Rechnung feststellen kann, ob eine Basis darin existiert? Ich muss nicht unbedingt finden, welche Vektoren genau eine Basis bilden.

Meine beste Lösung bisher ist es zwei nicht kolineare Vektoren aus der Menge festzuhalten und dann mit je einem Vektor aus der Vektor auf lin. unabh. zu prüfen. So bleibt der Aufwand wenigstens linear in der Mächtigkeit der Menge, aber lieber wäre mir soetwas wie alle Vektoren in eine große Matrix zu stecken und dann irgendeine Zauberformel darauf anzuwenden.

Gruß,
Cruz

[Marc Reichelt]

Hallo Cruz,

jetzt wirds n'bissl mathematisch. Betrachten wir 3 dimensionale Vektoren. Habe ich genau 3 Stück davon, ist es ist kein allzu großer Aufwand festzustellen, ob sie eine Basis bilden, sprich linear unabhängig sind. Ich kann sie in eine Matrix packen und z.B. die Determinante der Matrix berechnen oder eine obere Dreiecksmatrix mit Gauß erzeugen. Habe ich allerdings 4 (oder mehr) 3D Vektoren und will rausfinden, ob eine Basis darin existiert, dann habe ich plötzlich 4 (oder mehr) Matrizen zu prüfen. Der Aufwand wächst kombinatorisch.

Das Problem ist, dass der Aufwand nicht linear wächst - daher gibt es auch keine einfache Formel dafür.
Die allgemeine Vorgehensweise ist, die Determinante der Matrix zu berechnen.
Wenn die Determinante ungleich 0 ist, nennt man die Matrix "regulär", d.h. unter anderem, dass die Vektoren linear unabhängig sind - die Matrix ist außerdem invertierbar.

Meine beste Lösung bisher ist es zwei nicht kolineare Vektoren aus der Menge festzuhalten und dann mit je einem Vektor aus der Vektor auf lin. unabh. zu prüfen. So bleibt der Aufwand wenigstens linear in der Mächtigkeit der Menge, aber lieber wäre mir soetwas wie alle Vektoren in eine große Matrix zu stecken und dann irgendeine Zauberformel darauf anzuwenden.

Wenigstens die Zauberformel gibt es, wenn man ein in JavaScript geschriebenes Online-Tool zum Berechnen der Determinante einer Matrix hinzuzählen darf. ;-)

Grüße

Marc Reichelt || http://www.marcreichelt.de/

[seth_not@home]

gudn tach!

Habe ich allerdings 4 (oder mehr) 3D Vektoren und will rausfinden, ob eine Basis darin existiert, [...]

Das Problem ist, dass der Aufwand nicht linear wächst

sondern?

daher gibt es auch keine einfache Formel dafür.

das kommt auf die definition von "einfach" an. ich finde die bestimmung des rangs einer matrix aus [latex]\mathbb R^{3,n}[/latex] erstmal einfach.

Die allgemeine Vorgehensweise ist, die Determinante der Matrix zu berechnen.

bei quadratischen matrizen. aber der fall wurde bereits abgehakt. insofern bringt die determinante (und somit auch genanntes tool) hier nichts.

prost
seth

[Marc Reichelt]

Hallo seth,

das kommt auf die definition von "einfach" an. ich finde die bestimmung des rangs einer matrix aus [latex]\mathbb R^{3,n}[/latex] erstmal einfach.

Sicher, aber bei einer Matrix [latex]\mathbb R^{3,n}[/latex] gibt es doch maximal drei unabhängige Vektoren. Alle restlichen lassen sich aus diesen drei bestimmen.

Die allgemeine Vorgehensweise ist, die Determinante der Matrix zu berechnen.

bei quadratischen matrizen. aber der fall wurde bereits abgehakt. insofern bringt die determinante (und somit auch genanntes tool) hier nichts.

Stimmt, ich ging von [latex]\mathbb R^{n,n}[/latex] aus. Allerdings haben die Vektoren eines [latex]\mathbb R^{n}[/latex] n Zeilen, sodass man eine quadratische Matrix bekommt - bei der man auch die Determinante bestimmen kann.
Cruz erwähnte im Ursprungsposting "4 oder mehr 3D-Vektoren" - ich hatte mich natürlich auf die lineare Unabhängigkeit konzentriert, und auch nicht auf 3D, sondern auf nD. ;-)

Grüße

Marc Reichelt || http://www.marcreichelt.de/

[[e-mail]]

gudn tach!

das kommt auf die definition von "einfach" an. ich finde die bestimmung des rangs einer matrix aus [latex]\mathbb R^{3,n}[/latex] erstmal einfach.

Sicher, aber bei einer Matrix [latex]\mathbb R^{3,n}[/latex] gibt es doch maximal drei unabhängige Vektoren. Alle restlichen lassen sich aus diesen drei bestimmen.

ja, eben.
es kann geprueft werden, ob der rang kleiner als 3 ist oder ob er gleich 3 ist.
rang<3 => kein erzeugendes system => keine basis enthalten
rang=3 => erzeugendes system => basis enthalten

und? ich verstehe dein "aber" nicht.

Die allgemeine Vorgehensweise ist, die Determinante der Matrix zu berechnen.

bei quadratischen matrizen. aber der fall wurde bereits abgehakt. insofern bringt die determinante (und somit auch genanntes tool) hier nichts.

Stimmt, ich ging von [latex]\mathbb R^{n,n}[/latex] aus.

ja, aber hier ist das nur fuer den fall n=3 interessant und der fall war, wie gesagt, bereits erledigt. und auf den fall (n,m) mit n=3 und m>3 laesst sich das determinantenverfahren nicht mehr anwenden.

Allerdings haben die Vektoren eines [latex]\mathbb R^{n}[/latex] n Zeilen, sodass man eine quadratische Matrix bekommt

¿hae?
redest du noch von Cruz' problem? falls ja, praezisiere mal, was du meinst.

prost
seth

[Marc Reichelt]

Hallo seth_not@wg,

Allerdings haben die Vektoren eines [latex]\mathbb R^{n}[/latex] n Zeilen, sodass man eine quadratische Matrix bekommt

¿hae?
redest du noch von Cruz' problem? falls ja, praezisiere mal, was du meinst.

Ich dachte, Cruz würde sich nur auf quadratische Matrizen ([latex]\mathbb R^{n,n}[/latex]) beziehen - wo also jeder Vektor aus der Dimension [latex]\mathbb R^{n}[/latex] stammt, und wo somit auch stets die Determinante bestimmt werden kann.

Grüße

Marc Reichelt || http://www.marcreichelt.de/

[Cruz]

Alle Vektoren in eine Matrix schreiben und den Rang der Matrix bestimmen ist die Lösung, die ich gesucht habe.