ランダムに生成した行列は高確率で正則

$\mathbb{F}_p ^{2 \times 2}$ の行列をランダムに生成すると、高確率で正則になる。

$\mathbb{F}_p ^{2 \times 2}$ のうち、正則なものは $(p^2-1)(p^2-p)$ 個ある(解析は付録に書いておく)。そのため、ランダムに生成した行列が正則になる確率は

\begin{equation}
\frac{(p^2-p)(p^2-1)}{p^4} = \left( 1-\frac{1}{p} \right) \left( 1 - \frac{1}{p^2} \right)
\end{equation}

である。$p=10^9+7$ だと $6.93\times 10^8$ 個生成してようやく、正則でない行列が生成される確率が 50% 以上となる。つまり、ランダムに生成しただけでは正則でない行列はまず生成されない。

この結果から分かることは、逆元が存在しないと機能しないアルゴリズムであっても、テストケースがランダムに作られていると意外と落ちないということ。テストケースが雑なコンテストだと、これが考慮されてないことが稀にあるので嘘解法のチャンスである。もちろん、落とそうと思えば簡単に落とせるので勧めはしない。

付録

定理:$\mathbb{F}_p ^{n \times n}$ の元のうち正則なものは $(p^n-1)(p^n-p) \cdots (p^n-p^{n-1})$ 個ある。

証明の方針:行列をベクトルを $n$ 個並べたものと考えて、線形独立を崩さないように上の行から決定していくことを考えると式が求まる。

証明:第 $i$ 行目のベクトルを $\mathbf{u}_i$ と置く。
$\mathbf{u}_1$ の候補は $\mathbf{0}$ 以外なら何でも良いので $p^n-1$ 通りある。$\mathbf{u}_2$ の候補は、$0 \mathbf{u}_1, \ldots (p-1) \mathbf{u}_1$ 以外なら何でも良いので $p^n-p$ 通りある。

$\mathbf{u}_1,\ldots,\mathbf{u}_k$ が定まっていたとする。このとき $\mathbf{u}_{k+1}$ を付け加えて線形独立であるためには、$\mathbf{u}_{k+1}$ が $\mathbf{u}_1, \ldots, \mathbf{u}_k$ が張る部分空間に属さなければ良い。つまり $p^n - p^k$ 通りある。(証明終わり)

感想

単なるスカラーであれば $1-1/p$ なので、 行列とスカラーで逆元を持つ確率はほとんど変わらない。