# Gaussian elimination

## Gauss Elimination

We consider the system of linear equations $Ax = b$ or

$\left[ \begin{matrix} {a_{11} } & {a_{12} } & {...} & {a_{1n} } \\ {a_{21} } & {a_{22} } & . & {a_{21} } \\ . & . & . & . \\ {a_{n1} } & {a_{n1} } & . & {a_{nn} } \\ \end{matrix} \right] \left[ \begin{matrix} {x_1 } \\ {x_2 } \\ . \\ {x_n } \\ \end{matrix} \right] = \left[ \begin{matrix} {b_1 } \\ {b_2 } \\ . \\ {b_n } \\ \end{matrix} \right]$

To perform Gaussian elimination starting with the above given system of equations we compose the augmented matrix equation in the form:

$\left[ \begin{matrix} {a_{11} } & {a_{12} } & {...} & {a_{1n} } \\ {a_{21} } & {a_{22} } & . & {a_{21} } \\ . & . & . & . \\ {a_{n1} } & {a_{n1} } & . & {a_{nn} } \\ \end{matrix} \left| \begin{matrix} {b_1 } \\ {b_2 } \\ . \\ {b_n } \\ \end{matrix} \right. \right] \left[ \begin{matrix} {x_1 } \\ {x_2 } \\ . \\ {x_n } \\ \end{matrix} \right]$

After performing elementary raw operations the augmented matrix is put into the upper triangular form:

$\left[ \begin{matrix} {a_{11}^' } & {a_{12}^' } & {...} & {a_{1n}^' } \\ 0 & {a_{22}^' } & . & {a_{2n}^' } \\ . & . & . & . \\ 0 & 0 & . & {a_{nn}^' } \\ \end{matrix} \left| \begin{matrix} {b_1^' } \\ {b_1^' } \\ . \\ {b_1^' } \\ \end{matrix} \right. \right]$

By using the formula:

$x_i = {1 \over {a_{ii}^' }}\left( {b_i^' - \sum\limits_{j = i + 1}^n {a_{ij}^' x_j } } \right)$

Solve the equation of the kth row for xk, then substitute back into the equation of the (k-1)st row to obtain a solution for (k-1)st raw, and so on till k = 1.