Gauss-Jordan Elimination

Consider the following equation:

$$\boldsymbol{A}\cdot\boldsymbol{x} = \boldsymbol{b}$$ (5.1)

The equation can be solved as follows:

1.

divide the first row by A₁₁, so that the new A₁₁ becomes 1

2.

subtract from the second row A_2i the first row multiplied by A₂₁, so that after that subtraction A₂₁ becomes 0

3.

subtract from the third row A_3i the first row multiplied by A₃₁, so that after that subtraction A₃₁ becomes 0

4.

$\ldots$

5.

subtract from the $n^{\textrm{{\scriptsize th}}}$ row A_ni the first row multiplied by A_n1, so that after that subtraction A_n1 becomes 0. Now the first column of matrix A is

$$\left( \begin{array}{c} 1 \\ 0 \\ 0 \\ \vdots \\ 0 \end{array} \right)$$

6.

divide the second row by A₂₂, so that the new A₂₂ becomes 1

7.

subtract from the first row A_1i the second row multiplied by A₁₂, so that after that subtraction A₁₂ becomes 0

8.

subtract from the third row A_3i the second row multiplied by A₃₂, so that after that subtraction A₃₂ becomes 0

9.

subtract from the fourth row A_4i the second row multiplied by A₄₂, so that after that subtraction A₄₂ becomes 0

10.

$\ldots$

11.

subtract from the $n^{\textrm{{\scriptsize th}}}$ row A_ni the second row multiplied by A_n2, so that after that subtraction A_n2 becomes 0. Now the first two columns of matrix A

$$\left( \begin{array}{cc} 1 & 0 \\ 0 & 1 \\ 0 & 0 \\ \vdots & \vdots \\ 0 & 0 \end{array} \right)$$

12.

$\ldots$

At the same time matching operations must be performed on vector b.

When the process is finished we get the following new equation

$$\left( \begin{array}{ccccc} 1 & 0 & 0 & \cdots & 0 \\ 0 &... ...1 \\ b_2 \\ b_3 \\ \vdots \\ b_n \end{array} \right)$$ (5.2)

The coefficients b_i are quite different now, but the equation can be solved trivially. And so, we get:

x_n = b_n (5.3)

In matrix notation the operations performed on A amount to having found such matrix A^-1 that

$$\boldsymbol{A}^{-1} \cdot \boldsymbol{A} \cdot \boldsymbol{x}... ...cdot\boldsymbol{x} = \boldsymbol{A}^{-1}\cdot \boldsymbol{b}$$ (5.4)

Now, if during the computation we were to perform all the motions not only on vector b, but also on another matrix, which has been initialized to 1, we would end up with A^-1 inside that matrix when the whole thing is over.

When these computations are carried out solutions can be found simultaneously to systems of equations with various right hand sides (but always the same left hand side A so vectors b are often aligned into a matrix, which doesn't have to be square, and that matrix is then also accompanied by a square matrix that has been initialized to 1, so as to yield A^-1 as well.

Although the above comprises the heart of the method there is one complication that we have to incorporate. It may happen that a particular diagonal term A_kk is zero or very small. In that case dividing whatever's left of A_ki by A_kk may lead to overflows. If this is the case then the solution is to interchange the rows or the columns so as to place the largest element of A_ki, which is called a pivot in the A_kk position, and get the small one in the pivot's old location. This is an essential part of the Gauss-Jordan Elimination technique and the program must never be written without pivoting.