Il metodo di eliminazione di Gauss realizza la seguente fattorizzazione (o scomposizione) della matrice A:

A=LU

Dove  è una matrice triangolare superiore e L è la matrice triangolare inferiore dei moltiplicatori, ovvero:

Per rendercene conto poniamo 

In termini di componenti tale relazione equivale a 

Dalle formule del MEG si ha:

e quindi :

Si noti cme moltiplicare  sinistra una matrice per ha come effetto la sottrazione da ogni  riga  (i=k+1,...,n) dalla riga . Allora :

Osservazioni: il prodotto di matrici triangolari o l'inversa di una matrice triangolare, sono ancora matrici triangolari. Pertanto è una matrice triangolare inferiore.

Inoltre si può verificare che .

Nel caso si adotti una strategia pivotale, ad esempio per righe, ricordando la formula relativa alla matrice di permutazione si ha:

dove abbiamo indicato con   la matrice di permutazione , essendo r e k gli indici delle righe che si cambiano tra loro. Allora per U si avrà la seguente espressione:

Posto

si ha allora che L è triangolare inferiore e si ottiene:

Il sistema di partenza si trasforma così nel sistema

Ogniqualvolta si conoscano i fattori triangolari L ed U di una matrice A, la risoluzione del problema fattorizzato comporta semplicemente la soluzione di 2 sistemi triangolari che possono essere risolti in parallelo.

In effetti, nel caso in cui non si ricorra alla pivotazione si ottiene:

Dunque si ottengono 2 sistemi triangolari risolvibili con n(n+1) flops. Nel caso si utilizzi la strategia pivotale per righe si avrebbe invece:

Esistono comunque dei sistemi per i quali a priori il MEG può essere realizzato senza ricorrere al pivoting (supponendo al solito di lavorare in aritmetica esatta).