Solve System of Linear Equations Using Cramer's Rule

#119 · Linear Algebra · Medium

Problem

Solve a system of linear equations using Cramer's Rule. Given a system Ax = b where A is a square matrix, find each unknown by replacing columns of A with b and computing determinant ratios.

Solution

def determinant(matrix: list[list[float]]) -> float:
    n = len(matrix)
    if n == 1:
        return matrix[0][0]
    if n == 2:
        return matrix[0][0] * matrix[1][1] - matrix[0][1] * matrix[1][0]

    det = 0
    for j in range(n):
        minor = [row[:j] + row[j+1:] for row in matrix[1:]]
        det += ((-1) ** j) * matrix[0][j] * determinant(minor)
    return det

def cramers_rule(A: list[list[float]], b: list[float]) -> list[float]:
    n = len(A)
    det_A = determinant(A)

    if abs(det_A) < 1e-10:
        return []  # No unique solution

    solution = []
    for i in range(n):
        # Replace column i of A with b
        A_i = [row[:] for row in A]
        for row_idx in range(n):
            A_i[row_idx][i] = b[row_idx]

        x_i = determinant(A_i) / det_A
        solution.append(round(x_i, 4))

    return solution

Explanation

Cramer's Rule: For system Ax = b, each variable x_i = det(A_i) / det(A), where A_i is matrix A with its i-th column replaced by vector b.
Determinant: Computed recursively via cofactor expansion along the first row. For 2x2 matrices, use the direct formula ad - bc.
No solution check: If det(A) = 0, the system has no unique solution (either no solution or infinitely many).
Cramer's Rule is elegant but impractical for large systems due to the cost of computing determinants.

Complexity

Time: O(n! * n) for the naive determinant computation, or O(n^3) with LU decomposition
Space: O(n^2) for creating modified matrices

← #118 #120 →