ライツアウトの数え上げ問題を多項式のgcdで解く
またまたライツアウトのお話です。
「ライツアウトの数え上げ問題」とは、
・$m \times n$ライツアウトのクリア可能な盤面はいくつあるか？
・それぞれのクリア可能な盤面に対し、解き方は何通りあるか？
という問題のことです。今回の記事のタイトルを決めるにあたって、私が勝手に作った言葉です。
これらの問題については、 前々回の記事 で行列を用いた解答が得られていますが、今回はさらに、ある2つの多項式の最大公約数を調べることによって上記の問題の解答を得ることができる、という結果を紹介します。
なお、今回の話はあくまで盤面や解き方の「個数」のみに着目した話であり、具体的な盤面や解き方についてはほぼ触れません。あらかじめご承知おきください。
復習
前々回の記事で得られた結果をおさらいします。以下、行列の成分や多項式の係数は有限体$\mathbb F_2$の代数閉包$\overline{\mathbb F_2}$の元であるとします。まず$m \times m$行列$A_m$を
$$ \begin{pmatrix}
1 & 1 & & & O \\
1 & 1 & 1 & & \\
& 1 & \ddots & \ddots & \\
& & \ddots & \ddots & 1 \\
O & & & 1 & 1
\end{pmatrix}$$
で定め、多項式列 $f_0(x), f_1(x), \ldots$ を
$$ f_0(x) = 1, \quad f_1(x) = x, \quad f_n(x) = x f_{n-1}(x) + f_{n-2}(x)$$
で定めます。ここで、前々回の記事から多項式列の添え字を1つずらしています。このほうが後の記述がすっきりします。また、$f_n(x)$がちょうど$n$次式になります。
前々回の記事では、以下の結果を得ました。
$m \times n$ライツアウトにおいて、クリア可能な盤面の個数は $2^{mn - m + \rank(f_{n}(A_m))}$ であり、それぞれに対して $2^{m - \rank(f_n(A_m))}$ 通りの解き方が存在する。
どうやら$m- \rank(f_n(A_m))$という値が重要そうなので、名前を付けておきます。
$c_{m,n} := m - \rank(f_n(A_m))$ と定め、これを$m \times n$ライツアウトの特性数と呼ぶ。
これも私が勝手に呼んでいるだけです。ライツアウトの言葉で言えば、
$m \times n$ライツアウトのクリア可能な盤面に対し、解き方の個数はある非負整数$c$を用いて$2^c$と表せるので、そのときの$c$を$m \times n$ライツアウトの特性数と呼び、$c_{m,n}$で表す。
と言えますね。このとき$m \times n$ライツアウトのクリア可能な盤面の個数は$2^{mn - c_{m,n}}$となります。
例えばよく知られているように、$5 \times 5$ライツアウトでは、クリア可能な盤面に対して4つの解き方が存在するので、$c_{5,5}=2$となります。
$m \times n$行列$A$に対し、$n - \rank(A)$という値は$A$の退化次数(Nullity)などと呼ばれ、$\mathrm{Null}(A)$などと書かれることがあります。この記号を用いれば$c_{m,n} = \mathrm{Null}(f_n(A_m))$と簡潔に書けるのですが、これらの用語や記号がどのぐらい一般的に使われているかよく分からないため、とりあえず使わずに進めることにします。
主張
では、今回証明する主張を述べます。
$m \times n$ライツアウトの特性数$c_{m,n}$は、$f_n(x)$と$f_m(x+1)$の最大公約数の次数に等しい。
行列はどこへやら。なんと多項式の最大公約数を計算するだけで特性数が求まってしまうのです。不思議な話ですね。
なお、上の定理は私のオリジナルというわけではありません。参考文献GKTの Theorem 3(3) で既に示されているものになります。
これが成り立つかもしれないという予想には自分でたどり着いていたのですが、証明ができず、試しに探してみたら上の論文を見つけた、という流れです。また、Mも参考になりました。
本記事で与える証明は、大部分は自分で考えたものですが、一部でMのアイデアを用いています(GKTでもほぼ同じ考えは用いているのですが、先に見つけたのがMなのでMからの引用ということにしています)。
方針
$c_{m,n}=m - \rank(f_n(A_m))$なので、$\rank(f_n(A_m))$を求めることを考えます。$A_m$のジョルダン標準形を用いれば、以下のような方針が立ちます。
$A_m$のジョルダン標準形を
$$ P^{-1}A_m P = J = \matcc{J(\lambda_1, m_1)}{}{O}{}{\ddots}{}{O}{}{J(\lambda_k, m_k)}$$
とおきます。ここで、$P$は正則行列で、
$$ J(\lambda_i, m_i) = \begin{pmatrix}
\lambda_i & 1 & & O \\
& \ddots & \ddots & \\
& & \ddots & 1 \\
O & & & \lambda_i
\end{pmatrix}$$
は$m_i \times m_i$のジョルダン細胞です。すると
$$ f_n(A_m) = P f_n(J) P^{-1}$$
ですが、正則行列をかけても階数は変わらないので、
$$ \rank f_n(A_m) = \rank f_n(J) = \rank \matcc{f_n(J(\lambda_1, m_1))}{}{O}{}{\ddots}{}{O}{}{f_n(J(\lambda_k, m_k))} = \sum_{i=1}^k \rank(f_n(J(\lambda_i, m_i)))$$
と計算できます。
あとは$\rank(f_n(J(\lambda_i, m_i)))$の計算に帰着されます。この計算は後ほど行うとして、問題は、そもそも$A_m$のジョルダン標準形は求まるのか？ということです。
$A_m$の固有多項式
ひとまず$A_m$の固有多項式について考えてみます。まず
$$ |A_m + \lambda E| = \begin{vmatrix}
1 + \lambda & 1 & & & O \\
1 & 1 + \lambda & 1 & & \\
& 1 & \ddots & \ddots & \\
& & \ddots & \ddots & 1 \\
O & & & 1 & 1 + \lambda
\end{vmatrix}$$
です。ここで、$\mathbb F_2$で考えているので、通常マイナスのところをプラスにしています。第1行について余因子展開すれば
$$ |A_m + \lambda E| = (1+\lambda)|A_{m-1} + \lambda E| + |A_{m-2} + \lambda E|$$
が分かります。すなわち、$A_m$の固有多項式を$g_m(\lambda)$と置けば
$$ g_m(\lambda) = (1 + \lambda)g_{m-1}(\lambda) + g_{m-2}(\lambda)$$
が成り立ちます。これと
$$ g_1(\lambda) = \lambda + 1, \qquad g_2(\lambda) = \lambda^2$$
から、帰納的に$g_m(\lambda)$を求めることができます。
あれ？似たような漸化式をどこかで見たような……？
試しに$\lambda+1 = x$としてみます。すると
$$ g_m(x+1) = x g_{m-1}(x+1) + g_{m-2}(x+1),$$
$$ g_1(x+1) = x, \qquad g_2(x+1) = (x+1)^2 = x^2 + 1$$
となります。なんとこれは、冒頭で述べた多項式列 $f_0(x), f_1(x), \ldots$ の漸化式にちょうど一致しています！したがって、
$$ g_m(x+1) = f_m(x)$$
が成り立ちます。言い換えれば
$$ g_m(\lambda) = f_m(\lambda+1)$$
も成り立ちます。
$A_m$の固有多項式は$f_m(\lambda+1)$である。
余談
ここはただの自分語りなので飛ばしても大丈夫です。
ここまでは自力でたどり着けました。ただ、$A_m$のジョルダン標準形についてこれ以上詳しいことは分からないだろうと諦めてしまいました。それでも特性数が$f_n(x)$や$f_m(x+1)$と関係しそうだということは分かったので、既知の特性数と比較して、定理2が成り立ちそうだと予想することはできました。あとは不等式で評価したりもしていて、元々はそのあたりの記事を書くつもりでした。
そして、このあたりでさすがに先行研究が気になってきました(それまでは日本語のブログ記事を軽くあさる程度でした)。それで調べてみた結果、上で挙げた論文を見つけたというわけです。しかもその中に、ちょうど諦めていた部分を突破する方法が載っていました。これを知ってしまった以上、記事の内容を変更せざるを得ず、元々書こうとしていた記事をボツにし、本記事を書くに至ったのです。
というわけで、記事が1つボツになった悲しさを紛らわすための余談でした。
気を取り直して先に進みましょう。次章「最小多項式」の内容が、まさにMを参考にした部分です。それでは続きをどうぞ↓
最小多項式
ここで、最小多項式という概念を導入します。ご存じの方も多いと思いますが、通常の線形代数の授業ではあまり扱われないと思いますので、一応ちゃんと書いておきます。
$K$を体とする。$K$成分の任意の正方行列$A$に対し、$f(A)=O$を満たす1次以上の$K$係数モニック多項式$f(x)$のうち、次数が最小であるものが一意に存在する。これを$A$の$K$上の最小多項式という。
この記事では、$K=\overline{\mathbb F_2}$として考えます。ケーリー・ハミルトンの定理から、$f(A)=O$を満たす1次以上のモニック多項式$f(x)$は少なくとも1つ存在します。しかも、$A$が$n$次正方行列なら、最小多項式は$n$次以下であることが分かります。
以下が知られています。
正方行列$A$の固有多項式が
$$ f(x) = (-1)^n(x - \lambda_1)^{m_1} \cdots (x - \lambda_k)^{m_k} \qquad (\lambda_1, \ldots, \lambda_k\text{ は } A \text{の相異なる固有値})$$
であるとすると、$A$の$K$上の最小多項式は
$$ f(x) = (x - \lambda_1)^{l_1} \cdots (x - \lambda_k)^{l_k} \qquad (1 \leqq l_i \leqq m_i)$$
の形である。さらにこのときの$l_i$は、$A$の固有値$\lambda_i$に対するジョルダン細胞の最大サイズに等しい。
この記事では$K=\overline{\mathbb F_2}$なので、$(-1)^n$は無視してかまいません。
命題から、$A$のジョルダン標準形が分かれば最小多項式も分かるわけですが、逆に言えば、もし何らかの方法で$A$の最小多項式が求まったならば、そこから$A$のジョルダン標準形についての情報が得られるとも言えます。
$A_m$の最小多項式
では、$A_m$の最小多項式はなんでしょうか？これを求めるため、1つ補題を示します。以下、
$$ \bm e_1 = \matda 10{\vdots}0$$
とします。
$\bm e_1, \ A_m \bm e_1, \ A_m^2 \bm e_1, \ \ldots, \ A_m^{m-1} \bm e_1$は$\overline{\mathbb F_2}$上1次独立である。
$A_m$の定義は
$$ A_m = \begin{pmatrix}
1 & 1 & & & O \\
1 & 1 & 1 & & \\
& 1 & \ddots & \ddots & \\
& & \ddots & \ddots & 1 \\
O & & & 1 & 1
\end{pmatrix}$$
であった。これを用いて計算すれば、$k=0,1,\ldots, m-1$に対し
$$ A_m^k \bm e_1 = \begin{pmatrix}
* \\ \vdots \\ * \\ 1 \\ 0 \\ \vdots \\ 0
\end{pmatrix} \leftarrow \text{第}k+1 \text{成分}$$
となることが分かる。実際、$k=0$のときは良く、ある$k$で成り立つとすれば
$$ A_m^{k+1}\bm e_1 = A_m (A_m^k \bm e_1) = \begin{pmatrix}
1 & 1 & & & O \\
1 & 1 & 1 & & \\
& 1 & \ddots & \ddots & \\
& & \ddots & \ddots & 1 \\
O & & & 1 & 1
\end{pmatrix} \begin{pmatrix}
* \\ \vdots \\ * \\ 1 \\ 0 \\ \vdots \\ 0
\end{pmatrix}\leftarrow \text{第}k+1 \text{成分}$$
を計算することで、$k+1$でも成り立つことが確かめられる。よって、$\bm e_1, \ A_m \bm e_1, \ A_m^2 \bm e_1, \ \ldots, \ A_m^{m-1} \bm e_1$を並べてできる行列は上三角行列で、対角成分はすべて$1$となるので、行列式が$1$であるから正則。したがって$\bm e_1, \ A_m \bm e_1, \ A_m^2 \bm e_1, \ \ldots, \ A_m^{m-1} \bm e_1$は$\overline{\mathbb F_2}$上1次独立である。
上の補題から、$A_m$の最小多項式が分かります。
$A_m$の最小多項式は$A_m$の固有多項式に等しい。
$A_m$の最小多項式が$m-1$次以下であると仮定し、それを
$$ f(x) = x^k + a_{k-1}x^{k-1} + \cdots + a_0$$
とおく。$f(A_m) = O$の両辺に右から$\bm e_1$をかけると
$$ A_m^k \bm e_1 + a_{k-1}A_m^{k-1} \bm e_1 + \cdots + a_0 \bm e_1 = \mathbf 0$$
を得る。ここで、$A_m^k \bm e_1$の係数が$1$であることに注意。一方補題5より$A_m^k \bm e_1, A_m^{k-1} \bm e_1, \ldots, \bm e_1$は$\overline{\mathbb F_2}$上1次独立であるので、これは矛盾。したがって$A_m$の最小多項式は$m$次であり、命題4より固有多項式に等しい。
$A_m$の各固有値$\lambda$に対し、$\lambda$に対応する$A_m$のジョルダン細胞はただ1つ存在し、そのサイズは固有値$\lambda$の重複度に等しい。
ジョルダン標準形を求めるのにこんな方法があるとは……。
特性数を求める
これで必要な手掛かりは揃いました。あとは計算していくだけです！
$A_m$の固有多項式(これは$f_m(x+1)$に等しい)を$\overline{\mathbb F_2}$の範囲で因数分解したものを
$$f_m(x+1) = (x - \lambda_1)^{m_1} \cdots (x - \lambda_k)^{m_k} \qquad (\lambda_1, \ldots, \lambda_k\text{ は } A \text{の相異なる固有値})$$
としましょう。すると定理6系1から、$A_m$のジョルダン標準形は
$$ \matcc{J(\lambda_1, m_1)}{}{O}{}{\ddots}{}{O}{}{J(\lambda_k, m_k)}$$
となります。さらに「方針」で述べた計算により
$$ \rank(f_n(A_m)) = \sum_{i=1}^k \rank(f_n(J(\lambda_i, m_i)))$$
となります。
$\rank(f_n(J(\lambda_i, m_i)))$を求めるため、さらに$f_n(x)$の因数分解も考えて
$$ f_n(x) = (x - \mu_1)^{n_1} \cdots (x - \mu_l)^{n_l} \qquad (\mu_1, \ldots, \mu_l \text{ は相異なる})$$
とします。ここで、記述をしやすくするため、$f_m(x+1)$と$f_n(x)$の共通根が先に並んでいるとし、
$$ \lambda_1 = \mu_1, \quad \lambda_2 = \mu_2, \quad \ldots, \quad \lambda_{k_0} = \mu_{k_0}$$
で、$\lambda_{k_0+1}, \ldots, \lambda_k$は$f_n(x)$の根でなく、$\mu_{k_0+1}, \ldots, \mu_l$は$f_m(x+1)$の根でないとします。
さて、
$$ f_n(J(\lambda_i, m_i)) = (J(\lambda_i, m_i) - \mu_1 E)^{n_1} \cdots (J(\lambda_i, m_i) - \mu_l E)^{n_l} = J(\lambda_i - \mu_1, m_i)^{n_1} \cdots J(\lambda_i - \mu_l, m_i)^{n_l}
$$
と計算できます。ここで、$\lambda_i \neq \mu_j$ならば$J(\lambda_i - \mu_j, m_i)$は正則、$\lambda_i = \mu_j$ならば
$$ J(\lambda_i - \mu_j, m_i) = J(0, m_i) = \begin{pmatrix}
0 & 1 & & O \\
& \ddots & \ddots &\\
&& \ddots & 1 \\
O&&&0
\end{pmatrix}$$
となります。したがって、
- $i=1, \ldots, k_0$のとき
$\lambda_i = \mu_i$であり、正則行列をかけても階数が変わらないことから
$$ \rank(f_n(J(\lambda_i, m_i))) = \rank(J(0, m_i)^{n_i})$$
となります。
- $i = k_0+1, \ldots, k$のとき
$f_n(J(\lambda_i, m_i))$は正則なので、
$$ \rank(f_n(J(\lambda_i, m_i))) = m_i$$
となります。
まとめると、
$$ \rank(f_n(A_m)) = \sum_{i=1}^{k_0} \rank(J(0, m_i)^{n_i}) + \sum_{i=k_0+1}^k m_i$$
が得られます。
最後に$\rank(J(0, m_i)^{n_i})$を求めましょう。$J(0, m_i)$のべき乗を計算すると、$1$の並びが1つずつ右上にずれていき、$m_i$乗したところで$O$になることが分かります。例えば$4 \times 4$の場合を書けば
$$ J(0, 4) = \matda{\rowd 0100}{\rowd 0010}{\rowd 0001}{\rowd 0000}$$
$$ J(0, 4)^2 = \matda{\rowd 0010}{\rowd 0001}{\rowd 0000}{\rowd 0000}$$
$$ J(0, 4)^3 = \matda{\rowd 0001}{\rowd 0000}{\rowd 0000}{\rowd 0000}$$
$$ J(0, 4)^4 = O$$
という具合です。したがって
- $n_i < m_i$ のとき $\rank(J(0, m_i))^{n_i} = m_i - n_i$
- $n_i \geqq m_i$ のとき $\rank(J(0, m_i))^{n_i} = 0$
であり、まとめて
$$ \rank(J(0, m_i))^{n_i} = m_i - \min\{ m_i, n_i \}$$
と表せます。
以上から、
$$ \rank{f_n(A_m)} = \sum_{i=1}^{k_0} (m_i - \min\{ m_i, n_i \}) + \sum_{i=k_0+1}^k m_i = m - \sum_{i=1}^{k_0} \min\{ m_i, n_i \}$$
が得られます。したがって$m \times n$ライツアウトの特性数は
$$ c_{m,n} = m - \left( m - \sum_{i=1}^{k_0} \min\{ m_i, n_i \} \right) = \sum_{i=1}^{k_0} \min\{ m_i, n_i \}$$
と計算できます。一方、
$$ \gcd (f_n(x), f_m(x+1)) = (x - \lambda_1)^{\min\{ m_1, n_1 \}} \cdots (x - \lambda_{k_0})^{\min\{ m_{k_0}, n_{k_0} \}}$$
なので、$\gcd (f_n(x), f_m(x+1))$の次数は$\disp \sum_{i=1}^{k_0} \min\{ m_i, n_i \}$となり、特性数に一致します。
というわけで、無事
$m \times n$ライツアウトの特性数$c_{m,n}$は、$f_n(x)$と$f_m(x+1)$の最大公約数の次数に等しい。
を示すことができました！けっこうな長旅でしたね。なお、ここまで$\overline{\mathbb F_2}$の範囲で議論してきましたが、$f_n(x), f_m(x+1)$は$\mathbb F_2$係数であり、その最大公約数も$\mathbb F_2$係数なので、実際に特性数を求める際は$\mathbb F_2$係数で考えれば十分です。
具体例
せっかくなので、特性数$c_{m,n}$をじゃんじゃん求めてみましょう！
多項式の最大公約数を求める方法といえばユークリッドの互除法がまず思い浮かびますが、ここでは普通に因数分解して求めてみます。見た目的にも分かりやすいですし。
漸化式
$$ f_0(x)=1, \quad f_1(x) = x, \quad f_n(x)=xf_{n-1}(x)+f_{n-2}(x)$$
を用いて$f_0(x), f_1(x), \ldots$を求め、$\mathbb F_2$の範囲で既約多項式の積に分解すると、以下のようになります。
| $n$ | $f_n(x)$ | $f_n(x)$ (因数分解) | $f_n(x+1)$ |
|---|---|---|---|
| 1 | $x$ | $x$ | $x+1$ |
| 2 | $x^2+1$ | $(x+1)^2$ | $x^2$ |
| 3 | $x^3$ | $x^3$ | $(x+1)^3$ |
| 4 | $x^4+x^2+1$ | $(x^2+x+1)^2$ | $(x^2+x+1)^2$ |
| 5 | $x^5+x$ | $x(x+1)^4$ | $x^4(x+1)$ |
| 6 | $x^6+x^4+1$ | $(x^3+x^2+1)^2$ | $(x^3+x+1)^2$ |
| 7 | $x^7$ | $x^7$ | $(x+1)^7$ |
| 8 | $x^8+x^6+x^4+1$ | $(x+1)^2(x^3+x+1)^2$ | $x^2(x^3+x^2+1)^2$ |
| 9 | $x^9+x^5+x$ | $x(x^2+x+1)^4$ | $(x+1)(x^2+x+1)^4$ |
| 10 | $x^{10}+x^8+x^4+x^2+1$ | $(x^5+x^4+x^2+x+1)^2$ | $(x^5+x^2+1)^2$ |
こうして因数分解しておけば、最大公約数の次数は一目瞭然ですね。特性数は以下のようになります。
| $m \setminus n$ | 1 | 2 | 3 | 4 | 5 | 6 | 7 | 8 | 9 | 10 |
|---|---|---|---|---|---|---|---|---|---|---|
| 1 | 0 | 1 | 0 | 0 | 1 | 0 | 0 | 1 | 0 | 0 |
| 2 | 1 | 0 | 2 | 0 | 1 | 0 | 2 | 0 | 1 | 0 |
| 3 | 0 | 2 | 0 | 0 | 3 | 0 | 0 | 2 | 0 | 0 |
| 4 | 0 | 0 | 0 | 4 | 0 | 0 | 0 | 0 | 4 | 0 |
| 5 | 1 | 1 | 3 | 0 | 2 | 0 | 4 | 1 | 1 | 0 |
| 6 | 0 | 0 | 0 | 0 | 0 | 0 | 0 | 6 | 0 | 0 |
| 7 | 0 | 2 | 0 | 0 | 4 | 0 | 0 | 2 | 0 | 0 |
| 8 | 1 | 0 | 2 | 0 | 1 | 6 | 2 | 0 | 1 | 0 |
| 9 | 0 | 1 | 0 | 4 | 1 | 0 | 0 | 1 | 8 | 0 |
| 10 | 0 | 0 | 0 | 0 | 0 | 0 | 0 | 0 | 0 | 0 |
最初に求めた通り、確かに$c_{5,5}=2$となっています。
特性数が$0$の場合、任意の盤面が1通りの解を持ちます。
また、$c_{4,4}=4$や$c_{3,5}=3$のように$c_{m,n}= \min \{m,n\}$が成り立つときは、クリア可能な盤面であれば端に寄せるだけでクリアできます(寄せる操作については前々回の記事を参照)。この際、短い方の辺に向かって寄せます。
終わりに
ちょっと遊ぶだけのつもりが、思ったより大事になってしまいました。個人的には満足するところまでたどり着けたので、ライツアウトについての考察はここで一区切りとしたいと思います。
ちなみに、上で挙げた論文では特性数についてさらに分析していたり、また他の論文ではライツアウトの盤面を一般の有限グラフに拡張した話なんてのも研究されているようです(参考文献GP,PGY)。人間の知的好奇心は果てしないですね。
ではまた
