Gaussian Elimination

Recall that any nonsingular matrix $A$ can be reduced to upper triangular matrix $U$ with all non-zero diagonal elements by elementary row operations.

Recall also that the elementary row operations can be realized by multiplication of the original matrix $A$ by the so called elementary matrices.

Moreover, we can reduce $A$ to $U$ by first applying elementary row operations of the second type (permutation of rows), and then applying elementary row operations of type 1. In other words, $\exists P_{1}, \dots, P_{k}$ and $E_{1}, \dots, E_{m}$ such that $E_{1} \dots E_{m} \cdot P_{1} \dots P_{k} A = U$ .
Denoting $E^{- 1} = L$ , we obtain the well known permuted $L U$ factorization of a nonsingular matrix:

P A = L U

$U$ is upper triangular
$L$ is special lower triangular
$P$ is a permutation matrix

Once the permuted $L U$ factorization is obtained, it is easy to solve $A x = b$ .

$P A x = P b = \tilde{b} \Rightarrow L U x = \tilde{b}$
Solve $L y = \tilde{b}$ by forward substitution
Solve $U x = y$ by back substitution