Gauss Jordan Elimination
1st October 2002
Gauss-Jordan Elimination
The steps of the Gauss-Jordan elimination process are as follows:
- Input augmented matrix A
- Get the reduced echelon form for A using elementary row operations. This is done by first creating leading 1s, then ensuring that columns containing leading 1s have only 0s above and below the leading 1, column by column starting with the first column.
- The matrix in reduced echelon form will either give the solution or demonstrate that there is no solution.
Two matrices A and B are row equivalent if A =>* B by elementary row operations. During the process of Gauss-Jordan elimination all matrices are row equivalent to the original and each other.
Example
x1 + 2x2 + x3 = 1 2x1 + 4x2 - x3 = -1 [ 1 2 1 1 ] [ 1 2 1 1 ] [ 2 4 -1 -1 ] => [ 0 0 -3 -3 ] R2 := R2 - 2R1 [ 1 2 1 1 ] [ 0 0 1 1 ] R2 := R2 / -3 To fix column 3: [ 1 2 0 0 ] R1 := R1 - R2 [ 0 0 1 1 ] (this is in reduced echelon form) So... x1 = -2x2 x2 = anything x3 = 1 The system has many solutions.
In general, any columns without a leading one of them correspond to a variable that can be any value.
The difficult part of Gauss-Jordan elimination is the bit in the middle—deciding which columns to manipulate and how to convert them in to leading 1s. Consider a matrix An x m in the middle of the computation. Some number il of rows have leading 1s in them and some number j of columns have been processed. j ≥ il
[ a1 ... a1m b1 ] A = [ ... ] [ an ... anm bn ] The matrix now looks like this: j 0 0 ... 0 1 0 ... 0 ... ... il 0 0 ... 0 0 0 ... 1 ... ... 0 0 ... 0 0 0 ...
Next step: Increment j. Look in column j for aoj ≠ 0, with i > il—now interchange row i and row il + 1 (if nothing found, move on to next columns. Create a leading 1, then reduce column j.
Pseudo code for Gauss-Jordan elimination
il = 0 (number of leading 1s created) for j = 1 ... m do: if ∃ i > il such that aij ≠ 0 then: il = il + 1 interchange row i and row il (this brings the new row just below the row you have just done) divide row i by ailj creating a leading 1 Reduce all other entries in the column to 0
Complexity
Suppose A is n x m. We can measure complexity by the number of +, -, *, / operations that are carried out. To do this we look at the pseudo code. If we run the main loop m times:
- The interchange operation takes 2m operations
- Dividing row i by ailj takes m-j operations
- The reduce other entries bit takes nm operations
So the complexity of the operation is O(mnm) or O(nm2)
Additional Resources
- Wikipedia has an excellent explanation of Gauss-Jordan Elimination
- The Gauss-Jordan elimination game is a javascript puzzle
- This page explains the Gauss-Jordan algorithm in a bit more depth
Homogeneous Systems
A system of linera equations is homogeneous if all of the constant terms are 0. For example:
3x1 + 2x2 = 0 x1 - x2 = 0
A homogeneous system in n variables always has the trivial solution x1 = x2 = ... = 0—so there is no chance that the system will have no solutions, reducing the possible outcomes from three to two.
Theorem
A homogeneous system with more unknowns than equations always has many solutions
Proof
Suppose the system has n equations with m unknowns, and m > n.
Let A = the augmented matrix
Find R = reduced echelon form of A using Gauss-Jordan elimination.
m 1 . . . . . . . 0 1 . . . . . . n 0 0 1 . . . . . 0 0 0 1 . . . . 0 0 0 0 1 . . .
R has ≤ n leading 1s, so at least m-n of the variables can take any value. This shows that there are many solutions.
Example
x1 + 2x2 + x3 = 0 x2 - x3 = 0
This is the intersection of two planes through the origin in 3D space.
Matrix notation for a system of equations
[ a11x1 + ... + a1mxm = b1 ] [ ... ] can be written as AX = B [ an1x1 + ... + anmxm = bn ] [ a1 ... a1m ] A = [ ... ] [ an1 ... anm ] [ x1 ] [ b1 ] X = [ . ] B = [ ] [ xn ] [ bn ]
More recent articles
- OpenAI DevDay: Let’s build developer tools, not digital God - 2nd October 2024
- OpenAI DevDay 2024 live blog - 1st October 2024
- Weeknotes: Three podcasts, two trips and a new plugin system - 30th September 2024