AcademyLinear Systems
Academy
Gauss-Jordan Elimination
Level 1 - Linear Algebra topic page in Linear Systems.
Principle
Gauss-Jordan elimination uses elementary row operations to transform an augmented matrix into reduced row echelon form. Once the matrix is reduced, the solution set can be read directly.
It is a systematic algorithm: create pivots, clear below them, scale them to \(1\), and clear above them.
Notation
\([A\mid\mathbf b]\)
an augmented matrix
\(R_i\)
row i
\(\operatorname{rref}\)
reduced row echelon form
\(\text{pivot}\)
the leading non-zero entry used to eliminate other entries
\(\sim\)
row-equivalent
The Core Method
Use this routine.
- Choose the leftmost column with a non-zero available entry.
- Swap rows if needed to move a non-zero entry into the pivot position.
- Scale the pivot row so the pivot becomes \(1\).
- Use row replacement to make every other entry in the pivot column zero.
- Move down and right to choose the next pivot.
- Continue until no more pivots can be created.
The final matrix is row-equivalent to the original augmented matrix:
Reduction target
\[[A\mid\mathbf b]\sim\operatorname{rref}([A\mid\mathbf b])\]
Worked Cases
Question
Use Gauss-Jordan elimination on \(\begin{pmatrix}1&2&|&5\\3&7&|&16\end{pmatrix}\).
Answer
Start with \(\begin{pmatrix}1&2&|&5\\3&7&|&16\end{pmatrix}\). Use \(R_2\leftarrow R_2-3R_1\): \(\begin{pmatrix}1&2&|&5\\0&1&|&1\end{pmatrix}\). Clear above the second pivot with \(R_1\leftarrow R_1-2R_2\): \(\begin{pmatrix}1&0&|&3\\0&1&|&1\end{pmatrix}\). Therefore \(x=3\) and \(y=1\).
Examples
Question
Why does Gauss-Jordan elimination clear entries above pivots as well as below them?
Answer
Clearing below pivots gives echelon form, which usually still requires back substitution. Clearing above pivots produces RREF. In RREF, pivot variables are isolated, so the solution set can be read directly from the rows.