Day 071-Q5 — 多項式行列式（Bareiss Algorithm + mod p Gaussian Elimination）

2026-06-24 赤色 Master / Phase 8+ ★★★★★★★★★ Bareiss・行列式・mod p・逆行列

問題

整数行列 $A \in \mathbb{Z}^{N \times N}$ と素数 $p$ が与えられる。以下を求めよ。

  1. $\det(A) \bmod p$
  2. $\det(A)$ の符号（正・負・ゼロ）
  3. $A^{-1} \bmod p$（$\det(A) \not\equiv 0 \pmod{p}$ の場合）

行列のエントリは絶対値が最大 $10^6$。Bareiss Algorithm を使い整数のまま行列式を計算せよ（Python の多倍長整数を利用）。

制約

パラメータ範囲
$N$$1 \le N \le 500$
$p$素数, $10^9 < p < 10^{10}$
$|a_{i,j}|$$\le 10^6$

入出力例

入力例 1

3 1000000007
1 2 3
4 5 6
7 8 10

出力例 1

det mod p: 3
sign: +
A_inv mod p:
1000000002 4 1000000004
1000000002 11 1000000001
3 1000000001 3

入力例 2（特異行列）

3 1000000007
1 2 3
4 5 6
7 8 9

出力例 2

det mod p: 0
sign: 0
(逆行列は存在しない)

逆行列の負値は mod $p$ で $+p$ して非負に変換する。例: $-2 \equiv 10^9+7-2 = 1000000005 \pmod{10^9+7}$。

概念図: Bareiss アルゴリズムの流れ

Bareiss アルゴリズム: 整数のままゼロ除算なし行列式計算 各ステップで M[i][j] = (pivot×M[i][j] - M[i][k]×M[k][j]) / prev_pivot （常に整数） 初期行列 A | 1 2 3 | | 4 5 6 | | 7 8 10| k=0後 (prev=1) | 1 2 3 | | 0 -3 -6 | ←(1×5 - 4×2)/1 | 0 -6 -11| ←(1×8 - 7×2)/1 k=1後 (prev=-3) | 1 2 3 | | 0 -3 -6 | | 0 0 3 | ←(-3×-11-(-6)×-6)/(-3)=3 det = sign×M[2][2] = (+1)×3 = 3 Bareiss 更新式（Sylvester's Identity より） M_k[i][j] = (M_{k-1}[k][k] × M_{k-1}[i][j] - M_{k-1}[i][k] × M_{k-1}[k][j]) / prev ここで prev = M_{k-2}[k-1][k-1]（前ステップのピボット） この除算は常に整数で割り切れる（Sylvester の恒等式の保証） 中間値のビット数: O(N × log(max_value)) 程度まで増加 mod p 逆行列: Gauss-Jordan 消去法 1. 拡張行列 [A | I] を mod p で構成 2. 各ピボット a の逆元: a^{-1} ≡ a^{p-2} (mod p) (Fermatの小定理) 3. 行の加算で他の行を0にする 4. 結果: [I | A^{-1} mod p] p が素数なので Z/pZ は体 → Gauss-Jordan が適用可能。O(N³) + O(N² log p) for 逆元

ヒント（段階的開示）

ヒント1: 方向性
Bareiss アルゴリズムは整数のまま Gaussian Elimination を行い、各ステップで除算が割り切れることを利用して行列式を計算する。中間値は大きくなるが Python の多倍長整数で対処。mod $p$ での逆行列は Gauss-Jordan 消去法（$p$ が素数なので体演算が可能）。
ヒント2: アプローチ

Bareiss の手順:

  1. 行列をコピー
  2. 各ステップ $k$: ピボット選択 → 他の行を消去
  3. 更新式: M[i][j] = (M[k][k]*M[i][j] - M[i][k]*M[k][j]) // prev
  4. $\det(A) = \text{sign} \times M[N-1][N-1]$

mod p 逆行列: 拡張行列 $[A \mid I]$ に Gauss-Jordan を mod $p$ で適用。ピボットの逆元は pow(pivot, p-2, p)。

ヒント3: コード骨格 
def bareiss_det(mat):
    n = len(mat); M = [row[:] for row in mat]
    sign = 1; prev = 1
    for k in range(n):
        pivot_row = next((i for i in range(k,n) if M[i][k]), -1)
        if pivot_row == -1: return 0
        if pivot_row != k:
            M[k], M[pivot_row] = M[pivot_row], M[k]
            sign *= -1
        for i in range(k+1, n):
            for j in range(k+1, n):
                M[i][j] = (M[k][k]*M[i][j] - M[i][k]*M[k][j]) // prev
            M[i][k] = 0
        prev = M[k][k]
    return sign * M[n-1][n-1]

模範解答 (Python)

import sys

