Matrix Determinant & Trace

#195 · Linear Algebra · Easy

Problem

Given a square matrix, compute its determinant and trace. Implement both operations from scratch without using built-in linear algebra functions.

Solution

def matrix_trace(matrix: list[list[float]]) -> float:
    n = len(matrix)
    return sum(matrix[i][i] for i in range(n))

def matrix_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.0
    for col in range(n):
        # Build minor matrix
        minor = []
        for i in range(1, n):
            row = []
            for j in range(n):
                if j != col:
                    row.append(matrix[i][j])
            minor.append(row)
        cofactor = ((-1) ** col) * matrix[0][col] * matrix_determinant(minor)
        det += cofactor
    return det

def det_and_trace(matrix: list[list[float]]) -> tuple:
    return matrix_determinant(matrix), matrix_trace(matrix)

Explanation

Trace: Sum of diagonal elements matrix[i][i] for i = 0..n-1.
Determinant: Use cofactor expansion along the first row.
For each element in the first row, compute the minor (submatrix with that row and column removed) and recursively compute its determinant.
Base cases: 1x1 matrix returns the single element; 2x2 uses ad - bc.
The cofactor alternates sign: (-1)^col * element * det(minor).

Complexity

Time: O(n!) for the determinant via cofactor expansion; O(n) for the trace
Space: O(n^2) for minor matrices in the recursion stack

← #194 #196 →