行列式

What · 是什么

行列式是方阵的一种标量运算，记det(A)或|A|。三种等价定义：全排列定义（n!项代数和）、归纳定义（按行/列展开递归）、公理化定义（满足倍乘、对换、倍加性质+单位阵行列式为1）。高斯消元法将矩阵化为上三角矩阵，行列式=对角线元素乘积（考虑行交换的符号变化）。竞赛中常需模质数求行列式（如矩阵树定理求生成树计数）。

Why · 为什么

How · 实现

伪代码

det = 1
for col in 0..n-1:
  find pivot row with A[row][col]!=0
  if none: return 0
  swap rows if needed, flip det sign
  for row in col+1..n-1:
    eliminate A[row][col] using row operations
for i: det *= A[i][i]
return det

Python 实现

def determinant(mat, mod=None):
    """Compute determinant via Gaussian elimination. O(n^3)."""
    n = len(mat)
    A = [row[:] for row in mat]
    det = 1
    for col in range(n):
        pivot = -1
        for row in range(col, n):
            if A[row][col] != 0:
                pivot = row
                break
        if pivot == -1:
            return 0
        if pivot != col:
            A[col], A[pivot] = A[pivot], A[col]
            det = -det
        for row in range(col + 1, n):
            if A[row][col] != 0:
                if mod:
                    ratio = A[row][col] * pow(A[col][col], mod - 2, mod) % mod
                    for j in range(col, n):
                        A[row][j] = (A[row][j] - ratio * A[col][j]) % mod
                else:
                    factor = A[row][col] / A[col][col]
                    for j in range(col, n):
                        A[row][j] -= factor * A[col][j]
    for i in range(n):
        if mod:
            det = det * A[i][i] % mod
        else:
            det *= A[i][i]
    if mod:
        det = (det % mod + mod) % mod
    return det

def determinant_naive(mat):
    """Naive recursive determinant via cofactor expansion. O(n!)."""
    n = len(mat)
    if n == 1:
        return mat[0][0]
    if n == 2:
        return mat[0][0] * mat[1][1] - mat[0][1] * mat[1][0]
    det = 0
    for j in range(n):
        minor = [row[:j] + row[j+1:] for row in mat[1:]]
        det += ((-1) ** j) * mat[0][j] * determinant_naive(minor)
    return det

if __name__ == "__main__":
    assert abs(determinant([[1, 2], [3, 4]]) - (-2)) < 1e-6
    assert abs(determinant([[1, 2, 3], [4, 5, 6], [7, 8, 10]]) - (-3)) < 1e-6
    assert determinant([[1, 0], [0, 1]]) == 1
    assert determinant([[0, 0], [0, 0]]) == 0
    # Mod arithmetic
    assert determinant([[1, 2], [3, 4]], mod=10**9 + 7) == (10**9 + 7 - 2)
    # Naive comparison
    assert abs(determinant([[2, 1, 0], [1, 2, 1], [0, 1, 2]]) - 4) < 1e-6
    assert determinant_naive([[2, 1, 0], [1, 2, 1], [0, 1, 2]]) == 4
    print("determinant: ALL TESTS PASSED")

易错点

• 行交换时需翻转det符号
• 模非质数时不能直接用费马小定理求逆元
• 浮点消元有精度问题，建议用分数或模运算
• 对角线出现0不一定行列式为0（需先消元）

例题

信源

• OI Wiki✓ https://oi-wiki.org/math/linear-algebra/determinant/
• CP-Algorithms✓ https://cp-algorithms.com/linear_algebra/determinant-gauss.html
• 书籍✓ CPH ch23 Matrices (p227-234)