Gauss-Jordan Elimination

Gauss-Jordan Elimination is a method for solving a linear system of equations. The method is named after Carl Friedrich Gauss and Wilhelm Jordan.

The content in today's blog is taken from Linear Algebra with Applications by Gareth Williams.

Consider the following system of linear equations:

x₁ - x₂ + 2x₃ = 3

2x₁ - 2x₂ + 5x₃ = 4

x₁ + 2x₂ - x₃ = -3

2x₂ + 2x₃ = 1

To use Gauss-Jordan Elimination, we start by representing the given system of linear equations as an augmented matrix.

Definition 1: Augmented Matrix Form

An augmented matrix is a matrix representation of a system of linear equations where each row of the matrix is the coefficients of the given equation and the equation's result.

Example 1:

The following system of linear equations:

x₁ - x₂ + 2x₃ = 3

2x₁ - 2x₂ + 5x₃ = 4

x₁ + 2x₂ - x₃ = -3

2x₂ + 2x₃ = 1

would be represented as:



The goal of Gauss-Jordan elimination is to transform the matrix into reduced echelon form.

Definition 2: Reduced Echelon Form

A matrix is said to be in reduced echelon form if:

(1) Any rows consisting entirely of zeros are grouped at the bottom of the matrix.

(2) The first nonzero element of any row is 1. This element is called a leading 1.

(3) The leading 1 of each row after the first is positioned to the right of the leading 1 of the previous row.

(4) If a column contains a leading 1, then all other elements in that column are 0.

Here are some examples of matrices that are not in reduced echelon form.

The matrix below violates (1). The rows consisting entirely of 0's are not grouped at the bottom.



The matrix below violates (2). In row 2, the first nonzero element is not a 1.



The matrix below violates (3). In row 3, the leading 1 is not to the right of the leading 1 in row 2.



The matrix below violates (4). The column associated with the leading 1 in row 2 contains a nonzero value.



Below are some examples of matrices that are in reduced echelon form:







Next, we need to use elementary row operations so the matrix results in reduced echelon form. The elementary row operations are operations that the result matrix represents the same system of linear equations. In other words, the two matrices are row equivalent.

Definition 3: Row Equivalence (Equivalent Systems)

Two matrices are row equivalent if they represent the same system of linear equations. They are also called equivalent systems.

The following three elementary operations preserve row equivalence. That is, the resulting matrix is row equivalent to the matrix before the operation.

(1) Interchanging two rows
(2) Multiplying the elements of a row by a nonzero constant
(3) Adding the elements of one row to the corresponding elements of another row.

(1) is clear. Changing the order of the linear equations does not change the values that solve them. (2) is equivalent to multiplying the same value to both sides of the equation. (3) is the idea that two linear equations imply that their sum is also a valid linear equation. In actual practice, we will combine (2) and (3) to get: (4) Add a multiple of the elements of one row to the corresponding elements of another row.

So, the following elementary operations result in a matrix that is row equivalent to the previous matrix:

Definition 4: Elementary Operations

(1) Row Exchange: The exchange of two rows.
(2) Row Scaling: Multiply the elements of a row by a nonzero constant.
(3) Row Replacement: Add a multiple of the elements of one row to the corresponding elements of another row.

Once the matrix is in reduced echelon form, we can convert the matrix back into a linear system of equations to see the solution.

Here's the full algorithm:

Definition 5: Gauss-Jordan Elimination

(1) Represent the linear system of equations as a matrix in augmented matrix form

(2) Use elementary row operations to derive a matrix in reduced echelon form

(3) Write the system of linear equations corresponding to the reduced echelon form.

Algorithm 1: Gauss-Jordan Elimination Algorithm

(1) Let A = an m x n matrix with m rows and n columns.

(2) Let k = 1, A_k = A, i=1

(3) If A_k is all zero's, then we are done and the A is in reduced echelon form.

(4) Let C_v be the first nonzero column in A_k such that C_v is not all zero's and v ≥ i.

(5) Let a_u,v be the first nonzero element in C_v such that u ≥ k.

(6) Let R_u be the row in A where a_u,v is found in C_v.

(7) R_u = R_u*(1/a_u,v) [After this, R_u has a leading 1, see proof below for explanation]

(8) If u ≠ k, then exchange R_u and R_k.

