Gauss Method

Gauss Method#

Matrix Row Operations#

In linear algebra, matrix row operations are fundamental techniques used to manipulate matrices into simpler forms, such as reduced row echelon form (RREF). These operations are essential for solving systems of linear equations, determining matrix rank, and finding inverse matrices.

Let’s start by defining our matrix and vector.

A = matrix(QQ, 3, [1,2,-1,0,1,3,2,-1,1])
show(A)

\(\displaystyle \left(\begin{array}{rrr} 1 & 2 & -1 \\ 0 & 1 & 3 \\ 2 & -1 & 1 \end{array}\right)\)

b = vector(QQ, [4,7,1])
show(b)

\(\displaystyle \left(4,\,7,\,1\right)\)

Let’s check this matrix has a solution:

solution = A.solve_right(b)
show(solution)

\(\displaystyle \left(\frac{8}{9},\,\frac{7}{3},\,\frac{14}{9}\right)\)

Documentation:

Augmented Matrices#

We can create an augmented matrix by adding the constants vector (\(b\)) to the matrix of coefficients (\(A\))

A_aug = A.augment(b, subdivide=True)
show(A_aug)

\(\displaystyle \left(\begin{array}{rrr|r} 1 & 2 & -1 & 4 \\ 0 & 1 & 3 & 7 \\ 2 & -1 & 1 & 1 \end{array}\right)\)

Documentation for sage.matrix.matrix1.Matrix.augment

Reduced row echelon form (rref)#

We show the method to retrieve the rref before showing row operations to manually obtain the rref.

rref = A_aug.rref()
show(rref)

\(\displaystyle \left(\begin{array}{rrr|r} 1 & 0 & 0 & \frac{8}{9} \\ 0 & 1 & 0 & \frac{7}{3} \\ 0 & 0 & 1 & \frac{14}{9} \end{array}\right)\)

Documentation for sage.matrix.matrix2.Matrix.rref

Row operations#

The three basic row operations are:

Swap Rows
Rescale Rows
Add Multiple of Row

Let’s start with the augmented matrix:

show(A_aug)

\(\displaystyle \left(\begin{array}{rrr|r} 1 & 2 & -1 & 4 \\ 0 & 1 & 3 & 7 \\ 2 & -1 & 1 & 1 \end{array}\right)\)

# Row 3  <- Row 3 - 2*Row 1
A_aug.add_multiple_of_row(2, 0, -2)
show(A_aug)

\(\displaystyle \left(\begin{array}{rrr|r} 1 & 2 & -1 & 4 \\ 0 & 1 & 3 & 7 \\ 0 & -5 & 3 & -7 \end{array}\right)\)

# Row 3 <-> Row 2
A_aug.swap_rows(1, 2)
show(A_aug)

\(\displaystyle \left(\begin{array}{rrr|r} 1 & 2 & -1 & 4 \\ 0 & -5 & 3 & -7 \\ 0 & 1 & 3 & 7 \end{array}\right)\)

# Row 3 <- -5*Row 3
A_aug.rescale_row(2, -5)
show(A_aug)

\(\displaystyle \left(\begin{array}{rrr|r} 1 & 2 & -1 & 4 \\ 0 & -5 & 3 & -7 \\ 0 & -5 & -15 & -35 \end{array}\right)\)

… and so on

See if you can complete the operations to achieve reduce row echelon form (rref).

Each of these operations modify (mutate) the original matrix. There are equivalent operations that leave the original matrix unchanged and return a new matrix. These operations have similar names, but have the prefix with_, e.g.

swap_rows() -> with_swapped_rows()
rescale_row() -> with_rescaled_row()
add_multiple_of_row() -> with_added_multiple_of_row()

Documentation: matrix0.

Gauss’s method step-by-step automation#

The following code automates the gauss method outputting each step.

Adapted from: gaus_method.sage

# Show Gauss's method and Gauss-Jordan reduction steps. 
# 2012-Apr-20  Jim Hefferon  Public Domain. 
# 2019-Nov-09 JH  Minor reformatting
# 2021-Sep-22 JH  Adjust for Python3

# Naive Gaussian reduction
def gauss_method(M,rescale_leading_entry=False):
    """Describe the reduction to echelon form of the given matrix of 
    rationals.
      M  matrix of rationals   e.g., M = matrix(QQ, [[..], [..], ..])
      rescale_leading_entry=False  boolean  make leading entries to 1's
    Returns: None.  Side effects: M is reduced, steps are printed.  
    Note that this is echelon form, not reduced echelon form, and that 
    this routine does not end the same way as does M.echelon_form().
    """
    num_rows=M.nrows()
    num_cols=M.ncols()

    print("Original matrix\n")
    show(M)    

    col = 0   # all cols before this are already done
    for row in range(0,num_rows): 
        # Do we need to swap in a nonzero entry from below?
        while (col < num_cols
               and M[row][col] == 0): 
            for i in M.nonzero_positions_in_column(col):
                if i > row:
                    print("\nswap row", row+1, "with row", i+1, "\n")
                    M.swap_rows(row,i)
                    show(M)
                    break     
            else:
                col += 1

        if col >= num_cols:
            break
       
        # Now we are guaranteed M[row][col] != 0
        if (rescale_leading_entry
           and M[row][col] != 1):
            print("\ntake", 1/M[row][col], "times row", row+1, "\n")
            M.rescale_row(row,1/M[row][col])
            show(M)
        change_flag=False
        for changed_row in range(row+1,num_rows):
            if M[changed_row][col] != 0:
                change_flag=True
                factor=-1*M[changed_row][col]/M[row][col]
                print("\ntake", factor, "times row", row+1, "plus row", changed_row+1, "\n")
                M.add_multiple_of_row(changed_row,row,factor)
        if change_flag:
            show(M)
        col +=1

A = matrix(QQ, 3, [1,2,-1,0,1,3,2,-1,1])

gauss_method(A)

Original matrix