Wie kann man überprüfen, ob m n-sized Vektoren linear unabhängig sind?

Question

Hinweis
Dies ist nicht unbedingt eine Programmierung Frage, aber die meisten Programmierer bald oder später mit Mathematik (insbesondere Algebra) zu tun haben, also denke ich, dass die Antwort auf jemand anderes in der Zukunft nützlich erweisen könnte.

Jetzt ist das Problem
Ich versuche, wenn es m Vektoren der Dimension n zu überprüfen linear unabhängig sind. Wenn m == n Sie können nur eine Matrix mit den Vektoren bauen und prüfen, ob die Determinante! = 0. Aber was, wenn m

Für Hinweise?

---

Siehe auch Dieses Video Vortrag .

Answer 1

Konstruieren einer Matrix der Vektoren (eine Zeile pro Vektor), und eine Gaußschen Eliminationszuführen auf dieser Matrix. Wenn eine der Matrixzeilen aufhebt, sind sie nicht linear unabhängig sind.

Der triviale Fall ist, wenn m> n, in diesem Fall sie nicht linear unabhängig sein können.

Answer 2

Konstruieren einer Matrix, deren Zeilen M sind die Vektoren und den Rang des M bestimmen. Wenn der Rang von weniger als M m ist (die Anzahl der Vektoren), dann gibt es eine lineare Abhängigkeit. In dem Algorithmus den Rang eines M bestimmen können Sie die Prozedur stoppen, sobald man eine Zeile von Nullen zu erhalten, aber den Algorithmus zur Vollständigkeit ausgeführt haben die zusätzliche Goldgrube der Dimension des Spannsatzes der Vektoren bereitstellt. Ach ja, und der Algorithmus der Rang eines M zu bestimmen, ist lediglich die Gauß-Elimination.

Achten Sie darauf, für die numerische Instabilität. Siehe die Warnung am Anfang des Kapitels zwei in Numerical Recipes.

Answer 3

Wenn m<n, müssen Sie ihnen eine Operation tun (es gibt mehrere Möglichkeiten: Gauß-Elimination, Orthogonalisierung usw. fast jede Transformation, die zur Lösung von Gleichungen verwendet werden können, tun wird) und überprüfen Sie das Ergebnis (zB Gaussian. Eliminierung => Null Zeile oder Spalte, Orthogonalisierung => Nullvektor, SVD => Null Einzahl)

Beachten Sie jedoch, dass diese Frage ist eine schlechte Frage für einen Programmierer zu stellen, und dieses Problem ist ein schlechtes Problem für ein Programm zu lösen. Das ist, weil jeder linear abhängig Satz von n<m Vektoren einen anderen Satz von linear unabhängigen Vektoren hat in der Nähe (zB. Das Problem ist numerisch instabil)

Answer 4

Ich habe in diesen Tagen auf diesem Problem gearbeitet.

Bisher habe ich einige Algorithmen in Bezug auf Gauß- oder Gaußsche-Jordan-Elimination gefunden, aber die meisten dieser Algorithmen nur auf quadratische Matrix, nicht allgemeine Matrix anzuwenden.

Um für die allgemeine Matrix anwenden, ist eine der besten Antworten könnten sein: http://rosettacode.org/wiki/Reduced_row_echelon_form#MATLAB

Sie können beide finden Pseudo-Code und Quellcode in verschiedenen Sprachen. Was mich betrifft, ich die Python-Quellcode in C ++ umgewandelt, bewirkt, dass der C ++ Code in dem oben angegebenen Link irgendwie komplex und ungeeignet ist in meiner Simulation zu implementieren.

Hope dies wird Ihnen, und viel Glück helfen ^^

Answer 5

Wenn die Rechenleistung kein Problem ist, wahrscheinlich der beste Weg ist singuläre Werte der Matrix zu finden. Grundsätzlich müssen Sie Eigenwerte von M'*M und Blick auf das Verhältnis der größten zur kleinsten finden. Wenn das Verhältnis nicht sehr groß ist, sind die Vektoren unabhängig.

Answer 6

Eine weitere Möglichkeit, dass m Zeilenvektoren sind linear unabhängig zu überprüfen, wenn sie in einer Matrix M der Größe mxn ausgedrückt, ist zu berechnen

det(M * M^T)

d. die Determinante einer mxm quadratische Matrix. Es wird Null, wenn und nur wenn M einige abhängigen Zeilen. Jedoch Gauß-Elimination sollte im Allgemeinen schneller sein.

Answer 7

Leider Mann, mein Fehler ...

---

Der Quellcode in dem oben angegebenen Link stellt sich heraus, falsch zu sein, zumindest den Python-Code, den ich getestet habe und der C ++ Code I umgewandelt habe erzeugt nicht das Recht, die ganze Zeit zu beantworten. (Während für die exmample in dem obigen Link, das Ergebnis korrekt ist :) -)

, um den Python-Code zu testen, einfach ersetzen die mtx mit

[30,10,20,0],[60,20,40,0]

und das zurückgegebene Ergebnis wäre wie:

[1,0,0,0],[0,1,2,0]

Trotzdem habe ich aus diesem einen Weg. Es ist nur dieses Mal habe ich die matalb Quellcode rref Funktion zu C ++ umgewandelt. Sie können Matlab und verwenden Sie den Befehl ausführen type rref den Quellcode rref zu erhalten.

Beachten Sie nur, wenn Sie mit einigen wirklich großen Wert arbeiten oder wirklich kleinen Wert, stellen Sie sicher, dass die Verwendung der long double Datentyp in C ++. Andernfalls wird das Ergebnis mit dem Matlab Ergebnis abgeschnitten und inkonsistent werden.

Ich habe die Durchführung große Simulationen in ns2 und alle beobachteten Ergebnisse sind solide. hoffen, dass diese Ihnen helfen und andere, die das Problem encontered haben ...

Answer 8

Eine sehr einfache Art und Weise, ist, dass nicht die rechnerisch effizient, einfach ist, um zufällige Reihen bis m=n zu entfernen und dann den Determinante Trick anwenden.

• m < n: Entfernen Reihen (stellen die Vektoren kürzer), bis die Matrix quadratisch ist, und dann
• m = n: prüfen, ob die Determinante 0 ist (wie Sie gesagt haben)
• m < n (die Anzahl der Vektoren größer als ihre Länge): sie linear abhängig sind (immer)
.

Der Grund, kurz gesagt, ist, dass jede Lösung auf das System von Gleichungen m x n ist auch eine Lösung für das n x n Gleichungssystem (Sie versuchen Av=0 zu lösen). siehe für eine bessere Erklärung, Wikipedia , was erklärt, es besser als ich kann.