1. Sistemes triangulars:
   

Definició 1: Direm que una matriu A de dimensió nxn és singular si no és invertible, és a dir, si no existeix cap matriu A^-1 tal que A^-1A=AA^-1=I  (I és la matriu identitat de dimensió nxn). És cas contrari, és a dir si és invertible, direm que és regular.

Teorema -3: una matriu A de dimensió nxn és singular si i solament si les seues fileres o columnes no són linealment independents (és a dir, si es pot trobar una combinació lineal de les mateixes igual a 0)

Definició 2: Direm que U=(U_ij)_i,j=1...n és una matriu triangular superior si i solament si per a tot i,j=1...n, si i>j aleshores U_ij=0 . Direm que L=(L_ij)_i,j=1...n és una matriu triangular inferior si i solament si per a tot i,j=1...n, si i<j aleshores L_ij=0 .

Teorema 17: Si U=(U_ij)_i,j=1...n és una matriu regular triangular superior (de manera que per a tot i,j=1...n, U_ii≠0) aleshores el vector x tal que per a tot i=n ...1, x_i=(c_i-Σ_j=i+1...n U_ijx_j)/U_ii és la solució del sistema Ux=c (en cas que fora triangular inferior es resoldria de forma similar).

Teorema 18: La resolució d'un sistema Ux=c amb una matriu U regular triangular superior requereix (n²-n)/2 sumes i multiplicacions.

---

2. Eliminació gaussiana i estratègies de pivoteig:

Algoritme 2: Eliminació gaussiana per a triangular el sistema Ax=b transformant-lo en altre sistema equivalent:

1. Prendre k=1, A^(k)=A, b^(k)=b .
2. Si volem millorar l'eficiència utilitzant pivoteig parcial, determinar ν tal que |A^(k)_νk|= max_i=k...n(|A^(k)_ik|) i intercanviar les fileres ν & k .
   
3. Si A(k)kk (element pivot) és diferent de 0, aleshores, per a tot i=k+1...n, j=1...n, calcular mik=A(k)ik/A(k)kk, A(k+1)ij=A(k)ij-mikA(k)kj, b(k+1)i=b(k)i-mikb(k)k . En cas contrari, aturar-se: fi.
   
4. Si k<n, aleshores prendre k=k+1 i tornar al pas 2 .
5. Prendre U=A⁽ⁿ⁾, c=b⁽ⁿ⁾ .

Teorema 19: Si A és una matriu regular (amb columnes linealment independents), aleshores utilitzant pivoteig parcial es pot arribar a obtenir U i c amb l'algoritme 2, essent U una matriu no singular triangular superior, i el sistema Ux=c és equivalent al sistema Ax=b .

Teorema 20: Si la matriu U és simètrica i definida positiva, o és diagonalment dominant (estrictament si més no per a una filera), és possible realitzar l'eliminació gaussiana prescindint del pas 2 de l'algoritme 2 .

---

3. Descomposició LU:

Definició 3: Definim la matriu de permutació simple P^ij de dimensió nxn com la que resulta d'intercanviar les fileres i & j de la corresponent matriu identitat I.

Teorema 21: Per a tota matriu quadrada A de dimensió nxn, P^ijA és la matriu resultant d'intercanviar les fileres i & j de la matriu A i  AP^ij és la matriu resultant d'intercanviar les columnes i &j de la matriu A.

Teorema 22: P^ijP^ij=I (matriu identitat de dimensió nxn) .

Definició 4: Direm que P és una matriu de permutació si i solament si, para tot vector x de dimensió n, Px és el resultat d'una determinada reordenació dels elements del vector x.

Teorema 23: Tota matriu de permutació P és un un producte de matrius de permutació simples P^ij .

Definició 5: Anomenarem transformació gaussiana L^j de dimensió nxn a qualsevol matriu triangular inferior tal que per a tot i=1...n, L^j_ii=1 & per a tot i,k=1...n, si k≠j & i>k, aleshores L^j_ik=0 .

Teorema 24: Les transformacions gaussianes tenen les següents propietats:

1. Si m_ij=L^j_ij per a tot i=j+1...n i x és un vector de dimensió n, aleshores per a tot i=1...j, (L^jx)_i=x_i & per a tot i=j+1...n, (L^jx)_i= x_i+m_ijx_j .
   
2. (L^j)^-1 és una transformació gaussiana tal que, per a tot i=j+1...n, ((L^j)^-1)_ij=-L^j_ij .
3. Si m_ij=L^j_ij per a tot i=j+1...n i x és un vector de dimensió n, aleshores per a tot i=j+1...n, ((L^j)^-1x)_i= x_i-m_ijx_j .
4. Si x és un vector de dimensió n tal que x_j≠0 i per a tot i=j+1...n, m_ij=L^j_ij=x_i/x_j, aleshores per a tot i=j+1...n, ((L^j)^-1x)_i=0 .
5. Si k>j, L^jL^k=L^j+L^k-I .
6. El producte de transformacions gaussianes és sempre una matriu triangular inferior L tal que, per a tot  i=1...n, L_ij=1 .
7. Π_r=1...k L^r és una matriu triangular inferior L tal que, per a tot j=k+1...n, i=i+1...n, L_ij=0 .
   

Teorema 25: Amb la terminologia de l'algoritme 2, per a tot k=1...n-1, A(k+1)=(Lk)-1A(k) amb Lkik=mik=A(k)ik/A(k)kk, per a tot i=k+1...n .

Teorema 26: Si A és una matriu tal que el sistema Ax=b es pot transformar sense pivoteig en el sistema triangular superior equivalent Ux=c, aleshores existeix una matriu triangular inferior L=Πk=1...n-1 Lk tal que LU=A, essent Lii=1 per a tot i=1...n & Lik=mik=A(k)ik/A(k)kk per a tot k=1...n-1, i=k+1...n .

Teorema 27: Si k<i,j, aleshores P^ij(Π_r=1...k L^r)P^ij=Π_r=1...k (L')^r , on les (L')^r són altres transformacions gaussianes.

Teorema 28: Si A és una matriu regular, aleshores existeixen una matriu de permutació P, una matriu triangular superior U i una matriu triangular inferior L amb unos en la diagonal tals que PA=LU .

Teorema 29: Si A és una matriu regular, aleshores existeixen una matriu de permutació P, una matriu triangular superior U i una matriu triangular inferior L amb unos en la diagonal tals que el sistema Ax=b és equivalent al sistema Ux=y tal que Ly=Pb (per tal com Ux=y, Ly=Pb són sistemes triangulars, es poden resoldre d'acord amb el teorema 17 amb n²-n sumes i multiplicacions en total, que caldria sumar a les aproximadament n³/3 que requereix la descomposició LU).