In continuare vom descrie algoritmul propriu-zis. Pornim cu un indice pentru linii, sa-l notam $i$, si un indice pentru coloane, $j$, initializate initial cu $1$. Cautam pe coloana $j$, o linie $x$, $i &le; x$ astfel incat $A{~x,j~} &ne; 0$. Daca aceasta linie nu exista, inseamna ca necunoscuta cu indicele $j$ este variabila libera, iar noi incrementam indicele $j$. Altfel, interschimbam liniile $i$ si $x$ si impartim toata ecuatia de pe linia $i$ la $A{~i,j~}$, pentru a face coeficientul A{~i,j~} egal cu $1$, usurand calculele urmatoare. In continuare vom scadea, din toate ecuatiile $u$, $i < u$, ecuatia $i$ inmultita cu o valoare $z{~u~}$, astfel incat toti coeficientii A{~u,j~} sa devina $0$. Avem astfel $A{~u,j~} - z{~u~} * A{~i,j~} = 0 => z{~u~} = A{~u,j~} / A{~i,j~}$, dar cum $A{~i,j~} = 1$, $z{~u~} = A{~u,j~}$. Aceasta reducere este necesara pentru respectarea conditiei $(1)$, avand in vedere ca nu putem avea $x &ne; i$ cu $p{~x~} = p{~i~}$. Incrementam pe $i$ si $j$ si reluam procedeul de la inceput. Algoritmul se incheie cand $i > N$ sau $j > M$. Complexitatea acestuia este $O(N^3^)$ ca timp si $O(N^2^)$ ca memorie.

Acum matricea respecta relatia $(1)$ si putem incepe sa calculam valorile necunoscutelor. Luam ecuatiile in ordine de la $N$ spre $1$, gasim pozitia $p{~i~}$, iar $x{~p{~i~}~}$ va fi dat de relatia $x{~p{~i~}~} = A{~i,N+1~} - A{~i,N~} * x{~N~} - A{~i,N-1~} * x{~N-1~} - ... - A{~i,p{~i~}+1~} * x{~p{~i~}+1~}$. Relatia $(1)$ ne garanteaza ca $x{~p{~i~}+1~}, x{~p{~i~}+2~}, ... , x{~N~}$ vor fi calculate anterior. Daca pe parcurs gasim o linie de forma $(0, 0, 0, ... , 0, X)$ (doar rezultatul ecuatiei este nenul), sistemul nu are solutie.

Acum matricea respecta relatia $(1)$ si putem incepe sa calculam valorile necunoscutelor. Luam ecuatiile in ordine de la $N$ spre $1$, gasim pozitia $p{~i~}$, iar $x{~p{~i~}~}$ va fi dat de relatia $x{~p{~i~}~} = A{~i,M+1~} - A{~i,M~} * x{~M~} - A{~i,M-1~} * x{~M-1~} - ... - A{~i,p{~i~}+1~} * x{~p{~i~}+1~}$. Relatia $(1)$ ne garanteaza ca $x{~p{~i~}+1~}, x{~p{~i~}+2~}, ... , x{~M~}$ vor fi calculate anterior. Daca pe parcurs gasim o linie de forma $(0, 0, 0, ... , 0, X)$ (doar rezultatul ecuatiei este nenul), sistemul nu are solutie.

O implementare de $100$ de puncte gasiti 'aici':job_detail/608486?action=view-source. Acest algoritm poate fi aplicat cu succes pentru sisteme de ecuatii in care coeficientii, necunoscutele si rezultatele sunt doar $0$ si $1$, iar operatorul $+$ din ecuatii este inlocuit de $XOR$.