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
- Prompt injection explained, November 2023 edition - 27th November 2023
- I'm on the Newsroom Robots podcast, with thoughts on the OpenAI board - 25th November 2023
- Weeknotes: DevDay, GitHub Universe, OpenAI chaos - 22nd November 2023
- Deciphering clues in a news article to understand how it was reported - 22nd November 2023
- Exploring GPTs: ChatGPT in a trench coat? - 15th November 2023
- Financial sustainability for open source projects at GitHub Universe - 10th November 2023
- ospeak: a CLI tool for speaking text in the terminal via OpenAI - 7th November 2023
- DALL-E 3, GPT4All, PMTiles, sqlite-migrate, datasette-edit-schema - 30th October 2023
- Now add a walrus: Prompt engineering in DALL-E 3 - 26th October 2023
- Execute Jina embeddings with a CLI using llm-embed-jina - 26th October 2023