[C/C++] Span di una matrice

[scugnix]

ciao a tutti volevo sapere se qualcuno aveva un algoritmo c o c++ che facesse lo span di una matrice.
Cioè mi spiego meglio data una matrice con tutti 0 e 1 me permetta di fare l'eliminazione di gauss(quindi ottenere una matrice a scale ) e successivamente trovare tutte le possibili soluzioni.
???????????????????????????????????

grazie

[ibykos]

for (i=1;i<N;i++){
	for (j=i;j<N;j++){
		coefficiente = -matrice[j-1][i]*matrice[j][i];
		moltiplica tutta la riga per il coefficente
		somma la riga i-esima con la riga (i-1)esima
	}
}

Un algoritmo simile a questo trasforma rende una matrice in forma triangolare con il metodo di gauss.

Dato poi un sistema A * x = b, con A e b noti, calcorare x

Bisogna trovare la matrice inversa di A e moltiplicare entrambi i membri per essa

L'inversa di una N*N (con N anche grande) si trova in questo modo:

dichiari una matrice A_inv di dimensioni pari ad Acon tutti 1 sulla diagonale e zero in altri posti.

esegui sulla matrice A_inv tutte le operazioni che esegui sulla matrice A (sottrazione di riga, moltiplicazione di riga per coefficiente) finchè non ottieni una matrice triangolare superiore.
Eseguendo di nuovo il metodo di Gauss ("girato al contrario") trasformi A in una matrice diagonale (A_inv non ha ancora significato).
Infine moltiplichi ogni riga di A (quindi anche di A_inv) per un coefficiente tale da rendere A una matrice con tutti 1 sulla diagonale e 0 altrove.
A questo punto A_inv è effettivamente l'inversa di A e non ti resta che moltiplicarla per il vettore b per ottenre il risultato.

Spero di esserti stato d'aiuto
ciao!

[scugnix]

mi spiego un po meglio :
Cominciamo dicendo che io parto da una serie di numeri del genere e tengo in considerazione anche il segno(numeri a destra dell'=)

-3808 = -2^5 * 7 * 17.
-12168 = -2^3 * 3^2 * 13^2.
-32928 = -2^5 * 3 * 7^3.
-49392 = -2^4 * 3^2 * 7^3.
384 = 2^7 * 3.
25704 = 2^3 * 3^3 * 7 * 17.
29952 = 2^8 * 3^2 * 13.

da questi ottengo la sottostante matrice(la prima colonna è fittizzia è solo per far capire che la prima riga è il segno dei numeri ,la seconda è l'esponente de primo 2 ecc... )

+/- 1 1 1 1 0 0 0
2 5 3 5 4 7 3 8
3 0 2 1 2 1 3 2
7 1 0 3 3 0 1 0
13 0 2 0 0 0 0 1
17 1 0 0 0 0 1 0

a questo punto faccio il modulo 2 e ottengo:

+/- 1 1 1 1 0 0 0
2 1 1 1 0 1 1 0
3 0 0 1 0 1 1 0
7 1 0 1 1 0 1 0
13 0 0 0 0 0 0 1
17 1 0 0 0 0 1 0

qui io risolvo gauss ottenendo la matrice triangolare ed è tutto OK!!!!
da adesso il dramma perche io devo ottenere le soluzioni dell'equazioni ricavate dalla matrice triagolare tutte = 0!!!!
(es.
x1+x2+x3=0
x1+x3=0
x1=0)
Quindi il problema è risolvendo il sistema come posso trovare tutte le soluzioni visto che il risultato finale del mio ipotetico esercizio potrebbe essere:
(x1=0
x2=x3
ecc...)
cioè come faccio a trovare tutte le combinazioni della soluzione sostituendo una volta 1 e poi 0??????????????????????
le soluzioni sarano del tipo riportato qui sotto!!!!!!!!!!!!!!

0 1
0 1
1 1
1 1
1 0
0 1
0 0

[ibykos]

Fatico a capirti :-)
Se il tuo problema è di tipo algebra lineare (mi sembra di aver capito che implica qualcosa del genere) si risolve come ti ho detto.
In ogni caso scrivo un esempio

Ho il seguente sistema di equazioni

3x-y-3z=4
x+y+z= 6
x-y-z=0

Che modello con la matrice A

+3 -1 -3
+1 +1 +1
+1 -1 -1

e con il vettore b

4
6
0

In totatle abbiamo

+3 -1 -3 x 4
+1 +1 +1 y = 6
+1 -1 -1 z 0

comincio a ridurre la matrice in forma triangolare

il coefficiente R12, quello per cui devo moltiplicare la prima riga per annullare il primo elemento della seconda vale = - (+1/+3) = -1/3

quindi la seconda riga diventa 0 4/3 2 14/3

ed il sistema ( moltiplico la seconda riga per 3 per ragioni di semplicità )diventa

+3 -1 -3 x 4
+0 +4 +6 y = 14
+1 -1 -1 z 0

ripeto l'operazione ed ottengo:

+3 -1 -3 x 4
+0 +4 +6 y = 14
+0 -2 +0 z -4

procedo fino alla triangolare

+3 -1 -3 4
0 +4 +6 14
0 0 3 3

A questo punto rieseguo il metodo di Gauss fino ad ottenere una matrice diagnale, cioè sommo la riga 3 (moltiplicata per un coefficiente opportuno) con la riga 1

Il primo coefficiente è - ( -3/3 ) = +1

da cui la matrice diventa

+3 -1 0 7
0 +4 +6 14
0 0 3 3

continuo fino alla diagonalizzazione

+3 0 0 9
0 +4 0 8
0 0 3 3

Infine moltiplico le righe della matrice per l'inverso del loro elemento non nullo ed ottengo

1 0 0 3
0 1 0 2
0 0 1 1

Raggiunto questo punto nel vettore b ho le soluzioni del sistema.

Se devi ottenere le soluzioni del sistema con le equazioni poste uguale a zero basta che poni b = 0 0 0.
ciao!

P.S.

purtoppo è saltata la formattazione (dannato html), le x,y,z che vedi in colonna devono essere ignorate

[scugnix]

Sei stato gentilissimo grazie adesso provo a vedere questo implementandolo nel mio algoritmo!!!!

GRAAAAAAAZZZZZZZIIIIIIIIIIIIIIIIEEEEEEEEEEEEEEEE