Appendix 4.
Gauss-Jordan Elimination

(c) 2017 by Barton Paul Levenson

You use Gauss-Jordan elimination to find the inverse of a matrix. The steps are:

1. Put together an "augmented matrix." This is your original matrix with an identity matrix of the same size glued on at the right. In other words, you double the number of columns and fill in the new ones with an identity matrix.
2. Apply "line operations" until the matrix on the left becomes an identity matrix. The matrix on the right will now be the inverse of the original matrix.

The basic line operations are scaling and eliminating.

"Scaling" a line changes it so the element in the left-hand matrix which is on the main diagonal--the "pivot element"--becomes a 1. In other words, you just multiply every element in that line by the appropriate constant. Let's say you want to scale the middle line of this matrix (make that 5 into a 1):

│ 2   7   6   │   1   0   0 │
│ 1   5   0   │   0   1   0 │
│ 9   3   5   │   0   0   1 │

You just multiply the second line through by 1/5, or 0.2:

│ 2     7     6   │   1     0     0 │
│ 0.2   1     0   │   0     0.2   0 │
│ 9     3     5   │   0     0     1 │

"Eliminating" is a four step operation:

1. Scale the line you're working on.
2. Scale a line above or below it so the element in the same column is also 1. The 1 in the column you're working from is the "pivot element."
3. Subtract the target line from the pivot line.
4. Replace the target line with the result. I'll demonstrate by eliminating the top element in column 2 from the matrix shown just above. Line b is the line with our pivot element; line a is the target line. I'll use fractions instead of decimals to be clearer:

                   a │  2     7   6    │   1     0    0 │
Original:          b │  1/5   1   0    │   0     1/5  0 │
                   c │  9     3   5    │   0     0    1 │

Multiply line      a │  2/7   1   6/7  │   1/7   0    0 │
a by 1/7:          b │  1/5   1   0    │   0     1/5  0 │
                   c │  9     3   5    │   0     0    1 │

Subtract a         b │  1/5   1   0    │   0     1/5  0 │
from b:          - a │  2/7   1   6/7  │   1/7   0    0 │
                     ——————————————     —————————————
                     -3/35  0  -6/7  |  -1/7   1/5  0

Replace a with     a │ -3/35  0  -6/7  │  -1/7   1/5  0 │
the result:        b │  1/5   1   0    │   0     1/5  0 │
                   c │  9     3   5    │   0     0    1 │

To do this systematically, you work from the top line to the bottom. Start with element 1, 1 (the very top left element) as the pivot element, then go to 2, 2 for the second line, etc.

Eliminating elements in later lines often leaves earlier pivot elements no longer equal to 1, so you have to scale all the lines again as the last step.

Not all matrices can be inverted! If you try entering the same data for two independent variables, or have too many variables compared to observations, or just have the bad luck to pick data that results in a "nonsingular" matrix, Gauss-Jordan elimination will fail--and it will always fail the same way, trying to divide by zero.

What follows on the next page is a complete Gauss-Jordan elimination procedure carried out on the 2 x 2 matrix A, as an example.

  Operation                A               Identity       

Problem           a  │  2      3     │     1      0      │
statement:        b  │  1      7     │     0      1      │


a <= a x 0.5:     a  │  1      1.5   │     0.5    0      │
                  b  │  1      7     │     0      1      │


                  a  │  1      1.5   │     0.5    0      │
b <= a - b:       b  │  0     -5.5   │     0.5   -1      │


                  a  │  1      1.5   │     0.5    0      │
b <= b / -5.5:    b  │  0      1     │    -0.091  0.182  │


a <= a x 2/3:     a  │  0.667  1     │     0.333  0      │
                  b  │  0      1     │    -0.091  0.182  │


a <= b - a:       a  │ -0.667  0     │    -0.424  0.182  │
                  b  │  0      1     │    -0.091  0.182  │


                        Identity               A-1       

a <= a x -1.5:    a  │  1      0     │     0.636 -0.273  │
                  b  │  0      1     │    -0.091  0.182  │

Proof:

A               A-1               I

│ 2 3 │  x  │  0.636 -0.273 │  =  │ 1 0 │
│ 1 7 │     │ -0.091  0.182 │     │ 0 1 │