1. 行列積の検証とFreivaldsのアルゴリズム
Freivaldsの乱択アルゴリズムとは、与えられた三つの$n\times n$行列 $A,B,C$ に対して$AB=C$かどうかを$O(n^2)$時間で乱択を用いて判定する方法です (ただし$A,B,C$は体$K$上の行列で、体の演算に要する計算時間は省略)。具体的には以下のアルゴリズムを考えます:
1. 一様ランダムなベクトル $r\sim \{0,1\}^n$ を選ぶ。
2. $ABr \ne Cr$ならば「$AB\ne C$」を出力して終了する。
3. ステップ1-2を何度も繰り返して終了しなかったら「$AB=C$」を出力して終了する。
明らかに$AB=C$を満たすとき、このアルゴリズムは確率1でステップ3で$AB=C$を出力します。一方で$AB\ne C$であったとしても、運が悪いと$AB=C$が出力されうることに注意してください。ところがこの悪い事象の発生確率は小さいことが証明できます:
すなわち、ステップ1-2を$T$回繰り返すと、出力結果が誤っている確率は高$々1/2^T$となります。正当性の証明は他の方の記事がありましたので、そちらを参照します。
そもそも$AB=C$かどうかの判定は、実際に$AB$を計算してそれを$C$と比較すれば良いのですが、行列積の計算が$O(n^2)$時間で行えるかどうかはこの分野の重大な未解決問題です。ところが単に行列積が正しいかどうかの検証は乱択を許すことによって簡単にできてしまうというのが面白いポイントです。このような「行列積を計算する」「行列積の検算を行う」の間にギャップがあるかどうか、つまり簡単に検証できる問題は簡単に解けるか否か?という問題はまさしくP対NP問題の「スケールダウン版」とも言えるでしょう。
2. ちょっとした変種
Freivaldsのアルゴリズムでは
\[ABr = Cr \]
をチェックしましたが、少し修正した以下のアルゴリズムを考えます。ここでは有限体$\mathbb{F}$上の行列を考えます。
1. 独立一様ランダムに二つのベクトル $s,r\sim \mathbb{F}^n$ を選ぶ。
2. $r^\top ABs \ne r^\top Cs$ならば「$AB\ne C$」を出力して終了する。
3. ステップ1-2を何度も繰り返して終了しなかったら「$AB=C$」を出力して終了する。
Freivaldsのアルゴリズムとの違いは
- ランダムベクトルの各成分が$\{0,1\}$ではなく$\mathbb{F}$上でランダムになってる
- 行列ベクトル積ではなく、二次形式で比較している
という点です。体$\mathbb{F}$が$|\mathbb{F}|\ge 3$なら、その正当性が簡単に証明できます。
証明
関数 $F\colon \mathbb{F}^n\times\mathbb{F}^n \to \mathbb{F}$を
\[
F(r,s) = r^\top (AB-C) s\tag{1}
\]
と定義すると、これは$2n$個の変数からなる二次多項式となり、しかも$AB\ne C$であることからこれは非ゼロ多項式である。したがって、Schwartz-Zippelの補題から
\[
\Pr_{r,s\sim\mathbb{F}^n}[F(r,s) = 0] \le \frac{\deg F}{|\mathbb{F}|} \le \frac{2}{3}
\]
となり主張を得ます。
実際に論文に使うのであればアルゴリズム1.1のようなものを使えば良いのですが、個人的にはSchwartz-Zippelの応用としても面白いし証明も単純なのでこちらの方が教育的ではあると考えています。
3. ランダムネスの削減
アルゴリズム1.1や2.1は乱択アルゴリズムですが、決定的に（すなわちランダムネスを使わずに）行列積の（積計算より高速に）検算はできるのでしょうか？これは実は未解決で、最近も論文（例えば[Künnemann, ESA2018]）が出ているようなトピックです。
決定的にするのは難しそうなので、使用するランダムビットを削減する（randomness-efficient）という方針で考えてみましょう。アルゴリズム1.1や2.1はそれぞれ$n$ビットと$O(n\log_2|\mathbb{F}|)$ビットのランダムネスを使っています。これを$0$ビットにできれば脱乱択できたことになります。
ここでは$\mathbb{F}\ge 3n$であれば、簡単に$O(\log |\mathbb{F}|)$ビットに削減できることを示します。このような結果自体は90年代（[Kimbrel, Sinha, IPL1993]）には知られていました。具体的には以下のアルゴリズムを考えます。$\mathbb{F}$は十分大きいと思ってください。
1. 体$\mathbb{F}$から一様ランダムに二つの要素 $a,b \sim \mathbb{F}$ を選び、
\begin{align*}
&r = \begin{pmatrix}1 \\ a \\ a^2 \\ \vdots \\ a^{n-1}\end{pmatrix}, \\
&s = \begin{pmatrix}1 \\ b \\ b^2 \\ \vdots \\ b^{n-1} \end{pmatrix}
\end{align*}
とする。
2. $r^\top ABs \ne Cs$ならば「$AB\ne C$」を出力して終了する。
3. ステップ1-2を何度も繰り返して終了しなかったら「$AB=C$」を出力して終了する。
最初の二つのアルゴリズムに比べて、ランダムベクトルの取り方を少し工夫しています。このアルゴリズムは
\[
2\log_2|\mathbb{F}|
\]
ビットのランダムネスを用いています。$\mathbb{F}\ge 3n$の場合には以下のように正当性が担保されます。
証明
定理2.1の証明とほぼ同じです。関数$G\colon\mathbb{F}^2\to\mathbb{F}$を
\[
G(a,b) = (1,a,a^2,\dots,a^{n-1})(AB-C)\begin{pmatrix} 1 \\ b \\ b^2 \\ \vdots \\ b^{n-1} \end{pmatrix} \tag{2}
\]
で定義します。仮定より$AB\ne C$なので、この関数は非ゼロな二変数多項式であり、その次数は$2n-2\le 2n$です。仮定より$|\mathbb{F}|\ge 3n$なので、Schwartz-Zippelより
\[
\Pr_{a,b\sim\mathbb{F}}[G(a,b)=0] \le \frac{2n}{3n} = \frac{2}{3}
\]
となります。すなわち、各反復でアルゴリズム3.1が誤って「$AB=C$」を出力してしまう確率は高々$1/3$ということになり、主張を得ます。
もっと色々と工夫の余地があり、例えば$r$と$s$を別々にサンプルしていましたが、$\mathbb{F}$が十分大きいという仮定を用いて良いならば$r=s$としてSchwartz-Zippelを適用すればランダムビット長を半分にできると思います。
4. 誤り訂正符号に基づく検算
実は行列積の検算は$AB-C$という行列とみなしたとき、それを誤り訂正符号で符号化し、それが非ゼロ文字列かどうかを確率的に検証している作業とみなすことができます。大雑把にいうと、誤り訂正符号とは文字列から文字列への写像であり、今回の問題設定では行列を符号化するような写像
\[
\mathsf{Enc}\colon \mathbb{F}^{n\times n}\to \mathbb{F}^{N\times N}
\]
であって、
任意の非ゼロ行列$D\in\mathbb{F}^{n\times n}$に対して、$\mathsf{Enc}(D)$は$\delta\cdot N^2$個の非ゼロ成分を含む（$\delta$は適当な定数）
という性質を持つものです。これを用いて行列検算に対する以下のアルゴリズムを考えます：
1. $\mathbf{i},\mathbf{j}\sim N$を選ぶ（ここでは$N$は集合として扱う）
2. $\mathsf{Enc}(AB-C)_{\mathbf{i},\mathbf{j}}\ne 0$ならば「$AB\ne C$」を出力
3. ステップ1-2を何度も繰り返して終了しなかったら「$AB=C$」を出力して終了する。
このアルゴリズムはアルゴリズム2.1と3.1を特殊ケースとして含んでいます。例えばアルゴリズム2.1では$N=\mathbb{F}^n$として、式(1)で考えた関数を用いて
\[
\mathsf{Enc}(D)_{r,s} = F(r,s)
\]
で定まる写像を考えることになります。アルゴリズム3.1は、$N=\mathbb{F}$として、式(2)の関数
\[
\mathsf{Enc}(D)_{a,b} = G(a,b)
\]
を考えていることに他なりません。これらの関数が誤り訂正符号として望ましい性質を持つことの証明のみが非自明です。したがって、この非自明な箇所がすでに証明されているような符号を作れば、いろんな行列積検算なアルゴリズムが考えられる、ということになります。
実はこの「行列を誤り訂正符号で行列に符号化する」アイデアは[Hirahara, Shimizu, STOC2025]のアイデア元の一つになっています（この論文を書いてるときに本記事の内容を思いついた）。
