Gaussian elimination

Gaussian elimination

1. Base Case

   • There is only one equation and one unknown: ax = b.  This can be solved directly : x = b/a. 
   • Special Base Case 1 : Contradictory equation
     • ax = b and a = 0 then 0 = b but if in reality b !=0 then the equation is contradictory and cannot be solved  (1  -2 |  3)       ------>    (1  -2 |  3) (2  -4 |  7)       ------>    (0   0 |   1) 
   • Special Base Case 2 : Irrelevant Equation
     • ax = b and a = 0 , b = 0 then  0 = 0 which means that the equation doesn't constrain the value of x in any way.The unknown can be chosen freely. 

2. General Case/Recursive Case

   • n equations containing n unknowns. Use the first equation to eliminate the first unknown in the remaining n - 1 equations.Those    n - 1 equations then only contain n - 1 unknowns and Gaussian Elimination can be applied recursively to those ( 1   5  -2 | -11)  ( 3  -2   7 |   5  ) ( -2  -1 -1 |   0 )
   • Special Recursive Case 1
     • Can't use the first equation for eliminating the first unknown.Simply exchange the first equation with another one for which the first coefficient is not zero, and run the algorithm on the rearranged system.
   • Special Recursive Case 2
     • Can't use any of the given equations to eliminate the first unknown. This is like "Special Base Case 2", in that it means that the first variable is not constrained at all by the given system.The algorithm should report back that the first variable can be chosen freely.