Problem 25: Invert a matrix

def invert(matrix: list[list[float]]) -> list[list[float]]: """ Return the inverse of a square matrix using Gaussian elimination with partial pivoting. The input matrix is not modified. """ n = len(matrix) if any(len(row) != n for row in matrix): raise ValueError("Only square matrices can be inverted") # Build the augmented matrix [A | I] aug: list[list[float]] = [ row[:] + [float(i == j) for j in range(n)] for i, row in enumerate(matrix) ] for col in range(n): # ---- Partial pivoting ---- # Find the row with the largest absolute value in the current column pivot_row = max(range(col, n), key=lambda r: abs(aug[r][col])) if abs(aug[pivot_row][col]) < 1e-15: raise ValueError("Matrix is singular or near‑singular") # Swap the current row with the pivot row (if needed) if pivot_row != col: aug[col], aug[pivot_row] = aug[pivot_row], aug[col] # ---- Normalize pivot row ---- pivot_val = aug[col][col] inv_pivot = 1.0 / pivot_val aug[col] = [x * inv_pivot for x in aug[col]] # ---- Eliminate other rows ---- for r in range(n): if r == col: continue factor = aug[r][col] if factor == 0.0: continue aug[r] = [ aug[r][c] - factor * aug[col][c] for c in range(2 * n) ] # Extract the right half of the augmented matrix – this is the inverse inverse = [row[n:] for row in aug] return inverse