(9) For each row R_w in A, if w ≠ k, then R_w = R_w + (-a_w,v)*R_k [After this, the only nonzero element in C_v is found at a_k,v, see proof below for explanation if needed]

(10) If k = m, then we are done and A is in reduced echelon form.

(11) Otherwise, we designate a partion of A_k such that:



[Note: In other words, A_k+1 = all but the top row of A_k]

(12) Let k = k + 1; i = v; and go to step #3

End

Here's an example:

Example 2: Using Gauss-Jordan Elimination

(1) We start with a system of linear equations:

x₁ - 2x₂ + 4x₃ = 12

2x₁ - x₂ + 5x₃ = 18

-x₁ + 3x₂ - 3x₃ = -8

(2) We represent them in augmented matrix form:



(3) We use elementary row operations to put this matrix into reduced echelon form (I will use R1, R2, R3 for Row 1, Row 2, and Row 3):

(a) Let R2 = R2 + (-2)R1 [Operation #3]



(b) Let R3 = R3 + R1 [Operation #3]



(c) Let R2 = (1/3)R2 [Operation #2]



(d) Let R1 = R1 + 2*R2 [Operation #3]



(e) Let R3 = R3 + (-1)*R2 [Operation #3]



(f) Let R3 = (1/2)R3 [Operation #2]



(g) Let R1 = R1 + (-2)*R3 [Operation #3]



(h) Let R2 = R2 + R3 [Operation #3]



(4) We now write down the system of linear equations corresponding to the reduced echelon form:

x₁ = 2

x₂ = 1

x₃ = 3

Of course, we need to be sure that we can always get to reduced echelon form. Here is the theorem that guarantees this:

Theorem 1: Every matrix is row equivalent to a reduced echelon form matrix

Proof:

(1) The Gauss-Jordan Elimination Algorithm works for any 1 x n matrix.

(a) Let A = 1 x n matrix

(b) Assume that A is not all zeros (if it were, then A is already in reduced echelon form)

(c) Let a_1,i be the first nonzero element in A.

(d) Let A = (1/a_1,i)*A

(f) A now has a leading 1 and since this is a one-row matrix, A is now in reduced echelon form.

(2) Assume that the Gauss-Jordan Elimination Algorithm works for any matrix up to k rows.

(3) We can now show that it will work for a matrix with k+1 rows.

(a) Let A = a nonzero matrix with k+1 rows [We can assume it is nonzero since if it were zero, it would already be in reduced echelon form]

(b) Assume that we've run the Gauss-Jordan Elimination Algorithm up to the kth row so that if we define B such that:



(c) We can see that B is in reduced echelon form since

(i) B has k rows

(ii) We can assume by our assumption in step #2 that the algorithm works for any matrix of k rows or less

(iii) The algorithm leaves B unchanged if we run it again.

(d) We can also see that A_k+1 consists of a single row which is zero for every column where there is a leading 1 in B. [Since these are zero'd out by the algorithm above]

(e) If there is a nonzero column in A_k+1, it must therefore be to the right of all the leading 1s in B.

(f) Assume that there is a nonzero column in A_k+1 [If there were not, we would be done, since then A_k+1 would consist of all zero's and A would then be in reduced echelon form]

(g) In this case, none of the rows in B are all zeros. [In order for A_k+1 to be nonzero, each of the previous rows must have had at least one nonzero column. If one was all zeros, it would have been exchanged with A_k+1 and then A_k+1 would be all zeros which it is not]

(h) Let a_k+1,x = the first nonzero element in A_k+1

(i) Let A_k+1 = (1/a_k+1,x)A_k+1

(j) For all rows i, 1 thru k, let R_i = R_i + (-a_i,x)*R_k+1.

(k) Clearly, this will zero out each of the remaining rows.

(l) A is now in reduced echelon form since:

(a) Any rows consisting entirely of zeros are grouped at the bottom of the matrix. [Note: there are none]

(b) The first nonzero element of any row is 1. [We assumed this was true of all rows in B and now we have shown it is also true of R_k+1]

(c) The leading 1 of each row after the first is positioned to the right of the leading 1 of the previous row. [From step #3e]

(d) If a column contains a leading 1, then all other elements in that column are 0. [From step #3j]

QED

References

• Gareth Williams, Linear Algebra with Applications, Wm. C. Brown Publishers, 1996.
• "Row Reduction", PlanetMath.org
• Hans Schneider, George Philip Barker, Matrices and Linear Algebra, 1989.