割れない時の行列式 - noshi91のメモ

概要

逆元が必ずしもない状況で行列式を計算する方法を紹介します

一般の可換環上の行列式

n91lib_rs/division_free_determinant.rs at master · noshi91/n91lib_rs · GitHub

除算を使わない $\Theta(n^4)$ のシンプルなアルゴリズムが知られています。除算無しでも $o(n^3)$ になるらしいのですが、詳しく勉強してないので詳細は分かりません。

${\rm mod}$ 合成数

掃き出し法のアルゴリズムを少し変えるだけで高速に計算できます。掃き出し法は「ある行を使って別の行の先頭要素を 0 にする」を繰り返すアルゴリズムなので、この部分を何とかできればいいです。そこで、0 にしたい列の要素を一旦 ( ${\rm mod}\ m$ ではなく) ただの数だと思って、ユークリッド互除法を行います。ユークリッド互除法は定数倍と加減算なので、 ${\rm mod}\ m$ でも問題なく計算できます。これを繰り返せば $O(n^3 \log(m))$ のアルゴリズムが得られます。 ${\rm gcd}$ を繰り返しとる操作は計算量が落ちるので、実際には $O(n^3 + n^2 \log(m))$ になっています。