核心概述
在整数矩阵上精确计算行列式，采用 Bareiss 无分数消元或多素模取 det 后用 CRT 重建，时间复杂度 O(n^3)。
原文引述
Description: Exact integer determinant via Bareiss fraction-free elimination (O(n^3)). Alternative: compute det mod several primes and reconstruct with CRT using a Hadamard bound for correctness. Time: O(n^3) Status: tested ——摘自本节点现有英文注释
展开阐述
-
定义与背景、典型场景
- 整数行列式（Integer Determinant）：对整矩阵 A 计算 det(A) 的精确整数值。
- 适用于需要确切整数结果且避免浮点误差的场景；当元素/规模较大时可转用多模重建。
-
接口/字段/数据结构与输入输出语义（据实现约定）
- long long detBareiss(vector<vector
> A) - 输入：n×n 整数矩阵 A（可按值传递以就地消元）。
- 输出：det(A)；当可能超出 64 位时需使用更大整数类型。
- long long detCRT(const vector<vector
>& A) - 多个素模下取 det 并按 081-数论-中国剩余定理 合并；在界限保证下返回精确值，否则返回模 M 的代表元。
- long long detBareiss(vector<vector
-
核心流程与关键要点
- Bareiss（无分数消元）
- 初始化 prev=1，sgn=1；逐列选择非零主元，必要时交换行并更新符号。
- 消元更新：A[i][j] = (A[i][j]*A[k][k] − A[i][k]*A[k][j]) / prev（k=0 时 prev=1），对整数矩阵应整除。
- 迭代结束 det = sgn * A[n−1][n−1]；全程整数运算，避免分数放大。
- 中间乘法可用 __int128 保护（见 090-数论-长整型模乘 的安全乘思路）。
- CRT 重建（可选）
- 选择若干互素素模 p_i，分别计算 det_i ≡ det(A) (mod p_i)（可用模高斯）。
- 用 081-数论-中国剩余定理 合并得 D∈[0,M)，M=∏p_i。
- 依据 Hadamard 界选择足够多的模使 M 超界限，并按最接近代表恢复符号。
- 依赖：088-数论-模逆、091-数论-模幂、094-数论-模运算。
- Bareiss（无分数消元）
-
数值稳定性/精度注意
- Bareiss 中整除性应成立；若出现不整除多为实现/溢出问题。
- 溢出风险：元素大/规模大时优先 CRT 或大整数类型。
- 行/列交换每次改变符号；sgn 需独立维护。
-
复杂度与边界条件、常见变体
- Bareiss：O(n^3)。
- CRT：每个模 O(n^3)，t 个模为 O(t·n^3)；常见 t∈{2..4}。
- 与 097-数值算法-行列式 的关系：浮点法有数值误差，整数需求使用 Bareiss/CRT。