Gauss-Jordan Elimination in python

Question

I am working on code to do Gauss-Jordan elimination in python. My directions are as follows:

def gauss_jordan(A):
for each row k do
   i* <- argmax_{k<i<n} |A_{ik}|
   if A_{i*k} = 0 then
     Matrix is not invertible
   end if
   Swap rows k and i*
   for each row j below k (i.e. j = k + 1,...,n) do
     f = A_{jk}/A_{kk}
     Aj = Aj - fA_{k}
   end for
end for
for each row k = n,..., 1 (i.e. in reverse) do
   A_{k} = A_{k}=A_{kk}
   for each row j above k (i.e. j = k -1,..., 1) do
     f = A_{jk}/A_{kk}  
     Aj = A_{j}-fA_{k}
   end for
end for

So far I have:

def gauss_jordan(A):
(h, w) = (len(A), len(A[0]))
for y in range(0,h):          
    for pivot in range(y, h):   
        if A[pivot][y].value % 2 != 0: 
            break 
    else: 
        return None

Is this the correct start? I feel quite lost in where to go next. The input will be a Numpy array. Any thoughts are much appreciated!

Answer 1

The very first thing you should do is create the augmented matrix. Block wise it would look like [A, identity(A.shape[0])] and then follow the algorithm through to solve. Your final answer will be the right half of the matrix. I believe your for loop is correct but the check is incorrect. You need to find the maximum in k's column. So when k is 1, you will go through the first column and find the maximum in absolute value in that column and return its index.

max_v=-10
index_m=-10
for t in range(k, A.shape[0]):
    if abs(A[t, k]) > max_v:
        max_v = abs(A[t, k])
        index_m = t

Note that k is my outermost loop that is going through all the rows of augmented A matrix. Hope this helped.