Linear Algebra - (Gaussian|Common) Elimination

Origin

Method illustrated in Chapter Eight of a Chinese text, The Nine Chapters on the Mathematical Art, that was written roughly two thousand years ago. Rediscovered in Europe by Isaac Newton (England) and Michel Rolle (France). Gauss called the method eliminiationem vulgarem (“common elimination”). Gauss adapted the method for another problem and developed notation.

Use case

Solving a matrix equation (ie a linear systems
Finding a basis for the null space of a matrix (ie vectors in null space) - used in e.g. integer factoring

basis

Finding a basis for the span of given vectors (and then for rank and therefore for testing linear dependence.

To find a basis for the row space of a matrix A, iteratively transform A into a matrix B

in echelon form
with no zero rows
whose row space is the same as that of A.

Key idea: keep track of transformations performed in putting matrix in echelon form.

Computation

sort the rows according to position of leftmost nonzero entry (first choose a row with a nonzero in first column, then choose a row with a nonzero in second column, …)

# To handle Vecs with arbitrary D, we must order the domain (here by hash)
col_label_list = sorted(matrixRowList[0].D, key=hash)
for c in col_label_list:
    rows_with_nonzero = [r for r in rows_left if rowlist[r][c] != 0]
    # if we don't have a vector with a nonzero on this position, pass
    if rows with nonzero != []:
        # each row is only used once as a pivot-row,
        pivot = rows_with_nonzero[0]
        
        # If we have more than one vector with a non-zero on this position
        # then (addition|substract) them in order to push the zero at the right side
        if len(rows_with_nonzero) > 1:
            # over R: add suitable multiple of rowlist[pivot] to each row in rows with nonzero[1:]
            # over Gf2: add row pivot to the others
            pivot = rows_with_nonzero[0]
            for r in rows_with_nonzero[1:]:
                multiplier = rowlist[r][c]/rowlist[pivot][c]
                rowlist[r] -= multiplier * rowlist[pivot]
            
        
        # Append the pivot in the list in echelon form
        new_rowlist.append(rowlist[pivot])
        # Remove the pivot row from the origin list
        rows_left.remove(pivot)

round-off error

As the computation use floating-point numbers, the Gaussian elimination method got the wrong answer due to round-off error.

These problems can be mitigated by choosing the pivot element carefully:

Partial pivoting: Among rows with non-zero entries in column c, choose row with entry having largest absolute value.
Complete pivoting: Instead of selecting order of columns beforehand, in each iteration choose column to maximize absolute value of pivot element.