def solve():
    data = sys.stdin.read().split()
    idx = 0
    N = int(data[idx]); idx += 1
    p = int(data[idx]); idx += 1

    A = []
    for i in range(N):
        row = [int(data[idx + j]) for j in range(N)]
        idx += N
        A.append(row)

    # Bareiss アルゴリズム
    def bareiss_det(mat):
        n = len(mat)
        M = [row[:] for row in mat]
        sign = 1; prev = 1
        for k in range(n):
            pivot_row = -1
            for i in range(k, n):
                if M[i][k] != 0:
                    pivot_row = i; break
            if pivot_row == -1:
                return 0
            if pivot_row != k:
                M[k], M[pivot_row] = M[pivot_row], M[k]
                sign *= -1
            for i in range(k + 1, n):
                for j in range(k + 1, n):
                    M[i][j] = (M[k][k] * M[i][j] - M[i][k] * M[k][j]) // prev
                M[i][k] = 0
            prev = M[k][k]
        return sign * M[n-1][n-1]

    det = bareiss_det(A)
    det_mod = det % p

    if det > 0: sign_str = "+"
    elif det < 0: sign_str = "-"
    else: sign_str = "0"

    print(f"det mod p: {det_mod}")
    print(f"sign: {sign_str}")

    if det_mod == 0:
        print("(逆行列は存在しない)")
        return

    # mod p 逆行列 (Gauss-Jordan)
    def gauss_jordan_inv_mod(mat, mod):
        n = len(mat)
        M = [[mat[i][j] % mod for j in range(n)] +
             [1 if i == j else 0 for j in range(n)]
             for i in range(n)]

        for k in range(n):
            pivot_row = next((i for i in range(k, n) if M[i][k] % mod != 0), -1)
            if pivot_row == -1:
                return None
            M[k], M[pivot_row] = M[pivot_row], M[k]
            inv_pivot = pow(M[k][k] % mod, mod - 2, mod)
            M[k] = [(x * inv_pivot) % mod for x in M[k]]
            for i in range(n):
                if i != k and M[i][k] % mod != 0:
                    f = M[i][k] % mod
                    M[i] = [(M[i][j] - f * M[k][j]) % mod for j in range(2 * n)]
        return [[M[i][n + j] for j in range(n)] for i in range(n)]

    inv = gauss_jordan_inv_mod(A, p)
    if inv is None:
        print("(逆行列は存在しない)")
    else:
        print("A_inv mod p:")
        for row in inv:
            print(*row)

solve()

Step-by-Step 解説

Step 1: Bareiss アルゴリズムの原理

通常の Gaussian Elimination では有理数が現れるが、Bareiss は除算が必ず整数で割り切れることを利用。更新式:

$$M_k[i][j] = \frac{M_{k-1}[k][k] \cdot M_{k-1}[i][j] - M_{k-1}[i][k] \cdot M_{k-1}[k][j]}{M_{k-2}[k-1][k-1]}$$

これは Sylvester の恒等式より整数で割り切れることが保証される。

Step 2: 行列式の符号管理

行の入れ替えを行うたびに sign *= -1。最終的に det = sign * M[N-1][N-1]。

Step 3: mod p での逆行列

$p$ が素数のとき $\mathbb{Z}/p\mathbb{Z}$ は体（Field）なので Gauss-Jordan 消去が使える。ピボットの逆元を Fermat の小定理 $a^{-1} \equiv a^{p-2} \pmod{p}$ で計算。

Step 4: 計算量分析

処理計算量
Bareiss（整数演算）$O(N^3)$（多倍長整数）
Gauss-Jordan mod $p$$O(N^3)$
Fermat 逆元$O(\log p)$ per call

Step 5: Python 実装上の注意

整数のままの Bareiss は中間値が $(10^6)^N$ 程度まで増大する可能性がある。$N = 500$ では実用上遅くなることがある。mod $p$ のみで良い場合は最初から Gauss-Jordan を mod $p$ で行うべき。

よくあるミス

ミス原因正しい書き方
除算が割り切れないと思うBareiss の保証を知らない// prev（整数除算）で問題なし
mod p 逆元を浮動小数で計算誤差が出るpow(a, p-2, p) を使う
負の mod 演算Python は常に非負問題なし（(-3) % 7 == 4）
行の交換後の符号管理行列式が変わる交換ごとに sign *= -1

次のステップ

  • 発展問題: 多項式行列の行列式 $\det(A(x)) \in \mathbb{F}_p[x]$ の計算（多項式 Bareiss）
  • Hessenberg 化による行列式計算の高速化
  • 特性多項式 $\det(\lambda I - A)$ の計算（Berkowitz's Algorithm）
  • 確率的行列式計算（Schwartz-Zippel を使ったランク判定）

自己評価