Come controllare se m vettori n-dimensioni sono linearmente indipendenti?

Question

responsabilità
Questo non è strettamente una questione di programmazione, ma la maggior parte dei programmatori prima o poi avere a che fare con la matematica (in particolare algebra), quindi penso che la risposta potrebbe rivelarsi utile a qualcun altro in futuro.

Ora il problema
Sto cercando di verificare se m vettori di dimensione n sono linearmente indipendenti. Se m == n si può semplicemente costruire una matrice utilizzando i vettori e verificare se il determinante è! = 0. Ma cosa succede se m

Eventuali suggerimenti?

---

Si veda anche questo video conferenza .

Answer 1

costruire una matrice di vettori (una riga per vettore), ed eseguire un gaussiana eliminazione su questa matrice. Se una qualsiasi delle righe di matrice annulla, non sono linearmente indipendenti.

Il caso banale è quando m> n, in questo caso, non possono essere linearmente indipendenti.

Answer 2

Costruire una M matrice avente righe sono i vettori e determinano la posizione di M. Se la posizione di M è inferiore m (il numero di vettori) allora c'è una dipendenza lineare. Nella algoritmo per determinare il grado di M è possibile interrompere la procedura, non appena si ottiene una fila di zeri, ma in esecuzione l'algoritmo a compimento ha la bonanza aggiunto di fornire la dimensione del set che abbracciano dei vettori. Oh, e l'algoritmo per determinare il rango di M è l'eliminazione solo gaussiana.

Fare attenzione per la stabilità numerica. Vedere l'avviso all'inizio del capitolo due in Numerical Recipes.

Answer 3

Se m<n, si dovrà fare qualche operazione su di loro (ci sono molteplici possibilità: eliminazione di Gauss, ortogonalizzazione, ecc, quasi ogni trasformazione che può essere utilizzato per risolvere le equazioni farà) e controllare il risultato (ad esempio gaussiana. eliminazione => riga zero o colonna, ortogonalizzazione => vettore zero, SVD => nullo singolare)

Si noti tuttavia che questa domanda è una cattiva domanda per un programmatore per chiedere, e questo problema è un cattivo problema per un programma per risolvere. Questo perché ogni insieme linearmente dipendente di vettori n<m ha un diverso insieme di vettori linearmente indipendenti nelle vicinanze (ad es. Il problema è numericamente instabile)

Answer 4

Ho lavorato su questo problema in questi giorni.

In precedenza, ho trovato alcuni algoritmi per quanto riguarda l'eliminazione gaussiana o gaussiana-Jordan, ma la maggior parte di questi algoritmi applicano solo alle matrice quadrata, non a matrice generale.

Per richiedere matrice generale, una delle migliori risposte potrebbe essere questo: http://rosettacode.org/wiki/Reduced_row_echelon_form#MATLAB

È possibile trovare sia pseudo-codice e il codice sorgente in varie lingue. Quanto a me, ho trasformato il codice sorgente Python per C ++, causa il codice C ++ fornito nel link qui sopra è in qualche modo complesso e inadeguato da implementare nella mia simulazione.

Spero che questo vi aiuterà, e buona fortuna ^^

Answer 5

Se la potenza di calcolo non è un problema, probabilmente il modo migliore è quello di trovare valori singolari della matrice. Fondamentalmente è necessario trovare autovalori di M'*M e guardare il rapporto tra il più grande al più piccolo. Se il rapporto non è molto grande, i vettori sono indipendenti.

Answer 6

Un altro modo per controllare che m riga vettori sono linearmente indipendenti, quando si inserisce in una matrice M di dimensioni mxn, è quello di calcolare

det(M * M^T)

vale a dire. il determinante di una matrice quadrata mxm. Sarà zero se e solo se M ha alcune righe dipendenti. Tuttavia eliminazione di Gauss dovrebbe essere in generale più veloce.

Answer 7

man Siamo spiacenti, il mio errore ...

---

Il codice sorgente fornito nel link qui sopra si rivela corretto, almeno il codice python Ho testato e il codice C ++ ho trasformato non genera la risposta giusta per tutto il tempo. (Mentre per l'exmample nel link qui sopra, il risultato è corretto :) -)

Per verificare il codice python, è sufficiente sostituire il mtx con

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

e il risultato restituito sarebbe come:

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

Tuttavia, ho un modo per uscire da questo. E 'solo questa volta ho trasformato il codice sorgente della funzione matalb rref a C ++. È possibile eseguire MATLAB e utilizzare il comando type rref per ottenere il codice sorgente di rref.

Basta notare che se si sta lavorando con alcuni davvero grande valore o molto piccolo valore, fanno uso che il long double tipo di dati in C ++. In caso contrario, il risultato sarà troncato e incompatibile con il risultato MATLAB.

ho condotto grandi simulazioni in ns2, e tutti i risultati osservati sono suono. spero che questo vi aiuterà e qualsiasi altra che hanno encontered il problema ...

Answer 8

Un modo molto semplice, che non è il computazionalmente più efficiente, è quello di rimuovere semplicemente le righe casuali fino m=n e quindi applicare il trucco determinante.

• m < n: rimuovere righe (rendono i vettori più breve) finché la matrice è quadrata, e quindi
• m = n: controllare se il determinante è 0 (come hai detto)
• m < n (il numero di vettori è superiore alla loro lunghezza): essi sono linearmente dipendente (sempre)
.

La ragione, insomma, è che qualsiasi soluzione al sistema di equazioni m x n è anche una soluzione al sistema di equazioni n x n (si sta cercando di risolvere Av=0). Per una spiegazione migliore, vedi Wikipedia , che spiega tutto meglio di me.