Implement Reduced Row Echelon Form (RREF) Function

#48 · Linear Algebra · Medium

Problem

Implement the Reduced Row Echelon Form (RREF) of a matrix. Transform a given matrix into RREF using Gaussian elimination with partial pivoting and back-substitution.

Solution

import numpy as np

def rref(matrix):
    mat = np.array(matrix, dtype=np.float64)
    rows, cols = mat.shape
    pivot_row = 0

    for col in range(cols):
        if pivot_row >= rows:
            break

        # Find pivot
        max_row = pivot_row
        for r in range(pivot_row + 1, rows):
            if abs(mat[r, col]) > abs(mat[max_row, col]):
                max_row = r

        if abs(mat[max_row, col]) < 1e-12:
            continue

        # Swap rows
        mat[[pivot_row, max_row]] = mat[[max_row, pivot_row]]

        # Scale pivot row
        mat[pivot_row] = mat[pivot_row] / mat[pivot_row, col]

        # Eliminate all other rows
        for r in range(rows):
            if r != pivot_row and abs(mat[r, col]) > 1e-12:
                mat[r] -= mat[r, col] * mat[pivot_row]

        pivot_row += 1

    return mat.tolist()

Explanation

Iterate through columns, finding the best pivot (largest absolute value) in the current column below the current pivot row.
Swap the pivot row into position.
Scale the pivot row so the leading entry becomes 1.
Eliminate all other entries in that column by subtracting the appropriate multiple of the pivot row.
The result is a matrix in reduced row echelon form where each leading entry is 1 and is the only nonzero entry in its column.

Complexity

Time: O(m n min(m, n)) where m is rows and n is columns
Space: O(m * n) for the matrix copy

← #47 #49 →