Gauss and Gauss-Jordan elimination¶
Author: Parin Chaipunya affil: KMUTT
The aim of this notebook is to write a function that reduces a given matrix into its RREF matrix using Gaussian elimination. We first write the Gauss elimination to get into the vibe, then extend it to Gauss-Jordan elimination towards the end.
Gauss elimination¶
In [1]:
import numpy as np
In [2]:
def REF(A):
m, n = A.shape
A = A.astype(float)
print(f"Input matrix \nA = \n{A}\n\n")
I = 0
for j in range(n):
print(f"-----CONSIDER COL {j}-----\n")
for i in range(m):
if i >= I and A[i,j] != 0:
print(f"CONSIDER ROW {I}\nSWAP rows {i} and {I}:")
A[[I,i]] = A[[i,I]]
print(f"A = \n{A}")
A[I,:] /= A[I,j]
A[I+1:,:] -= A[I+1:,[j]] * A[I,:]
print(f"PIVOT at ({I},{j}): \nA = \n{A}\n\nROW {I} DONE.")
I += 1
break
print(f"COL {j} DONE.\n")
print("-----ALL COLs DONE-----\n")
print(f"REF(A) = \n{A}")
return A
Example¶
We then test our REF function with the following matrices.
In [3]:
A = np.array([[2, 0, 0, 1], [2, 1, 0, -1], [0, 0, 0, 1.]])
A
Out[3]:
array([[ 2., 0., 0., 1.],
[ 2., 1., 0., -1.],
[ 0., 0., 0., 1.]])
In [4]:
A_ref = REF(A)
Input matrix A = [[ 2. 0. 0. 1.] [ 2. 1. 0. -1.] [ 0. 0. 0. 1.]] -----CONSIDER COL 0----- CONSIDER ROW 0 SWAP rows 0 and 0: A = [[ 2. 0. 0. 1.] [ 2. 1. 0. -1.] [ 0. 0. 0. 1.]] PIVOT at (0,0): A = [[ 1. 0. 0. 0.5] [ 0. 1. 0. -2. ] [ 0. 0. 0. 1. ]] ROW 0 DONE. COL 0 DONE. -----CONSIDER COL 1----- CONSIDER ROW 1 SWAP rows 1 and 1: A = [[ 1. 0. 0. 0.5] [ 0. 1. 0. -2. ] [ 0. 0. 0. 1. ]] PIVOT at (1,1): A = [[ 1. 0. 0. 0.5] [ 0. 1. 0. -2. ] [ 0. 0. 0. 1. ]] ROW 1 DONE. COL 1 DONE. -----CONSIDER COL 2----- COL 2 DONE. -----CONSIDER COL 3----- CONSIDER ROW 2 SWAP rows 2 and 2: A = [[ 1. 0. 0. 0.5] [ 0. 1. 0. -2. ] [ 0. 0. 0. 1. ]] PIVOT at (2,3): A = [[ 1. 0. 0. 0.5] [ 0. 1. 0. -2. ] [ 0. 0. 0. 1. ]] ROW 2 DONE. COL 3 DONE. -----ALL COLs DONE----- REF(A) = [[ 1. 0. 0. 0.5] [ 0. 1. 0. -2. ] [ 0. 0. 0. 1. ]]
In [5]:
B = np.array([
[3, 9, 0, 15, 3],
[1, 3, 0, 5, 1],
[-10, 0, 0, 2, -1],
[0, 0, 0, 0, 0],
[1, 0, 1, 1, 4]
])
B
Out[5]:
array([[ 3, 9, 0, 15, 3],
[ 1, 3, 0, 5, 1],
[-10, 0, 0, 2, -1],
[ 0, 0, 0, 0, 0],
[ 1, 0, 1, 1, 4]])
In [6]:
B_ref = REF(B)
Input matrix A = [[ 3. 9. 0. 15. 3.] [ 1. 3. 0. 5. 1.] [-10. 0. 0. 2. -1.] [ 0. 0. 0. 0. 0.] [ 1. 0. 1. 1. 4.]] -----CONSIDER COL 0----- CONSIDER ROW 0 SWAP rows 0 and 0: A = [[ 3. 9. 0. 15. 3.] [ 1. 3. 0. 5. 1.] [-10. 0. 0. 2. -1.] [ 0. 0. 0. 0. 0.] [ 1. 0. 1. 1. 4.]] PIVOT at (0,0): A = [[ 1. 3. 0. 5. 1.] [ 0. 0. 0. 0. 0.] [ 0. 30. 0. 52. 9.] [ 0. 0. 0. 0. 0.] [ 0. -3. 1. -4. 3.]] ROW 0 DONE. COL 0 DONE. -----CONSIDER COL 1----- CONSIDER ROW 1 SWAP rows 2 and 1: A = [[ 1. 3. 0. 5. 1.] [ 0. 30. 0. 52. 9.] [ 0. 0. 0. 0. 0.] [ 0. 0. 0. 0. 0.] [ 0. -3. 1. -4. 3.]] PIVOT at (1,1): A = [[1. 3. 0. 5. 1. ] [0. 1. 0. 1.73333333 0.3 ] [0. 0. 0. 0. 0. ] [0. 0. 0. 0. 0. ] [0. 0. 1. 1.2 3.9 ]] ROW 1 DONE. COL 1 DONE. -----CONSIDER COL 2----- CONSIDER ROW 2 SWAP rows 4 and 2: A = [[1. 3. 0. 5. 1. ] [0. 1. 0. 1.73333333 0.3 ] [0. 0. 1. 1.2 3.9 ] [0. 0. 0. 0. 0. ] [0. 0. 0. 0. 0. ]] PIVOT at (2,2): A = [[1. 3. 0. 5. 1. ] [0. 1. 0. 1.73333333 0.3 ] [0. 0. 1. 1.2 3.9 ] [0. 0. 0. 0. 0. ] [0. 0. 0. 0. 0. ]] ROW 2 DONE. COL 2 DONE. -----CONSIDER COL 3----- COL 3 DONE. -----CONSIDER COL 4----- COL 4 DONE. -----ALL COLs DONE----- REF(A) = [[1. 3. 0. 5. 1. ] [0. 1. 0. 1.73333333 0.3 ] [0. 0. 1. 1.2 3.9 ] [0. 0. 0. 0. 0. ] [0. 0. 0. 0. 0. ]]
In [7]:
C = np.array([
[0, 0, 0, 0, 0, 0],
[0, 0, 1, 0, 1, 4],
[1, 1, 2, 0, 2, -5],
[1, 0, 1, 3, 3, 1],
[2, 1, 3, 3, 5, -4]
])
In [8]:
C_ref = REF(C)
Input matrix A = [[ 0. 0. 0. 0. 0. 0.] [ 0. 0. 1. 0. 1. 4.] [ 1. 1. 2. 0. 2. -5.] [ 1. 0. 1. 3. 3. 1.] [ 2. 1. 3. 3. 5. -4.]] -----CONSIDER COL 0----- CONSIDER ROW 0 SWAP rows 2 and 0: A = [[ 1. 1. 2. 0. 2. -5.] [ 0. 0. 1. 0. 1. 4.] [ 0. 0. 0. 0. 0. 0.] [ 1. 0. 1. 3. 3. 1.] [ 2. 1. 3. 3. 5. -4.]] PIVOT at (0,0): A = [[ 1. 1. 2. 0. 2. -5.] [ 0. 0. 1. 0. 1. 4.] [ 0. 0. 0. 0. 0. 0.] [ 0. -1. -1. 3. 1. 6.] [ 0. -1. -1. 3. 1. 6.]] ROW 0 DONE. COL 0 DONE. -----CONSIDER COL 1----- CONSIDER ROW 1 SWAP rows 3 and 1: A = [[ 1. 1. 2. 0. 2. -5.] [ 0. -1. -1. 3. 1. 6.] [ 0. 0. 0. 0. 0. 0.] [ 0. 0. 1. 0. 1. 4.] [ 0. -1. -1. 3. 1. 6.]] PIVOT at (1,1): A = [[ 1. 1. 2. 0. 2. -5.] [-0. 1. 1. -3. -1. -6.] [ 0. 0. 0. 0. 0. 0.] [ 0. 0. 1. 0. 1. 4.] [ 0. 0. 0. 0. 0. 0.]] ROW 1 DONE. COL 1 DONE. -----CONSIDER COL 2----- CONSIDER ROW 2 SWAP rows 3 and 2: A = [[ 1. 1. 2. 0. 2. -5.] [-0. 1. 1. -3. -1. -6.] [ 0. 0. 1. 0. 1. 4.] [ 0. 0. 0. 0. 0. 0.] [ 0. 0. 0. 0. 0. 0.]] PIVOT at (2,2): A = [[ 1. 1. 2. 0. 2. -5.] [-0. 1. 1. -3. -1. -6.] [ 0. 0. 1. 0. 1. 4.] [ 0. 0. 0. 0. 0. 0.] [ 0. 0. 0. 0. 0. 0.]] ROW 2 DONE. COL 2 DONE. -----CONSIDER COL 3----- COL 3 DONE. -----CONSIDER COL 4----- COL 4 DONE. -----CONSIDER COL 5----- COL 5 DONE. -----ALL COLs DONE----- REF(A) = [[ 1. 1. 2. 0. 2. -5.] [-0. 1. 1. -3. -1. -6.] [ 0. 0. 1. 0. 1. 4.] [ 0. 0. 0. 0. 0. 0.] [ 0. 0. 0. 0. 0. 0.]]
Gauss-Jordan elimination¶
With only one line added to the REF function above, we achieve the Gauss-Jordan elimination as in the RREF function presented below.
In [9]:
def RREF(A):
m, n = A.shape
A = A.astype(float)
print(f"Input matrix \nA = \n{A}\n\n")
I = 0
for j in range(n):
print(f"-----CONSIDER COL {j}-----\n")
for i in range(m):
if i >= I and A[i,j] != 0:
print(f"CONSIDER ROW {I}\nSWAP rows {i} and {I}:")
A[[I,i]] = A[[i,I]]
print(f"A = \n{A}")
A[I,:] /= A[I,j]
A[I+1:,:] -= A[I+1:,[j]] * A[I,:]
A[:I,:] -= A[:I,[j]] * A[I,:] # This line is added from the code in 5.1.
print(f"PIVOT at ({I},{j}): \nA = \n{A}\n\nROW {I} DONE.")
I += 1
break
print(f"COL {j} DONE.\n")
print("-----ALL COLs DONE-----\n")
print(f"RREF(A) = \n{A}")
return A
Example¶
We next test the RREF function witht the following matrices.
In [10]:
A = np.array([[2, 0, 0, 1], [2, 1, 0, -1], [0, 0, 0, 1.]])
A
Out[10]:
array([[ 2., 0., 0., 1.],
[ 2., 1., 0., -1.],
[ 0., 0., 0., 1.]])
In [11]:
A_rref = RREF(A)
Input matrix A = [[ 2. 0. 0. 1.] [ 2. 1. 0. -1.] [ 0. 0. 0. 1.]] -----CONSIDER COL 0----- CONSIDER ROW 0 SWAP rows 0 and 0: A = [[ 2. 0. 0. 1.] [ 2. 1. 0. -1.] [ 0. 0. 0. 1.]] PIVOT at (0,0): A = [[ 1. 0. 0. 0.5] [ 0. 1. 0. -2. ] [ 0. 0. 0. 1. ]] ROW 0 DONE. COL 0 DONE. -----CONSIDER COL 1----- CONSIDER ROW 1 SWAP rows 1 and 1: A = [[ 1. 0. 0. 0.5] [ 0. 1. 0. -2. ] [ 0. 0. 0. 1. ]] PIVOT at (1,1): A = [[ 1. 0. 0. 0.5] [ 0. 1. 0. -2. ] [ 0. 0. 0. 1. ]] ROW 1 DONE. COL 1 DONE. -----CONSIDER COL 2----- COL 2 DONE. -----CONSIDER COL 3----- CONSIDER ROW 2 SWAP rows 2 and 2: A = [[ 1. 0. 0. 0.5] [ 0. 1. 0. -2. ] [ 0. 0. 0. 1. ]] PIVOT at (2,3): A = [[1. 0. 0. 0.] [0. 1. 0. 0.] [0. 0. 0. 1.]] ROW 2 DONE. COL 3 DONE. -----ALL COLs DONE----- RREF(A) = [[1. 0. 0. 0.] [0. 1. 0. 0.] [0. 0. 0. 1.]]
In [12]:
B = np.array([
[3, 9, 0, 15, 3],
[1, 3, 0, 5, 1],
[-10, 0, 0, 2, -1],
[0, 0, 0, 0, 0],
[1, 0, 1, 1, 4]
])
B_rref = RREF(B)
Input matrix A = [[ 3. 9. 0. 15. 3.] [ 1. 3. 0. 5. 1.] [-10. 0. 0. 2. -1.] [ 0. 0. 0. 0. 0.] [ 1. 0. 1. 1. 4.]] -----CONSIDER COL 0----- CONSIDER ROW 0 SWAP rows 0 and 0: A = [[ 3. 9. 0. 15. 3.] [ 1. 3. 0. 5. 1.] [-10. 0. 0. 2. -1.] [ 0. 0. 0. 0. 0.] [ 1. 0. 1. 1. 4.]] PIVOT at (0,0): A = [[ 1. 3. 0. 5. 1.] [ 0. 0. 0. 0. 0.] [ 0. 30. 0. 52. 9.] [ 0. 0. 0. 0. 0.] [ 0. -3. 1. -4. 3.]] ROW 0 DONE. COL 0 DONE. -----CONSIDER COL 1----- CONSIDER ROW 1 SWAP rows 2 and 1: A = [[ 1. 3. 0. 5. 1.] [ 0. 30. 0. 52. 9.] [ 0. 0. 0. 0. 0.] [ 0. 0. 0. 0. 0.] [ 0. -3. 1. -4. 3.]] PIVOT at (1,1): A = [[ 1. 0. 0. -0.2 0.1 ] [ 0. 1. 0. 1.73333333 0.3 ] [ 0. 0. 0. 0. 0. ] [ 0. 0. 0. 0. 0. ] [ 0. 0. 1. 1.2 3.9 ]] ROW 1 DONE. COL 1 DONE. -----CONSIDER COL 2----- CONSIDER ROW 2 SWAP rows 4 and 2: A = [[ 1. 0. 0. -0.2 0.1 ] [ 0. 1. 0. 1.73333333 0.3 ] [ 0. 0. 1. 1.2 3.9 ] [ 0. 0. 0. 0. 0. ] [ 0. 0. 0. 0. 0. ]] PIVOT at (2,2): A = [[ 1. 0. 0. -0.2 0.1 ] [ 0. 1. 0. 1.73333333 0.3 ] [ 0. 0. 1. 1.2 3.9 ] [ 0. 0. 0. 0. 0. ] [ 0. 0. 0. 0. 0. ]] ROW 2 DONE. COL 2 DONE. -----CONSIDER COL 3----- COL 3 DONE. -----CONSIDER COL 4----- COL 4 DONE. -----ALL COLs DONE----- RREF(A) = [[ 1. 0. 0. -0.2 0.1 ] [ 0. 1. 0. 1.73333333 0.3 ] [ 0. 0. 1. 1.2 3.9 ] [ 0. 0. 0. 0. 0. ] [ 0. 0. 0. 0. 0. ]]
In [13]:
C = np.array([
[0, 0, 0, 0, 0, 0],
[0, 0, 1, 0, 1, 4],
[1, 1, 2, 0, 2, -5],
[1, 0, 1, 3, 3, 1],
[2, 1, 3, 3, 5, -4]
])
C_rref = RREF(C)
Input matrix A = [[ 0. 0. 0. 0. 0. 0.] [ 0. 0. 1. 0. 1. 4.] [ 1. 1. 2. 0. 2. -5.] [ 1. 0. 1. 3. 3. 1.] [ 2. 1. 3. 3. 5. -4.]] -----CONSIDER COL 0----- CONSIDER ROW 0 SWAP rows 2 and 0: A = [[ 1. 1. 2. 0. 2. -5.] [ 0. 0. 1. 0. 1. 4.] [ 0. 0. 0. 0. 0. 0.] [ 1. 0. 1. 3. 3. 1.] [ 2. 1. 3. 3. 5. -4.]] PIVOT at (0,0): A = [[ 1. 1. 2. 0. 2. -5.] [ 0. 0. 1. 0. 1. 4.] [ 0. 0. 0. 0. 0. 0.] [ 0. -1. -1. 3. 1. 6.] [ 0. -1. -1. 3. 1. 6.]] ROW 0 DONE. COL 0 DONE. -----CONSIDER COL 1----- CONSIDER ROW 1 SWAP rows 3 and 1: A = [[ 1. 1. 2. 0. 2. -5.] [ 0. -1. -1. 3. 1. 6.] [ 0. 0. 0. 0. 0. 0.] [ 0. 0. 1. 0. 1. 4.] [ 0. -1. -1. 3. 1. 6.]] PIVOT at (1,1): A = [[ 1. 0. 1. 3. 3. 1.] [-0. 1. 1. -3. -1. -6.] [ 0. 0. 0. 0. 0. 0.] [ 0. 0. 1. 0. 1. 4.] [ 0. 0. 0. 0. 0. 0.]] ROW 1 DONE. COL 1 DONE. -----CONSIDER COL 2----- CONSIDER ROW 2 SWAP rows 3 and 2: A = [[ 1. 0. 1. 3. 3. 1.] [-0. 1. 1. -3. -1. -6.] [ 0. 0. 1. 0. 1. 4.] [ 0. 0. 0. 0. 0. 0.] [ 0. 0. 0. 0. 0. 0.]] PIVOT at (2,2): A = [[ 1. 0. 0. 3. 2. -3.] [ -0. 1. 0. -3. -2. -10.] [ 0. 0. 1. 0. 1. 4.] [ 0. 0. 0. 0. 0. 0.] [ 0. 0. 0. 0. 0. 0.]] ROW 2 DONE. COL 2 DONE. -----CONSIDER COL 3----- COL 3 DONE. -----CONSIDER COL 4----- COL 4 DONE. -----CONSIDER COL 5----- COL 5 DONE. -----ALL COLs DONE----- RREF(A) = [[ 1. 0. 0. 3. 2. -3.] [ -0. 1. 0. -3. -2. -10.] [ 0. 0. 1. 0. 1. 4.] [ 0. 0. 0. 0. 0. 0.] [ 0. 0. 0. 0. 0. 0.]]