Source
Adapted from my own handwritten and hand-typed notes from Year 1 to Year 3 of my EEE degree
Gaussian elimination is a systematic way to solve a linear system. It uses row operations to turn the augmented matrix into a triangular (row echelon) form, then solves by back substitution.
Row Echelon Form
The first nonzero entry of each nonzero row is called a pivot.
A matrix is in row echelon (RE) form when:
- all zero rows are at the bottom
- each pivot is to the right of the pivot in the row above
- every entry below a pivot is zero
It is in reduced row echelon (RRE) form if, in addition:
- every pivot is 1
- every other entry in a pivot column is 0
The RRE form of a matrix is unique. Reducing all the way to RRE form is called Gauss-Jordan elimination.
Method
Steps:
- Write the augmented matrix
- Take the leftmost nonzero column as the pivot column. Swap rows if needed so the top entry is nonzero
- Use row operations to make every entry below the pivot zero
- Cover that row and repeat on the rows below until the matrix is in RE form
- Back substitute from the last equation upwards (or keep going to RRE form and read off the answer)
Worked Example
Solve , , .
Back substitution:
So .
What the RE Form Tells You
Once the matrix is in RE form you can read off the type of solution straight away. A row like means no solution, and fewer pivots than unknowns means free variables. This is covered in Consistency and Number of Solutions.
Software
For big systems use software, e.g.
rref([A b])orA\bin MATLAB.