Gaussian Elimination

To get a matrix into Reduced-Row-Echelon-Form do:

1. Find the first non-zero column starting. (starting from the left)
2. Swap the top row with some other row, if necessary, to get a nonzero value at the top of the column found above.
3. If the value that is now at the top of the column is not a one, divide the whole row by it, to get a leading 1.
4. Add multiples of the top row to the rows below, to obtain only zeros below the leading one.
5. Put the top row aside. GOTO back to the first step above until the entire matrix is in row echelon form.
6. Now from the last nonzero row and working upwards, add multiples of each row to the rows above to obtain zeros on top the leading 1's.

Here is an Example using Maple

    |\^/|     Maple V Release 3 (SUNY at Albany)
._|\|   |/|_. Copyright (c) 1981-1994 by Waterloo Maple Software and the
 \  MAPLE  /  University of Waterloo. All rights reserved. Maple and Maple V
 <____ ____>  are registered trademarks of Waterloo Maple Software.
      |       Type ? for help.
Warning: new definition for   norm
Warning: new definition for   trace
> A := matrix(4,5,[100,10,1,-1,0, 15,15,15,-1,0, 1,10,100,-1,396, -1,-1,1,0,1]);


                              [ 100  10   1   -1   0  ]
                              [                       ]
                              [  15  15   15  -1   0  ]
                         A := [                       ]
                              [  1   10  100  -1  396 ]
                              [                       ]
                              [  -1  -1   1    0   1  ]

> A1 := swaprow(A,1,4);


                              [  -1  -1   1    0   1  ]
                              [                       ]
                              [  15  15   15  -1   0  ]
                        A1 := [                       ]
                              [  1   10  100  -1  396 ]
                              [                       ]
                              [ 100  10   1   -1   0  ]

> A2 := mulrow(A1,1,-1);


                              [  1    1   -1   0   -1 ]
                              [                       ]
                              [  15  15   15  -1   0  ]
                        A2 := [                       ]
                              [  1   10  100  -1  396 ]
                              [                       ]
                              [ 100  10   1   -1   0  ]

> A3 := addrow(A2,1,2,-15);


                              [  1    1   -1   0   -1 ]
                              [                       ]
                              [  0    0   30  -1   15 ]
                        A3 := [                       ]
                              [  1   10  100  -1  396 ]
                              [                       ]
                              [ 100  10   1   -1   0  ]

> A4 := addrow(A3,1,3,-1);


                              [  1    1   -1   0   -1 ]
                              [                       ]
                              [  0    0   30  -1   15 ]
                        A4 := [                       ]
                              [  0    9  101  -1  397 ]
                              [                       ]
                              [ 100  10   1   -1   0  ]

> A5 := addrow(A4,1,4,-100);


                               [ 1   1    -1   0   -1 ]
                               [                      ]
                               [ 0   0    30  -1   15 ]
                         A5 := [                      ]
                               [ 0   9   101  -1  397 ]
                               [                      ]
                               [ 0  -90  101  -1  100 ]

> A6 := swaprow(A5,2,3);


                               [ 1   1    -1   0   -1 ]
                               [                      ]
                               [ 0   9   101  -1  397 ]
                         A6 := [                      ]
                               [ 0   0    30  -1   15 ]
                               [                      ]
                               [ 0  -90  101  -1  100 ]

> A7 := mulrow(A6,2,1/9);


                            [ 1   1     -1     0     -1  ]
                            [                            ]
                            [ 0   1   101/9  -1/9  397/9 ]
                      A7 := [                            ]
                            [ 0   0     30    -1     15  ]
                            [                            ]
                            [ 0  -90   101    -1    100  ]

> A8 := addrow(A7,2,4,90);


                             [ 1  1    -1     0     -1  ]
                             [                          ]
                             [ 0  1  101/9  -1/9  397/9 ]
                       A8 := [                          ]
                             [ 0  0    30    -1     15  ]
                             [                          ]
                             [ 0  0   1111   -11   4070 ]

> A9 := mulrow(A8,3,1/30);


                            [ 1  1    -1     0      -1  ]
                            [                           ]
                            [ 0  1  101/9   -1/9  397/9 ]
                      A9 := [                           ]
                            [ 0  0    1    -1/30   1/2  ]
                            [                           ]
                            [ 0  0   1111   -11    4070 ]

> A10 := addrow(A9,3,4,-1111);


                            [ 1  1    -1     0      -1   ]
                            [                            ]
                            [ 0  1  101/9   -1/9   397/9 ]
                            [                            ]
                     A10 := [ 0  0    1    -1/30    1/2  ]
                            [                            ]
                            [               781          ]
                            [ 0  0    0     ---   7029/2 ]
                            [                30          ]

> A11 := mulrow(A10,4,30/781);


                             [ 1  1    -1     0      -1  ]
                             [                           ]
                             [ 0  1  101/9   -1/9  397/9 ]
                      A11 := [                           ]
                             [ 0  0    1    -1/30   1/2  ]
                             [                           ]
                             [ 0  0    0      1     135  ]

> # The solution can now be obtained by "backsub" (backsubstitution),
> # or you may continue with more elementary operations to put zeros
> # on top of the leading ones.